暑假训练快结束了，突然又想整个这个，零散的刷题时间也要积累起来，万一以后忘了呢。。。
数据结构专题
1. [SNOI2017]一个简单的询问
link：https://www.luogu.com.cn/problem/P5268
从来没有见过这么水的蓝题，一眼莫队板题，分开维护两个区间的和，加入一个数就减去原来的贡献，加上增加的贡献。删除亦然。
Tips：
- 块长要设为1000，会影响复杂度。
- 排序按 \(l1,r1,l2,r2\) 关键字排。
2. [USACO19DEC] Bessie's Snow Cow P
link：https://www.luogu.com.cn/problem/P5852
set+线段树。会发现如果点 u 已经染过A种颜色，那它的子孙就没必要再染了。所以给每个颜色开个 set 来存储染上这种颜色的点，暴力删除 set 里它的子孙，并加入这个节点。大概就是这样一个思路：
假设现在正在进行一个修改操作，将 x 染成 col 色：
- 找到 set 中 x 的前一个点，判断其是否是 x 的祖先，如果是的话直接 continue 跳过本次操作。
- 通过 set 找到 x 子树中已经被染上 col 色的节点。
- 将这些节点的子树权值总体减 1，同时把这些节点移出 set。
- 将 x 放入对应的 set，同时将 x 子树中的节点权值总体加 1。
Tips：
- 线段树大坑，一定要好好检查。
set是个很好用的东西，平常写代码时可以尝试一下。
3. [十二省联考 2019] 春节十二响
link：https://www.luogu.com.cn/problem/P5290
也不算太难。考虑贪心思想，大的和大的分成一段，小的和小的分。而考虑到不能有祖先--子孙关系，所以就是和父亲节点的其他儿子合并。用大根堆存储两个子树的答案，合并时取出堆顶，比较两个堆顶并得出最大值，把这些值再放入较大一点的堆里面，至于为什么要放到较大堆里面，可以用启发式合并来证明。
让高度小的树成为高度较大的树的子树，这个优化可以称为启发式合并算法。
摘自 OI-WiKi 。
Tips：注意 long long。
4. [SDOI2011] 消防
link：https://www.luogu.com.cn/problem/P2491
树的直径有这一结论：对于 任意树上的节点 , 距离其最远的点 一定为树的直径的端点。
所以整两个dfs把树的直径求出来。具体的，先从根节点跑一遍，求出直径的一个端点p，再从 p 跑一遍，即可求出另一个端点。
然后采用尺取法（移动区间），可以计算出在所有满足条件的最优情况下，最大值的最小值。（其实就是维护两个指针，根据s调整指针，再用记录这两个指针距离两个端点的距离 的最大值 的最小值）
但最远距离还可能是直径外的，所以再在直径的每个节点dfs一遍即可。
放一下代码吧：
dfs：
void dfs(int u,int fa)
{
f[u]=fa;
if(len[u]>len[p]) p=u;
for(int i=head[u];i;i=edge[i].next)
{
int v=edge[i].to;
if(v==fa||vis[v]) continue;
cout<<v<<endl;
len[v]=len[u]+edge[i].w;
dfs(v, u);
}
}
尺取法：
for(int i=p, j=p;i;i=f[i])
{
while(len[j]-len[i]>s) j=f[j];
ans=min(ans, max(len[i], len[p]-len[j]));
}
Tips：
- 最后搜索的时候要标记一下直径上的点。避免重复。
- 注意到 f 数组，存的不是父亲节点，而是直径上的前驱节点。
5. [HNOI2016] 序列
link：https://www.luogu.com.cn/problem/P3246
看着明显是一个莫队，但也可以强制在线。难点就是转移，从 \([l,r]\) 向 \([l,r+1]\) 转移，每次转移的变化由两部分组成：\([l,p]\) 和 \([p+1, r]\) ( p 是这个区间最小值)，前者贡献很好算，后者可以用dp求解，搞一搞dp式子可以发现它能预处理出来。
具体的：
设 \(f[l][r]\) 表示以 \(r\) 为右端点，左端点在 \([l,r]\) 的区间的答案(要求的就 \(f[p+1[r+1]\) )，记录一下 \(pre_i\) 表示从 \(i\) 向前第一个比 \(i\) 小的数的位置(这个可以单调栈O(n)求出)，那么左端点在 \([pre_r,r]\) 的区间最小值都是 \(a[r]\) ，那么就有 \(f[l][r]=f[l][pre_r]+a_r×(r-pre_r)\)。
可以发现 \(dp\) 增量只和 \(r\) 自身有关，所以可以去掉 \(l\) 那一维，因为最终一定会存在一个点
\(x\) ，满足 \(pre_x=p\)，那么 \(f_{r+1}=a_{r+1}×(r+1-pre_{r+1})+…+a_x×(x-p)+f_p\) 。
我们可以发现 \(f_{r+1}-f_p\) 就是原来要求的 \(f[p+1][r+1]\)。
RMQ：https://blog.csdn.net/qq_41311604/article/details/79900893
数论专题
明显刷题吃力了很多。。。数论还是我的弱项。
1. [ABC281G] Farthest City
link：https://www.luogu.com.cn/problem/AT_abc281_g
一层一层递推过来，dp[i][j]表示总共i个点，最后一层有j个点的方案数。
有dp转移式：\(dp[i][j]+=dp[i-j][k]*C_{n-i+j-1}^{j}*(2^k-1)^j*2^{C_j^2}\)。
k就是枚举前面每一层的最后一层的点数，\((2^k-1)^j\) 表示每个点向前面的k个点连线：\(C_k^1,C_k^1...C_k^k\) ，共有 \((2^k-1)^j\) 种方案。\(2^{C_j^2}\) 表示j内部的连线，共有 \(C_j^2\) 种连线，有 \(C_{C_j^2}^0,C_{C_j^2}^1...C_{C_j^2}^{C_j^2}\) 种方案数。
自己只推出来一半，剩下的式子还是推不出来。考虑的不够全面，还有所欠缺。
Tips：
- 二项式定理很重要，不要忘了。
TLE要预处理。- 取模别炸。
2. [ABC305G] Banned Substrings
link：https://www.luogu.com.cn/problem/AT_abc305_g
由于AC自动机学得比较晚，所以印象还是较为深刻的。但矩阵快速幂是真的忘得一干二净了。
考虑将所有不能匹配的串构建到AC自动机上，\(dp[i][son[u][1/0]]\) 表示到T的第i位，当前在u节点，下一个节点是a/b的方案数。注意到这是不能匹配的，做以维护一个数组记录每个点是否有结束标记，构建矩阵，用矩阵快速幂来优化，递推dp转移。
Tips：注意RE。
此题并未完全掌握，务必在学习AC自动机时再看一遍！！！
3. [CQOI2016] 密钥破解
link：https://www.luogu.com.cn/problem/P4358
虽然学新知识是好事，但这个 \(Pollard\,rho\) 给我看的够呛。
可以利用这种算法将N分解，就很轻松地得到p和q，根据扩展欧几里德定理即可求出d和n。
发现自己的扩欧学得还是不扎实，唉，赶紧填坑吧。
4. [NOI2018] 屠龙勇士
link：https://www.luogu.com.cn/problem/P4774
一眼excrt。
根据数据范围给出的表格，我们可以迅速发现 p 数组（有一个点都为质数）即为模数，就能立马推出式子：\(a[i]≡x*atk[i] (mod\,p[i])\)，发现和普通的excrt的区别就是多带了个*x，因为模数不一定为质数，所以我们无法用逆元求解，所以就考虑从excrt的本质操作入手。
excrt的过程其实就是两两联立相邻的两行方程，用扩欧求解，方程为：\(lcm*x+p_i*y=(a_i-ans)\) ，总共有 n-1 次合并，将 atk[i] 带入里面推式子，发现式子变为 \(atk_i*lcm*x+p_i*y=a_i-atk_i*ans\) ，也就多带了个 atk[i] ，所以直接改变excrt函数即可。
杀死每条龙的剑提前预处理即可，用multiset。
5.「雅礼集训 2018 Day10」足球大战
link：https://gxyzoj.com/d/hzoj/p/3990
其实是一道很简单的概率题，枚举主队和客队的赢的场数，直接递推即可，式子即为：
但是由于数据范围（1e7），要先预处理，边计算边枚举i，注意卡常。
Tips：
- 开两个1e7的数组会炸空间，但由于组合数都只需要n的阶乘，所以用一个数来存储 \(n!\)。
- 求逆元的写法可能会被卡，考虑换写法（详见数论）。
DP专题
1. [NOIP2021] 数列
link：https://www.luogu.com.cn/problem/P7961
发现n的范围极小，只有30，就可以考虑 \(O(n^4)\) 的复杂度。
因为在计算S的二进制表示时会有进位的现象，考虑从低位到高位转移，设 \(dp[i][j][k][p]\) 表示到S从低到高的第i为，已经确定了j个序列里a中的元素，前i位中有k个1，要向下一位进位p。
采取刷表法。
废，写不完了，等未来某一天再补吧。
2. [ABC234G] Divide a Sequence
link：https://www.luogu.com.cn/problem/AT_abc234_g
3. [春季测试 2023] 圣诞树
link：https://www.luogu.com.cn/problem/P9119
图论专题
1. 小L的有向图
link：https://gxyzoj.com/d/hzoj/p/2144?tid=66aa3ef2d0a287a57dccd3c8
2. 「NOIP2017」逛公园
link：https://www.luogu.com.cn/problem/P3953
3. [bzoj2438] [中山市选2011]杀人游戏
link：https://www.luogu.com.cn/problem/P4819
生活似海/起伏不定/无边总是看不到头/我欲乘风/浪迹远方/因为我并不平凡普通
标签：专项,cn,训练,luogu,www,link,https,com From： https://www.cnblogs.com/zhouyiran2011/p/18367931