A simple Blog for wyx I've been down the bottle hoping.
操作集锦……
发表于: | 分类: Oi | 评论:0 | 阅读:190

要NOI辣,真的不想做新题辣,然后就总结总结套路好了……

我就按照BZ AC倒序然后中间想到什么说什么了

我可能会一直说到NOI结束qwq

可能不是特别细致只是一些比较傻逼的个人总结


4929 第三题

多项式多点求值,需要利用多项式除法多项式取余,核心思想是分治构造用给定的点构造多项式然后直接对这个多项式取余然后继续分治。还是去看picks博客吧……

4923 K小值查询

这题我写过题解……

分值域讨论就好啦…… $<k$显然没有影响,$k<x<2k$他最后会变成 k以内,直接暴力插入剩下的大小关系都不变直接平衡树打标记就好啦

注意到每个数字最多被暴力插入log次因为log次之后就变成1了,更直接的每次减小一半

这类题好像贼多

4921 互质序列

我自从见到这个套路之后天天都是这坨题

区间gcd必然会在log次内变成1,因为每次去掉一个最小的质因数

4911 切树游戏

直接at自己博客吧……就是链分治

4903 吉夫特

一定是我考试的时候石乐志

注意到对$n$以内每个数字枚举子集的复杂度是 $3^{\log_2(n)}$

4900 密钥

一定是我考试的时候石乐志 *2

直接前缀和乱搞……事实上由于随机的太不上心,然后………………前缀和从来都在 -8~8 中间所以开16个前缀和也成……

4897 成绩单

一定是我做题的时候石乐志*3

我写的是二分历史最大值然后用可持久化trie

实际上直接每个节点记录次数为1234时刻是多少就行了

4896 补退选

直接 $N^5$ dp 一点都不虚,枚举起点终点最大值最小值然后中间再跑个dp

4887 可乐

矩阵乘法裸题

注意到最后加个计数器,然后计数器连个自环

4878 ~ 4886 BZ 五月月赛

at自己的博客

感觉比较好的题大概就是跌塔游戏那个有向图建图把 , $i\to j$表示以i为底然后 $j$为高,由于每个高度都只能有一个出度然后题目就简单了

4874 框子放球

没记错是个挺厉害的构造,好像是转化成图论,最后统计size为奇数的联通块个数就好

SHOI 2017

说几个有用的东西就好了……都说就写不完了

期末考试告诉我们考试的时候要努力读懂题……

相逢是问候是在叫我们ext欧拉定理

大概是
$$
a^b \equiv \begin{cases}
a^{b \bmod \varphi(p) } & { \gcd(a,p) = 1} \newline
a^{b \bmod \varphi(p) + \varphi(p)} & \gcd(a,p) \neq 1, b \geq \varphi(p) \
\end{cases}
\pmod p$$

注意到如果他根本就比 $\varphi(p)$ 小的话就直接快速幂就好了(捂脸)……………………………………

组合数问题:注意组合数的实际含义

摧毁树状图:直接dp吧……太麻烦了 saffah老师的错误标程告诉我们有时候基于度数的树形dp能get不少分

寿司餐厅: 当数据范围非常小限制非常强的时候写写网络流。还有就是数据范围小的时候随机化也有不少分

4864

直接splay没啥说的了

4843

这题还是挺巧的,注意到我们可以让人数等于负数,表示现在还剩下多少本书,思路巧妙

4836

套路:按照值域分治FFT

4833

套路:凡是满足$\gcd(f_i,f_j)=f(\gcd(i,j))$的,然后让你求$lcm(S)$的最后答案总是等于

$lcm(f(S)) = \prod_{\exists a \in S, d|a} g_d$

其中$g_x = \prod_{d|x} f(d)^{\mu(\frac{x}{d})}$

推导自己找我博客吧,斐波那契最小公倍数

4827

没啥说的了,随便推推发现是循环卷积然后就是傻逼题了

4826

这题教育我们如果遇到了树套树然后好像能离线,记得&……

写个线段树就好

4825

妙的一道题

用到了二叉搜索树的定义,然后就变成权值线段树求前驱后继了

4821

线段树随便乱搞就好

4819

看到除法就二分答案分数规划然后想想怎么验证就好了

4818

我就笑笑不说话

4817

注意lct原理,对于这题我们可以假设最开始都只有虚边,然后每次就是access了,在access的时候顺便处理一下虚边子树的答案

4816

推式子

卡常数

4815

推式子

分块

卡常数

怎么推式子看造化吧……

4811

按位统计大家都会然后你发现32棵线段树挂了

考虑和位统计……&……,维护全0和全1最后答案是啥,然后通过位运算解决问题

4810

当你发现bitset不会的reverse的时候怎么办

维护一个反的bitset

4809

不会的出门右转

4806

傻题,注意到我们只需要知道有多少个行有一个子有多少个行有两个子然后直接组合数转移就行了

4805

……………………………………………………

4804

枚举gcd发现后面变成了经典式子然后反演,然后就没有然后了

4796

这题一看就得按三位一分块吧,一画发现总能在一步之内使得一个块的权值为2

ZJOI day1

仙人掌看我题解吧,我到现在为止还是只会我的那个dp做法

树状数组是二维数点……最近做了不少二维数点,经典套路就是看着像是个数据结构然后每个点又有两个属性……

我记得吕老板有个归并排序,那题和这个神似……%

4774

n = 8 -> 暴搜/状压

然后就发现是状压直接斯坦纳树

4773

一个挺好的题,类似树上找lca的过程对距离矩阵矩阵乘法,相当于不断分解每个点的所有轨迹

4771

跪Claris教我做人

以后所有按层统计子树的题直接按层建主席树就好了,因为刚好是DFS序上的减法

4766

说起来很逗这题我们后来考了一个树的版本然后我和宋爷都没坐上

这题结论挺简单,值得让我门注意的是树是天然的二分图所以很多树上问题可以用二分图的性质解决如树上最大独立集我们可以直接用总点数减去最小匹配

这个确实是666

4764

lct维护外向基环树

一个环我们通常都能拆环

多个环?

缩点……

有没有特例?

有……我来科普一些科技吧,很多人都知道伪仙人掌上最大流的$log^2$做法但是实际上复杂度可以更低

通过这样的方法:拆掉一个环上的最小边权的边,然后把这条边的边权加到环上所有的其他的边上,然后问题变成树上两点最小值

对于修改直接lct就好了

4762

dls神题…………

看到计数想容斥我只能这么说了

JSOI 2016

最佳团体:看到比值想分数规划然后验证+1

扭动的回文串:这个思路很好,就是等效替代一下然后就变成每个位置二分的题了

4750

6666

我做了这题然后切了一道51nod 2333333

直接分治,以中点为中心维护前段的后缀最小/大值,后端的前缀最小/大值

然后做的时候注意到很多东西的单调性所以我们可以直接扫扫扫考虑指针所在位置的最大值和最小值就好了

4735

吉司机神题,直接考虑前缀和最小的地方然后考虑环的位置变化就好了

POI 2017

4726没啥意思……

4724好玩一些:考虑一个数字 $\bmod {p-1} \equiv 0$ 当且仅当他在b进制各位和是b-1的倍数……

因为$a\times B^{k} \equiv a \pmod {B-1}$ 算是trick吧

4707

注意到什么都不想直接把它当成权值矩阵dp就好了

然后发现二进制前面相同像极了平时写的线段树【跪】

然后就是树形dp了你敢信?

4706

OEIS

4668

我直接写了个lct

据说可以冰茶几

NOI 2016

优秀的拆分:跪正解的插标记统计,这个操作铭记在心

网格:注意特判所有的特殊情况

循环之美:我的做法和大家不一样,比大家的简单点,我直接上图吧
如果你看到这行字说明他挂了

区间:看到题的时候不要想得太难……,离线的时候扫扫还是挺好的

4644

好好读题+线段树分治

4631

跪Claris

直接链表+线段树就好

我石乐志写的set

4624

经典问题:最大权重子矩阵

解决方法:将两个矩阵补成一边大,空的地方补0,化成1维,reverse一个,直接卷,观察出每个位置的值其实就是相同-不同/总权值

注意最后更新答案需要在合法位置更新

styx

BZOJ上提交过的最长代码

看我题解吧……

4605

这题教导我们kdt不能写裸数组,就算不写指针也得写个结构题存一下,要不然常数*=3

4597

套路:有的题当某一变量足够大的时候答案确定,然后数据范围小……就暴力吧

例如:本题+UNR T1

4590

二分答案就好辣

4570

经典dp,然后考虑把$(i,f[i])$作为一个点,那么就有凸包辣

然后就二分一下就好啦

4568

写的不是正解但是能过,直接树剖维护一条链的线性基,查询就线性基合并吧……

线性基合并怎么合并?

拆了插入

4566

后缀自动机练习题

4561

经典扫描线,由于圆圆不相交所以上下关系不变qwq

4556

先二分答案然后就变成那个点的子树内有没有该区间的结束点

直接线段树合并就好啦

4553

基础数据结构练习题

4552

注意到查询只有一次所以我们可以二分答案,然后每次就变成了一段置1 一段置0

4551

你想怎么做就怎么做吧……

树剖/lct/冰茶几

HNOI

数据结构OI教我做人

4537:莫队不解释

4538:一个创造性的思维,把不在这条链的信息存在这条链上,然后用线段树+堆解决问题

4540:莫队/线段树,推荐ca题解

4542:莫队,注意又是刚才的套路,当一定情况下答案总是0……

4530

LCT维护子树信息,具体做法是维护tr表示一个点的所有儿子的信息,然后单独维护出一个点的轻儿子的信息就好啦

CQOI2016

K远点对:直接kdtree就好啦,每个点维护一个堆然后全局一个堆,双堆解决问题

手机号码:数位dp……记录是否有4是否有8然后什么后面几位都是啥反正他让你存啥你就存啥

一个细节是复杂度是除了第一位以外所有数字的乘积*位数

4503

模糊匹配,直接通配符设置成0就好啦

JSOI 2015

字符串树:我没记错好像是点分治/树剖

送礼物:看到比值想到分数规划,然后单调队列/线段树,bz上我的线段树过不去

子集选取:套路:一个经验丰富的选手能看出答案是$n^k$的形势,然后打表

salesman:我不知道为什么但是我的贪心过了

ZJOI 2016

小星星:n小+计数 = 状压+容斥

旅行者:套路:两两之间统计答案可以(1)分治(2)枚举中间点

4416

再次是套路:当某个变量足够大的时候答案固定系列

4407

考虑枚举gcd = d

然后就有 $ans = \sum_{d=1}^{min(n,m)}\frac{n}{d} \frac{m}{d} \sum_{x|d}\mu(\frac{d}{x}) x^k$

后面那个东西是两个积性函数的狄利克雷卷积显然是积性的考虑怎么筛

当两个东西互质的时候由积性函数知道直接乘在一起就好啦,考虑不互质怎么办,注意到不互质他所有约数$mu \neq 0$的部分是不变的,所以直接乘 $(prime[j])^k$ 然后你发现预处理就是nlogn了慢的要死

考虑优化,注意到只需要对素数处理整数次幂因为剩下的用不上,然后由于素数只有 $\frac{n}{\log(n)}$的,然后复杂度就是$On$的了

4399

看完输入的opt就知道咋回事了233333记忆犹新

然后就是线段树合并裸题

POI2015

我重新看了一遍自己的题解,大家也可以看我的题解qwq

4373

这类题突然非常常见诶

常见做法有完全条件判断/合法条件hash

这题的话完全条件判断比较好弄,注意到算每个差都是d的倍数直接搞搞gcd就好

4318

平方的期望!=期望的平方

然后算***的平方 -> 拆成三项分别算

4316

仙人掌求直径

4296

构造,记忆犹新

题目大意是给一个无向图,求一个最大的诱导子图使得每个点度数都$\ge d$

做法是把不足d的都扔进队列,然后用他们做头跑拓扑排序

4293

什么不足d的加到d大于x的减到x

两种套路:1,segmentbeats 2,直接排序然后每次就是连续的一段了

4276

线段树优化建图

这题都贼裸注意一下线段树上怎么连边就好了

4269

天天有人往bz传sb题

找一坨数字异或最大值就直接线性基就行了

次大值?

你想咋算就咋算吧,反正上面是可以贪心的

常见方法有:枚举(这个贼傻),然后还可以直接异或最小的,还可以高斯消元找控制位,反正你就瞎写写总是对的

4247

我NOIP之前做的忘了啥题了

4237

按照横坐标分治然后从大到小单调栈跑纵坐标就好啦

4236

挺好的思路吧,总能用上

把a-b的差相等变成a-a的差和b-b的差然后就能map了

4204

循环矩阵,就是对角线都是一个数字所以只需要拿一行快速幂就好辣

诶说到这个我想起了一个自己YY的一个分块矩阵

就是有一些递推式$f_n$里面带n,然后就没法直接矩阵乘法了,但是在模数非常小的时候他是以模数为循环节的然后就可以跑出模数以内的所有矩阵放在一起搞了

这方法我觉得是挺好的不知道哪有题

要是出题的话一个非常好的例子就是错排公式的递推公式

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP