NOIP 复习
最后的诗篇。
做题的套路
- 多读题多读题多读题!!一道题至少连带样例读三遍
- 注意形如
a_i \bmod a_{i + 1} = 0,a_{i+1} > a_i 这样的条件转化,往往把大问题缩小成小问题 - 注意特殊性质!!不要过度抽象问题从而挑战 NPC
- 二分别写挂。。。。
- 二分一个值判断是否合法,经常把
>x 设为 1,< x 设为 -1。 - 倍增能处理很多事情!很重要。
- ST 表不一定是区间最值,通过一些魔改也可以处理其他问题,猫树这种东西就算了(
- 中位数
\leq x 这个限制相当于>x 的数不超过\frac{len}{2} 个. - 约数问题如果数太大,考虑从唯一分解定理的角度的
p_i 考虑问题,\gcd 就变成求交,\operatorname{lcm} 就变成求并 - 考察题目如果有很强的两边可以分开考虑的性质,就优先分开考虑。
- 如果是字符串相关问题,优先考虑这个问题是不是和 LCP 有一定关系。如果有是好事,可以 二分+Hash来解决。
- 区间问题观察值域,如果值域不大可以考虑在值域上 DP 之类的来解决。
图论
经典套路
-
对于一些特殊的建图(e.g. 若
a_x | a_y 则有边(x,y,val) )这种边数起飞的情况,我们通常两种考虑思路:-
一个等效建边的思想,即如果
(x,z) 与(y,z) 同时建出,但是实际上与只建(x,z) 效果是一样的,那么我们可以通过只建具有“代表性”的边来优化建边条数。通常在一些连通性问题中这么考虑 -
建虚点,通过对边权转化来达到相同的效果。比如这个题ZR#2455
n 个点m 条边的有向图,每个点x 都有一个权值v_x ,每条边的长度均为1 。如果顶点
x 和y 满足v_x\operatorname{and} v_y=v_y ,则增加一条从x 到y 的有向边。现在想知道从
1 号顶点出发,到其他所有顶点的最短路径的长度。1\le n\le 200000,1\le m\le 300000 这个题暴力做最坏就是一个完全图,可以新增
2^{20} 个点,这些点中所有点向它所有的子集连一条长度为 0 的有向边。对于原来的所有点
x ,向v_x 连一条长度为 1 的边,然后v_x 向这个点连 0 的边。 由于边权只有 0 和 1,所以仍然可以 BFS,每次要把用 0 的边连接的所有点都加入队尾,以保证距离不降。这样的时间复杂度是
\mathcal{O}(3^{20} + n + m) 。但是可以发现对于新增的2^{20} 个点x ,只需要向x 去掉 某一位的1 的点连边。 这样的话,时间复杂度就可以变成\mathcal{O}(20 · 2^{20} + n + m) 。
-
-
矩阵转移
例如像 NOI2020 美食家 以及 NOI Online #3魔法值 这种题,一般是
n 可以支持n^3 ,而且询问的次数特别大的时候。挺套路的一个东西,证明一下题目中所求的东西是否满足结合律就可以了。要注意这种题的快速幂往往是先把转移矩阵
F 的幂求出来,然后再用向量乘矩阵的n^2 来保证复杂度正确。 -
分层图
也是套路化的东西,不再赘述。
最小生成树
关于 MST 有一些非常经典的性质与推论,可以启发思考。
性质 1:对于一条非树边
(x,y) ,树上x\to y 上边的最大值的权值小于等于非树边的权值
证明:反证法。考虑
做这类题的时候不要拘泥于 Kruskal,有时候 Prim 和 Boruvka 有奇效。
Kruskal 重构树
这个东西解决的问题比较抽象一点,和生成树本身没啥关系了,具体可以看之前我写的 blog.
最短路
就是几种算法:SPFA,Dijkstra,Floyd
注意如果只是求传递闭包的话 Floyd 记得用 bitset:
// std::bitset<SIZE> f[SIZE];
for (k = 1; k <= n; k++)
for (i = 1; i <= n; i++)
if (f[i][k]) f[i] = f[i] | f[k];
然后如果边权特殊的图注意能不能 01 bfs,也就是队头 push 0,队尾 push 1。
连通性问题
咕咕,赌他不考
欧拉回路类问题
首先板子要记住,用一个类似当前弧优化的东西才能保证复杂度不退化到
vector <pii> G[N];
vector <int> ans;
int n,m,tot,d1[N],d2[N],cur[N];
bool vis[N];
void dfs(int x) {
for (int &i = cur[x];i < G[x].size();++i) {
pii &e = G[x][i];
int y = e.first;
if (!e.second) {
e.second = 1;
dfs(y);
}
}
ans.push_back(x);
}
signed main() {
read(n,m);
for (int i = 1;i <= m;++i) {
int x,y;read(x,y);
G[x].push_back(mp(y,0));
d1[x]++,d2[y]++;
}
for (int i = 1;i <= n;++i) sort(G[i].begin(),G[i].end());
bool flag = 1;
int cnt1 = 0,cnt2 = 0,s = 1;
for (int i = 1;i <= n;++i) {
if (d1[i] != d2[i]) flag = 0;
if (d1[i] - d2[i] == 1)++cnt1,s = i;
if (d2[i] - d1[i] == 1)++cnt2;
}
if (!flag && !(cnt1 == 1 && cnt2 == 1)) {
puts("No");
return 0;
}
dfs(s);
reverse(ans.begin(),ans.end());
for (auto x : ans) printf("%d ",x);
return 0;
}
这类问题难点在于抽象出欧拉回路的模型。例如这个题
你有
n 个二元组,第i 个二元组的值为(a,b) 。任意两个二元组都不相同。求是否存在一个二元组的排列,使得这些二元组满足对于任意
1≤i<n ,有A_i=A_{i+1} 或B_i=B_{i+1} 。且对于任意2≤i<n ,A_{i−1}=A_i=A_{i+1} 和B_{i−1}=B_i=B_{i+1} 都不成立。如果有解,你还需要找到字典序最小的解。我们认为一个二元组的字典序更小,当且仅当这个二元组在输入中更早出现。
n \leq 5\times 10^5
这个题最厉害的在于,把
基环树
NOIP 考过的东西……感觉找环很重要!Mark 一个
int to[N<<1],nxt[N<<1],hd[N],tot = 1;
inline void add(int x,int y) {to[++tot] = y;nxt[tot] = hd[x];hd[x] = tot;}
inline void addedge(int x,int y) {add(x,y);add(y,x);}
ll a[N],n,l,r,f[N][2],ans,e;
void findcir(int x,int f) {
vis[x] = 1;
for (int i = hd[x];i;i = nxt[i]){
int y = to[i];
if (y != f) {
if (!vis[y]) findcir(y,x);
else {
l = x,r = y;e = i;
}
}
}
}
ll DP(int x,int fa) {
for (int i = hd[x];i;i = nxt[i]) {
int y = to[i];
if (y != fa && i != e && (i ^ 1) != e) {
DP(y,x);
}
}
return 0;
}
大概只需要找出环中间的那条边,然后就可以开搞啦!如果有必要的话可以记录一下每个点的父亲,然后递归回去。
基环树的问题大部分都是先想一颗树上要怎么做,然后再把这个问题放到环上来考虑。
常用有两种套路:
-
断环
例如 ZJOI2008 骑士 这个题就是枚举环上的每条边,然后断开这条边进行 DP。我实现的比较暴力就直接每次都断开来思考了。
-
分类讨论
例如 IOI2008 Island,暴力找环,树上 DP,环上拆链 DP。
二分图网络流
不做额外复习,参考NOI 一轮复习 I:二分图网络流 - ix35
动态规划
DP 三要素
状态,决策和转移。其中 “状态” 又最为关键,决策最为复杂。这三点直接决定了一个 DP 的好坏。
“状态” 的优化可以从很多角度出发,思维难度及其高,有时候状态选择的好坏会直接导致出现暴零和满分的分化。
“决策” 优化则有着大量模板化的东西,相对考察选手码力。
线性 DP
如果某个维度(例如读入顺序)上 DP 特别难做,考虑换一个角度(例如在值域上)进行 DP。
一定要注意把 DP 的式子写出来!然后再考虑怎么上优化。
1D 的 DP
因为状态一般简化,所以我们从决策的角度来考虑如何优化
f_x = \max\limits_{l_x\leq y\leq r_x} \{f_y\} + val_x - 如果相邻状态的段的左右区间满足非降的关系,那么可以直接上单调队列做到均摊
\mathcal{O}(1) ,总时间复杂度\mathcal{O}(n) 的东西 - 如果区间没有特别的关系,但是满足
r_x \leq x 那么可以把f 拍到线段树上来进行转移,这样就做到单次\mathcal{O}(\log n) 总时间复杂度\mathcal{O}(n\log n)
- 如果相邻状态的段的左右区间满足非降的关系,那么可以直接上单调队列做到均摊
f_x = \sum\limits_{y = l_x}^{r_x} f_y - 一般考虑维护一个
g_x = \sum\limits_{y = 1}^x f_y 来进行前缀和优化。
- 一般考虑维护一个
2D 的DP
这类题目就复杂很多,通常两个方面入手。
-
状态能否优化?
这主要考虑的是我们状态有没有表示出正确的东西,如果换一个角度来表示就会好很多。这个东西好像很智商(
或者我们另一个角度考虑,我们能否把一些比较好求的东西求出来,换一个方式 DP?
一道题:
我们定义一个整数序列是好的当且仅当
-
\forall 1 \leq i \leq n,1 \leq a_i \leq m \forall 1 \leq i < n 有以下两个条件至少成立一个:a_i \le a_{i+1} (a_i \bmod a_{i+1}) > 0
求有多少个序列是好的。
n,m\leq 10^5 我们很容易设计出暴力 DP,即
f_{i,j} 表示第i 位选j 的方案数,暴力转移是\mathcal{O}(nm\log m) 的。发现转移基本上没啥可以优化的点了,但是我们发现,我们从反面考察,两个都不成立的就是:
a_i > a_{i + 1},a_i\bmod a_{i+1} = 0 。我们考虑这个序列的长度实际上很短,最长只有\log n 级别的。所以我们考虑容斥,预处理出g_i 表示长度为i 的不合法子串,然后转移就变成了f_i = \sum (-1)^{len} g_{len}\times f_{i - len} 这样做到了
\mathcal{O}(n\log^2 m) 。 -
-
转移能否优化?
这类的方法和 1D 类似。
区间 DP
咕咕。
树形 DP
树上背包
不再赘述,本质上看成一个
DS
讲道理,感觉 NOIP 并没有很显式的考察某种 DS。最多就是扫描线之类的问题(奶)。
ST 表
需要注意的大概是建表的时候第二层循环的写法:
本作品采用 知识共享署名-相同方式共享 4.0 国际许可协议 进行许可。