降低预期 降低预期 降低预期
无符号：独立做出
\(\large\color{orange}+\) 号：经过或多或少的提示做出
\(\large\color{red}?\) 号：看题解做出
1.29
- CF1790F Timofey and Black-White Tree \(\large\color{orange}+\)
见过类似的题：CF1039D You Are Given A Tree
考场上想到类似的思路，似乎因为二分的 check 没细想而放弃。
- CF1790B Taisia and Dice \(\large\color{orange}+\)
赛时的暴搜被卡了，改写贪心了。不知道怎么评价，也许考场上要冷静、多想（？）
- P8267 [USACO22OPEN] Counting Liars B
感觉比较经典的 trick：使撒谎奶牛数最小的位置一定能在端点 \(p_i\) 上取到，枚举 + 计数，\(O(n^2)\)。排序之后双指针可以做到 \(O(n\log n)\)。
- P8268 [USACO22OPEN] Alchemy B \(\large\color{orange}+\)
正着做不好做，不如反过来从 \(n\) 往回走。外层再套个二分答案就好了。当一个值被放在图上，不断地由一个点给它的出边连向的点累加的时候要注意结果是指数级的，要特判。（因为这看讨论区才找到错误）
- P8266 [USACO22OPEN] Photoshoot B
感觉是思维题，但是自己做出来了。把对结果没贡献的删掉就好做了。
- P8269 [USACO22OPEN] Visits S
很常见的基环树的题。找基环树上的环似乎有蛮多做法：
- 双向边可以用 dfs 记录路径找环或求边双连通分量。
- 有向边 \(i\rightarrow a_i\)（内向基环树森林），并查集或拓扑排序或求强连通分量。
- P8270 [USACO22OPEN] Subset Equality S\(\large\color{orange}+\)
比较很多个元素可以转为比较两个元素，再合并。用了类似 trick 的题：CF1781D 枚举两个数确定 \(x\)；CF1772D 对于所有 \(1\le i < n\) 满足 \(\left|a_i-x\right|\le \left|a_{i+1}-x\right|\)（也就是只需要考虑相邻两个数），就可以得到：\(\left|a_1-x\right|\le \left|a_2-x\right|\le\cdots \le \left|a_n-x\right|\)。
可以通过 \(ab\) \(bc\) \(ac\) 合法得到 \(abc\) 合法，感觉类似于不等式的关系（？ \(p_i<p_j\)，\(p_i>p_k\)，不能确定 \(p_j\) 和 \(p_k\) 的关系，而等号可以）。用 vector 存位置 + 前缀和可以做到 \(O(\left|\Sigma \right|n+\left|\Sigma \right|^2q)\)。
- P8271 [USACO22OPEN] COW Operations S\(\large\color{red}?\)
思维题，但是比 B 的 T3 难不少。
最精妙的解法：赋值：空为 \(0\)，C 为 \(1\)，O 为 \(2\)，W 为 \(3\)。可以发现，操作可以转化为，选取相邻两个数，将它们删去，将它们的异或和填入。因为异或满足结合律、交换律，所以直接求异或前缀和判断区间 \([x,y]\) 的异或和是否为 \(1\) 就可以了。（欣赏性做法，大胆赋值？）
想到了操作是可逆的 WO -> WWC -> C，但是不会再往下推了：OW -> OOC -> C -> WO。得到操作能够使相邻两个字符交换。可以通过这样的操作使区间有序，同时通过删除操作使得每种字符最多出现一次。这样就好考虑了，能够得到字符 C 的只有两种情况： OW 和 C。
1.30
1.31
2.1
晚上 CF，心态爆炸，D 写了一坨答辩，没调出来，错失良机。期望是最终状态定（0），转移从下往上，概率是最初状态定（1），从上往下。改变观念，改变观念，改变观念，并非如此。通过确定已知状态的期望或概率，求出未知状态的期望或概率。
2.2
后缀数组
2.3
whk 来了！！！
2.8
【CF1270F】Awesome Substrings
【国家集训队】数颜色 / 维护队列（带修莫队）
【SHOI2009】舞会
【SCOI2007】最优驾车
【CF1523E】Crypto Lights
2.9
已经 2.9 了……
早上网络流，晚上 CF
二分图中 最大匹配 = 最小顶点覆盖
最小顶点覆盖 + 最大独立集 = 总点数
【USACO07OPEN】Dining G
【ICPC-Beijing】狼抓兔子
【网络流 24 题】骑士共存问题
【SCOI2007】蜥蜴
【SCOI2007】组队
老妈生日。
晚上 CF E dp 裸题，但是没有想到用 DP 做，被 LA 群的傻逼干扰了，在那里想”暴力“是什么。
DP：You don't even think to call me Godfather.
但是把 D 写出来了，还不错。
2.10
【SDOI2010】星际竞速
建模与 餐巾计划问题 有些类似（当然都没做出来也是共同点），都存在“状态割裂”，那题将 新毛巾 和 旧毛巾 割裂，这题把 到达一个点 和 从一个点出发 割裂。
【BZOJ1283】序列
不会。很智慧的一步，转化题意：选 \(1\) 次转化为选 \(k\) 次，每一次选的数的间隔大于等于 \(m\)。
【SDOI2016】数字配对
前半部分不会……首先连出来的是个二分图，然后只会 \(O(\dfrac{n^2\sqrt V}{\log (\sqrt V)})\) 暴力判 + 连边，T 飞了（也许以后想到这还需要再想一下，算一下运算次数，然后进一步改进思路）。正解是预处理每个数的质因数个数 \(c_i\)，如果两个数 \(i,j(a_i>a_j)\) 中间有连边，首先需要满足 \(c_i=c_j+1\)（根据这条更好地说明了图是二分图），然后再判 \(a_i\) 是否是 \(a_j\) 的倍数。还有一个结论，最小费用最大流每次跑出来的最短路长度是递增的。
【HAOI2006】数字序列
嗯……写了一万年。想错了，还要重写。想了挺多错误的结论，不得不不断重写。首先第一步：\(a_i-a_j\ge i-j\) 才能保证当保留 \(a_j\)，\(a_i\) 仍可以保留。然后就可以 DP，令 \(b_i=a_i-i\)，就是个 LIS。 这里出现了第一个错误：计算保留的两个数之间的区间 \((j,i)\) 所需要改变的最小值，也就是代价，我直接用 \(b\) 做了（即把大于 \(b_i\) 的降为 \(b_i\)，小于 \(b_j\) 的升为 \(b_j\)），但这是错误的。本来以为它活了，结果它又死了。错误原因有所改变，一开始以为它错是因为更改完后无法满足 \(a_i<a_{i+1}\)，但 \(b_i+i<b_i+i+1\)。实际上是因为 \(b\) 有大有小，可能“大小大”，导致还原后不合法。然后第二个错误的原因：整个数列都需要更改，所以需要在末尾补上一个极大值，然后答案为这个新增位置的 DP 值才能保证都被修改。这种情况感觉以后可能还会遇到不少次，引以为戒。结论：随机数据下 LIS 长度是 \(O(\sqrt n)\) 的。
2.11
【SDOI2013】费用流
感觉不算难，但也调了挺久的。注意一下最大流中流量最大的边可以为小数。
【CF1784C】Monsters（hard version）
不知道为什么老师讲的这么复杂，实际理解和写起来似乎没有那么难。
【CF1784D】Wooden Spoon
考虑计算 \(n\) 个对手固定时的答案（看起来很显然，但是自己未必能想到），得到一个长串的连乘的式子，然后 \(f[i][j]\) 表示第 \(i\) 轮是 \(j\)，它将输在第 \(i+1\) 轮，就可以倒着 DP 了。
【CF1778D】Maximizing Root
嗯....又写错了，套了数据，继续调试。莫名其妙地过了？？？
一个比较大的错误：当对以点 \(x\) 为根的子树操作时，设现在求 \(f[x][i]\)，乘上的不一定是最小的可能值 \(\dfrac{d_i}{\gcd(a_x,d_i)}\)，可能乘上更大的数使子树内更优。
晚上打了 ABC。
【ABC289G】Shopping in AtCoder store
考场上首先想到了每个商品都是独立的，分开考虑，同时 \(P\) 的取值只可能有 \(n\) 种，即 \(B_i+C\)。这时的我只会二分求出来满足 \(B_i+C\ge P\) 的个数，然后就不会了。问了老师之后，才意识到结论：把 \(B\) 从大到小排序后，当把 \(P\) 的值定为 \(B_i+C\) 的时候，满足 \(B_j+C\ge P\) 的 \(j\) 的个数就是 \(i\)！！！然后就可以转化为对于每一个 \(C\)，求 \(B_i\cdot i+C\cdot i\)。这显然是一个类似斜率优化的式子！其中 \(k=-C\)，\(x=i\)，\(y=B_i+i\)，最大值 \(b=y-kx\)。（我还是觉得斜率优化表示成截距然后数形结合更好理解），建出上凸包（斜率递减），然后把 \(C\) 从小到大排序（斜率 \(k\) 递减）即可。说真的，我又忘了斜率优化，写了挺久的。
2.12
【CF1788F】XOR, Tree, and Queries
不算难的 CF Div.2 F，把树上一条链的权值通过树上差分转成两个端点之间权值得关系（在 NFLS 见过一次得而 trick），用带权并查集做。
【ABC289F】Teleporter Takahashi
当目前处于 \((x,y)\) 时，选择 \((z,w)\)，目标状态为 \((2z-x,2w-y)\)。这是如果第一次选择 \((a+1,c)\)，第二次选择 \((a,c)\)，得到 \((2a-[2(a+1)-x],2c-(2c-y))\)，即 \((x-2,y)\)。类似地，可以发现单次可以使 \(x\) 或 \(y\) \(+2\) 或 \(-2\)。然后不断移动就可以了。特判一下 \(a=b\) 和 \(c=d\) 的情况。
【LuoguP1654】OSU!
一个trick，想求高次 \(k\)，就把 \(1\sim k\) 次都存下来，通过低次转移。
下午本来有场 CF，想了蛮久的不会 A，心态爆炸，逃跑了（当然这场也因为 F 是原题，同时 CF 暴政而臭名昭著）。以后杜绝这种情况。我甚至应该感到高兴，这是为数不多能严厉地考察考场心态的机会。
2.13
【NOIP2016 提高组】换教室
虽然这题一眼 DP，但是搞了挺久的。主要问题在于对期望的线性性质不熟啊，怀疑自己对的做法是错的好久。根据期望的线性性质，可以单独地计算相邻两节课所需要行走的期望路程，并将它们加起来。
【LuoguP5011】水の造题
期望题，计算 \(N\) 个位置原本贡献，相邻两个位置的额外贡献。（期望的线性性质使得它可以算贡献）。
【HNOI2015】亚瑟王
一直在想 \(i\) 在第 \(j\) 轮发动的概率？从简单的情况入手，第一张牌发动的概率为 \([1-(1-p_1)^m]\)。第二张牌则需要考虑第一张牌的情况了，如果第一张牌在某一轮发动了，那么第二张牌的发动概率为 \([1-(1-p_1)^m][1-(1-p_2)^{m-1}]\)，在第一张牌发动的那一轮，第二张牌不发动的概率为 \(1\)（也就是不能发动）；如果第一张牌没有发动过：\((1-p_1)^m[1-(1-p_2)^m]\)。这是个一大串的连乘式子，考虑 DP，设 \(f[i][j]\) 表示第 \(1\sim i\) 张牌中，有 \(j\) 张牌发动的概率。
转移：第 \(i\) 张牌不发动：\(f[i-1][j]\times (1-p_i)^{m-j}\)；第 \(i\) 张牌发动：\(f[i-1][j-1]\times [1-(1-p_i)^{m-j+1}]\)。
最后计算答案（又是期望的线性性质）：\(\sum\limits_{i=1}^{n}\sum\limits_{j=0}^{\min\{i-1,m\}}d_i\times f[i-1][j]\times [1-(1-p_i)^{m-j}]\)。注意这里是 \(f[i-1][j]\)，在这里写错过， \(i\) 需要特别计算使用的概率，因此是 \(i-1\)。
总之，期望的线性性质异常重要，在上述三道题中都有涉及。
2.14
【CF1151F】Sonya and Informatics
观察到交换方案的总次数很好算，为 \(\frac{n(n-1)}{2}k\)。考虑计算 \(k\) 次交换后 0/1 串变成非降序列的方案数，除以总方案数得到的就是概率。继续观察，发现性质：设 0/1 串中 \(0\) 的个数为 \(m\)，最终的序列一定形如 \(\underbrace{0\dots 0}_{m}\underbrace{1\dots 1}_{n-m}\)。这样就可以把数分成四类：在前 \(m\) 位合法的 \(0\)，在后 \(n-m\) 位不合法的 \(0\)，在前 \(m\) 位不合法的 \(1\)，在后 \(n-m\) 位合法的 \(0\)。再此基础上观察交换的操作，设合法的 \(0\) 有 \(i\) 个（剩下的 \(3\) 类都可以通过 \(i\) 表示），都可以成为 \(i-1,i,i+1\) 状态之一，然后就可以 DP 了，最后再放入矩阵就可以了。
最难点可能在于我会认为计算 \(k\) 次交换后 0/1 串变成非降序列的方案数不可做，但这都要想过之后才知道，不是吗？敢想敢试！！！不过说实话，这题写了挺久的，原因是我推错了两次式子。Think Twice,Code Once.
【ZJOI2015】地震后的幻想乡
2.15
【USACO12FEB】Cow Coupons G
2.16 2.17
whk 考试
2.18
矩阵树定理。不会行列式。不认真地学习行列式失败。
2.19
线性空间、线性基，不会。
浪费两天。只有六周了。
2.20
【CF1778E】The Tree Has Fallen!
询问以 \(r\) 为根，\(x\) 的子树巴拉巴拉，似乎没怎么见过，看起来很吓人。先把 \(1\) 拿出来作为根。询问时小小分讨一下：\(r=x\)，就是整棵树；\(x\) 是 \(r\) 的祖先，就是整棵树把 \(r\) 的仅次于 \(x\) 的祖先的子树部分扣掉；其它情况就是以 \(x\) 为根的子树。最后套个线性基，线性基合并是 \(O(\log^2V)\) 的 。
【WC2011】最大XOR和路径
感觉还是有点智慧的。异或的性质：把一段链异或两次它就相当于没走过了。然后从 \(1\sim n\) 的路径就可以表示为一条链和若干个环的异或和。根据性质，一条链其实可以跟一个在链上的环异或起来得到一条新的链，还可以是链与一个不在链上的环的异或值，也就是从链上走到环上，在环上回来的结果。
很智慧，但既然见过了，就把它当作结论记了：无向图从 \(u\) 到 \(v\) 的 XOR 和路径可以通过 dfs 树上 \(u\) 到 \(v\) 的 XOR 和和若干个通过返祖边组成的环表示出来。
【LuoguP7112】[模板]行列式求值
今天又大致学了一下，其实第一篇题解只是讲了几个证明，看起来比较复杂罢了。暂时跳过证明。
行列式定义：\(\det(A)=|A|=\sum\limits_{p}(-1)^{\tau(p)}\prod\limits_{i=1}^{n}a_{i,p_i}\)，其中 \(\tau(p)\) 表示排列 \(p\) 的逆序对个数。
性质 1：交换两行（列），行列式变为相反数。
性质 2：给某一行的所有元素对应地加上另一行的所有元素乘一个常数，行列式不变。
然后根据这两个性质，就可以通过类似高斯消元的方法，把矩阵转变为上三角的形式，行列式就是转变后的矩阵的对角线的积。具体地，把一个数消为 \(0\)，可以通过辗转相除法。经过一些复杂度分析，设模数为 \(p\)，时间复杂度是 \(O(n^3+n^2\log p)\) 的。
int calc(){
bool t = 0;
int res = 1;
for(int i = 1;i <= n;i++){
for(int j = i + 1;j <= n;j++){
while(a[j][i]){
int div = a[i][i] / a[j][i];
for(int k = i;div && k <= n;k++)
a[i][k] = (a[i][k] - 1ll * div * a[j][k] % Mod + Mod) % Mod;
swap(a[i],a[j]),t ^= 1;
}
}
}
for(int i = 1;i <= n;i++)
res = 1ll * res * a[i][i] % Mod;
if(t)res = -res;
return (res + Mod) % Mod;
}
【HEOI2015】小 Z 的房间
矩阵树定理板子。
【中山市选】生成树
图有特殊性质，显然每个五边形中至少断掉一条边（这五条边构成了一个环，并且 \(n\) 个环没有相交的边）。但是这还不够，还需要再隔断一条边。钦定 \(n\) 个五边形中断掉两条边的，一共有 \(n\) 种选择。进一步考虑，发现内部的圈与五边形相连的边必须断掉，即当五边形断掉两条边时共有四种选择。方案数为 \(4n5^{n-1}\)。
直接用矩阵树定理也是能过的。图看起来有规律的还是要试着想想其它做法再用矩阵树定理。
2.21
【FJOI2007】轮状病毒
DP，不用矩阵树定理。注意环上问题断开成链后要特殊考虑跨过断点的区间。
【BZOJ5056】OI 游戏
正权图（图中一定无负环和零环）把 \(d_x+w_{x,y}=d_y\) 的边连上后是一个 DAG。这题不需要这个性质，直接把边连出来，矩阵树定理求以 \(1\) 为根的外向树的方案数。
【LuoguP6178】[模板]Matrix-Tree 定理
无向图，定义 Laplace 矩阵：\(L_{i,i}\) 的值为 \(i\) 的度数，其余 \(L_{i,j},i\neq j\) 的值为 \(-e_{i,j}\)。方案数为去掉第 \(i\) 行和第 \(i\) 列后的矩阵的行列式。
有向图，以 \(i\) 为根的外向树定义 \(L_{i,i}\) 的值为 \(i\) 的入度，其余 \(L_{i,j},i\neq j\) 的值为 \(-e_{i,j}\)。以 \(i\) 为根的内向树定义 \(L_{i,i}\) 的值为 \(i\) 的出度，其余 \(L_{i,j},i\neq j\) 的值为 \(-e_{i,j}\)。方案数为去掉第 \(i\) 行和第 \(i\) 列后的矩阵的行列式。
【SHOI2016】黑暗前的幻想乡
每个公司都要修的条件太苛刻了，容斥！\(2^n\) 枚举没有修的公司的集合，然后用矩阵树定理求方案数。复杂度是 \(O(2^nn^3)\) 的。
【CQOI2018】社交网络
【JSOI2010】巨额奖金
利用矩阵树定理计算最小生成树个数。
最小生成树树性质：1. 当把 \(\le w\) 的边连上后，图的连通性是确定的。2. 只有权值相同的边才可能互相替换。
枚举出现的边权 \(w\)，把树上为 \(w\) 的边断掉，其余保留并缩点。缩完点后把所有 \(w\) 的边加入，用矩阵树定理求方案数，根据性质 2 用乘法原理求总方案数。
用矩阵树定理通过的题：P4111 P4821 P6178 P4336 P4455 P2143
【六省联考2017】分手是祝愿
比较神的第一步：从高往低摁按钮，考虑到 \(i\) 时，若 \(i\) 仍亮着，由于 \(i\) 的倍数都已考虑过，\(i\) 必须操作，这就是最优的方案（类似的操作我也见过，要注意考虑）。然后把它放到 DP 状态里，就是个期望 DP 板子。如果从终态过来的期望不好考虑，可以考虑相邻状态的期望。
【CF1781F】Bracket Insertion
合法括号序列一个性质：把 ( 当作 1，) 当作 -1，每个位置的前缀和都大于等于 \(0\)，且总和为 \(0\)。
第二点一定满足，只用考虑第一点，将题意转化为维护一个自然数序列，每次可以选择一个数 \(x\)，将它改为三个数 \(x,x+1,x\) 或 \(x,x-1,x\)。设 \(f(i,x)\) 表示初始的数为 \(x\) 做了 \(i\) 次操作合法的概率。然后就可以通过考虑三段转移 DP 了。
2.22
【LuoguP3600】随机数生成器
概率 DP。枚举 \(x\)，通过转化求最大值小于等于 \(x\) 的概率 \(p_x\)，最大值恰好为 \(x\) 的概率为 \(p_x-p_{x-1}\)。方便 DP 把包含其它区间的区间去掉。DP，和下面异曲同工，同样枚举最右的小于等于 \(x\) 的位置，得到转移式 \(f_i=\sum\limits_{j=l}^{i}f_{j-1}\times \dfrac{x}{m}\times(1-\dfrac{x}{m})^{i-j}\)。
\(((A\times B)\times C)_{i,j}=\sum\limits_{k=1}^n\left(\sum\limits_{l=1}^nA_{i,l}\times B_{l,k}\right)\times C_{k,j}=\sum\limits_{k=1}^{n}\sum\limits_{l=1}^{n}A_{i,l}\times B_{l,k}\times C_{k,j}\)
\((A\times(B\times C))_{i,j}=\sum\limits_{k=1}^{n}A_{i,k}\times\left(\sum\limits_{l=1}^{n}B_{k,l}\times C_{l,j}\right)=\sum\limits_{k=1}^{n}\sum\limits_{l=1}^{n}A_{i,k}\times B_{k,l}\times C_{l,j}\)
广义矩阵乘法：\(\times\) 有结合律、交换律。\(\times\) 对 \(+\) 有分配律。
【NOI Online #3 提高组】魔法值
矩阵加速板题。关键点在于预处理 \(A^{2^i}\)，转为 \(1\times n\) 的矩阵乘 \(n\times n\) 的矩阵，做到 \(O(qn^2\log k)\)。
【CF1737E】Ela Goes Hiking
首先需要观察蚂蚁 \(i\) 怎么才能赢。除了最后一只蚂蚁 \(i\)，其余如果初始朝右必输。分成两段，打败 \(1\sim i -1\) 和撞墙回来打败剩余的蚂蚁。想错了蛮多次，主要在后半段，后半段与前半段有较大区别，这种地方要多确认几次再想实现细节。前半段只要前大半蚂蚁朝右就能一直赢（一开始想枚举第一个向左的蚂蚁，但没有必要，大于一半后剩下的不用管，赢的概率为 \(1\)），后半段考虑 DP，设 \(g_i\) 表示大小为 \(i\) 的蚂蚁，打败 \(i+1\sim n\) 蚂蚁的概率。\(g_n\) 已知为 \(1\)，从后往前 DP，枚举第一个向左的蚂蚁得到转移式：\(g_i=\sum\limits_{j=i+1}^{2i-1}2^{j-i}g_j\)。
\(a,b\) 均为正整数，\(\lceil\dfrac{a}{b}\rceil=\lfloor\dfrac{a+b-1}{b}\rfloor\)
满足 \(ax\le b\) 的最大整数值 \(x=\lfloor\dfrac{b}{a}\rfloor\)
满足 \(ax<b\) 的最大整数值 \(x=\lfloor\dfrac{b-1}{a}\rfloor\)
满足 \(ax\ge b\) 的最小整数值 \(x=\lceil\dfrac{b}{a}\rceil=\lfloor \dfrac{b+a-1}{a}\rfloor=\lfloor\dfrac{b-1}{a}\rfloor+1\)
满足 \(ax>b\) 的最小整数值 \(x=\lceil\dfrac{b+1}{a}\rceil=\lfloor\dfrac{b+a}{a}\rfloor=\lfloor\dfrac{b}{a}\rfloor+1\)
2.23
【CF1278F】Cards
首先有暴力式子：\(\sum\limits_{i=1}^{n}(\frac{1}{m})^i(1-\frac{1}{m})^{n-i}C_n^ii^k\)。奇妙的转换：考虑大小为 \(x\) 的集合 \(\{a_1,a_2,\dots,a_x\}\)，\(a_i\) 表示第 \(a_i\) 轮第 \(i\) 次摸到了 Joker。期望 = 概率 \(\times\) 权值，它的权值应该为 \(x^k\)，\(x^k\) 的组合意义为有 \(x\) 种数可选，长度为 \(k\) 的序列个数，转化题意，考虑每个序列对期望的贡献。对于所有值域为 \([1,n]\) 的长度为 \(k\) 的整数序列，设其中一个序列的不同数的个数为 \(i\)，则它出现的概率为 \((\frac{1}{m})^{i}\)。设 \(f(i,j)\) 表示长度为 \(i\) 且不同的数个数为 \(j\) 的序列个数，\(k^2\) 求即可。当 \(k=1\) 时，期望为 \(\dfrac{n}{m}\)，可以理解为对第 \(i\) 次仍摸出 Joker 的概率求和。
【NOI Online #1 入门组】魔法
第一眼看上去像分层图，注意边权可以为负，要用 SPFA，复杂度 \(O(nmk)\)。
\(k\) 太大了，换做法。DP，设 \(f(d,i,j)\) 表示 \(i\) 到 \(j\) 用了 \(d\) 次魔法的最短路，同时定义 \(A(i,j)=\min\limits_{(i,x)\in E}\{-w(i,x)+D(x,j)\}\)。得到 \(f(d)=f(d-1)\times A\)。矩阵加速即可。
犯的错误：\(k\) 次魔法不一定全用（有可能用不出来），所以 \(A(i,i)\) 要和 \(0\) 取 \(\min\)。
【LuoguP9089】Work
做 CF、Luogu 比赛的题，要下意识地写双模哈希。
思考过程：去掉合并，考虑 \(n=1\)，再考虑 \(n>1\)，最后考虑合并并计算答案。
如果去掉合并，并且 \(n=1\)，就算串的后缀和串的 LCP，多个串就把所有前缀通过 Hash 存下来，二分求 LCP 时查询，求出当前位置能凑出的最大右端点 \(R\)。最后加上合并，查询 \([i+1,R+1]\)（一开始漏了 \(R+1\)）能凑出的最大右端点 \(R'\)。\(i\) 为左端点时，\([i,\max\{R',R\}]\) 都可以作为右端点，直接加入答案。（赛时不会这部分合并，写了区间 DP，把这个做法忘掉，求你了）
【THUSCH2017】大魔法师
4、5、6 操作多了个 \(v\)，就给矩阵多加一列存 \(1\)，想了挺久才明确这个。剩下的就和普通线段树一样了，每个节点存 \([l,r]\) 的矩阵和，再加个懒标记。写了 30 min，想还弄了一会。
【LuoguP4223】期望逆序对
考虑一对数 \(i,j(i<j)\)，交换 \(k\) 次后七种情况 \((A,B)(B,A)(A,C)(C,A)(B,C)(C,B)(C,C)\)。求出 \(7\) 种方案数后，再讨论 \(a_i\) 和 \(a_j\) 的大小关系，计算逆序对的总数。
2.24
【CF24D】Broken robot
转移方程式显然。主要是解方程。对于 \(i\)，只有 \(i-1,i,i+1\) 前会有系数。当消第 \(i\) 元时，只有第 \(i+1\) 行的第 \(i\) 元大于 \(0\)。只用消连续两行即可。一次消元就是 \(O(n)\) 的。
【JLOI2015】装备购买
贪心 + 实数线性基板子。考虑向量第 \(i\) 维大于 \(0\)，如果基中第 \(i\) 维为 \(0\)，就直接把向量 \(x\) 放入；否则和第 \(i\) 维消元，把第 \(i\) 维消为 \(0\)。
【BJWC2011】元素
贪心 + 线性基板子。
【SCOI2016】幸运数字
线性基可以合并，套个倍增就好了 \(O((n+q)\log n\log^2 V)\)。似乎还有 \(O((n+q)\log^2V)\) 的做法，有点像可持久化 Trie（原来我以前写过类似的，CF1100F）。
\(\large\color{red}+\)【CF1726E】Almost Perfect
排列 \(p\) 的逆 \(q\)，\(q_i\) 的值为 \(i\) 在 \(p\) 中的位置。
重要性质：把 \(i\rightarrow p_i\) 看做一条有向边，因为 \(q_{p_i}=i\)，把它看作一条从 \(p_i\rightarrow i\)，是 \(i\rightarrow p_i\) 的反向边，得到当 \(p_x=y\) 时 \(q_y=x\)，反之也成立。设 \(p_i=j\)，得到 \(q_{p_i}=q_{j}=i\) 。
考虑处理条件 \(|p_i-q_i|\le 1\)。尝试把 \(q\) 扔掉，考虑 \(p_j=i\)，得到 \(|p_{p_j}-q_{p_j}|\le 1\)，\(|p_{p_j}-j|\le 1\)。把置换环拉成链，设 \(a_{i+1}=p_{a_i}\)，那么又可以转化题意：\(|a_{i+2}-a_{i}|\le 1\)。对于环中的最小值，应该有 \(i-2\equiv i\) 或 \(i+2\equiv i\) 或 \(i-2\equiv i+2\)，因此环长只可能为 \(1\)、\(2\)、\(4\)。对于大小为 \(4\) 的环，从最小值出发开始构造，\(a_1=i,a_2=j+1,a_3=i+1,a_4=j\) 和 \(a_1=i,a_2=j,a_3=i+1,a_4=j-1\)。
2.25
【SDOI2013】淘金
若干个 \(1\sim 9\) 的数的乘积一定能被 \(1\sim 9\) 内质数的乘积表示。然后就是 \([2,3,5,7]\) 凑出小于等于 \(n\) 的数。这样的数的个数并不多。把它们离散化后就可以作为 DP 的状态了。剩下就是个二元组求第 \(k\) 大的问题。
【BZOJ3329】Xorequ
将题意转化为 \(x \& 3x=x\)。\(3x\) 可以理解为 \(x\) 右移一位再加上 \(x\)。对于每一位考虑，\(3x\&x\) 第 \(i\) 位的值只与 \(i-1\) 位和第 \(i\) 位有关。分讨：1. 第 \(i\) 位为 \(0\)，不管怎样 \(\&\)，都是 \(0\)；2. 第 \(i\) 位为 \(1\)，\(i-1\) 位为 \(0\)，\(3x\) 这一位也为 \(1\)；若第 \(i-1\) 为 \(1\)，则 \(3x\) 第 \(i\) 为 \(0\)，并进位，不合法。即满足 \(x\&3x=x\) 需要任意相邻两位不都为 \(1\)。第一问：数位 DP 第二问：\(f_1=2\)，\(f_2=3\)，\(f_i=f_{i-1}+f_{i-2}\)。
【CQOI2016】手机号码
数位 DP 板子，写了一个小时，吐了！！！
2.26
【CF1512G】Short Task
求 \(\sigma(i)\) 的板子题。首先 \(\sigma(i)\) 是积性函数。
分开讨论：
- \(i\) 是质数： \(\sigma(i)\) = \(i+1\)。
- \(i\) 的不是 \(p\) 的倍数：\(\sigma(i\times p)=\sigma(i)\times (p+1)\)。
- \(i\) 的是 \(p\) 的倍数：\(\sigma(i\times p)=\sigma(i)+(\sigma(i)-\sigma(\frac{i}{p}))\times p\)
【UVA12716】GCD XOR
基础思路：枚举 \(\gcd(a,b)\) 的值，再枚举 \(a\)，通过 \(a\oplus b=\gcd(a,b)\) 求出 \(b\)，最后判断 \(\gcd(a,b)\) 是否等于枚举的值。
非常屌的利用性质：\(a\oplus b\ge a-b\)，\(\gcd(a,b)=\gcd(a,a-b)\le a - b\)，所以 \(a\oplus b=\gcd(a,b)=a-b\)。枚举 \(\gcd(a,b)\)，再枚举 \(a\) 求出 \(b\)，这时候 \(\gcd(a,b)\) 等于枚举的值一定成立，只要判断 \(a\oplus b\) 的值即可。
【CF1717E】Madoka and The Best University
枚举 \(\gcd(a,b)\)，可以再枚举 \(a,b,a-b,a+b\)。枚举 \(a+b\)，求出 \(c\)，\(\operatorname{lcm}(c,\gcd(a,b))\) 的值就可以求了。考虑 \(a+b=S\)，且 \(\gcd(a,b)=g\) 的数的对数。都除以 \(g\) 后，\(\gcd(a',b')=\gcd(a',S'-a')=\gcd(a',S')=1\)，方案数为 \(\varphi(S')\)。
有 n 个点和 m 条连接两个点的双向道路，每条道路有一定的距离。其中，有 n 个点是特别的，经过之后最多可以行驶的距离不能超过 b。
在计划他的 q 次行程，每次给出 xyb，表示出发点是 x，终点是 y，后最多可以行驶的距离不能超过 b，且保证 x,y 都有。他想要知道，是否能从 x 走到 y。
2.27
【CF1789D】Serval and Shift-Shift-Shift
基本的想法：拿某一位上的 \(1\)，不断异或其它不满足的位置。为了尽可能成功，需要找目标状态中的最右或最左的 \(1\)。讨论一下。需要注意在限定 \(n\) 位的时候 bitset 把一个数左移出去了以后，有可能把它右移又回来了，需要处理。
下午打 USACO S，只写出来第一题。
【CF1280C】 Jeremy Bearimy
算贡献，讨论每条边两端点的个数，就可以算出每条边最多被用多少次，最少被用多少次。
【USACO19DEC】Milk Visits G
树上主席树，或离线 DPS 做。
2.28
【CF1793C】Dora and Search
从区间 \([1,n]\) 开始考虑，如果 \(a_l\) 的值等于最大值或最小值，那么 \(l\) 一定得被舍弃。同样处理 \(r\)。\(l,r\) 都不用动时找到区间。
【CF1793D】Moscow Gorillas
直接枚举左端点找右端点不好做。计算当 \(\operatorname{MEX}\) 取值为 \(x\) 时，在 \(a\) 种能取到值的区间，在 \(b\) 中能取到值的区间。当 \(x>1\) 时，对应的区间一定形似：左端点在 \([l_1,r_1]\) 中，右端点在 \([l_2,r_2]\) 中，就可以计算了。
【CF1528C】Trees of Tranquillity
非常重要的性质：以 \(x\) 为根的子树对应的 dfs 序上的区间只要包含关系。因此可以直接在第一棵树上 dfs，同时通过性质贪心地选择节点。
【UVA1642】Magical GCD
固定左端点，区间 \([l,r]\) 的 \(\gcd\) 取值只有 \(O(\log n)\) 种。
3.1
【省选联考2021】宝石
因为 \(P\) 互不相同，可以直接设状态 \(f(x)\) 表示匹配到了 \(x\)。然后向上倍增，向下二分答案 + 倍增。
【CF1728E】Red-Black Pepper
复习一下结论 \(ax+by=n\) 的通解：
\(\begin{cases}x=x'+k\dfrac{b}{\gcd(a,b)}\\y=y'-k\dfrac{a}{\gcd(a,b)}\end{cases}\)
\(\begin{cases}ax=ax'+k\operatorname{lcm}(a,b)\\by=by'-k\operatorname{lcm}(a,b)\end{cases}\)
【SCOI2014】方伯伯的商场之旅
直接求最优位置不好求，计算当位置改变时的代价的变化。因为代价显然先变小后变大，贪心地，直取代价变小的变化量，用数位 DP 求。
3.2
【CF1790G】Tokens on Graph
Ad-hoc 题？每次移动一个 token 到 bonus 只能移动其它 token。那么必须存在一条从某个 token 到 1 的路径且路径上的每个点都是 bonus。选择最短的一定最优，再考虑其它 token 的总贡献：两个连在一起的 bonus，贡献无数步，单独的 bonus，贡献 1 步（前提是有 token 能走到）。因为最后一步不需要 bonus，总贡献大于等于 d - 1 即可。
【CSP-S2019】树的重心
对于一个大小为 \(n\) 的树与任意一个树中结点 \(x\)，称 \(x\) 是该树的重心当且仅当在树中删去 \(x\) 及与它关联的边后，分裂出的所有子树的大小均不超过 \(\lfloor\dfrac{n}{2}\rfloor\)。对于包含至少一个结点的树，它的重心只可能有 1 或 2 个。
两种做法：当树根不是重心时，重心一定在根出发的重链上；算贡献，计算每个点做为重心的次数。选择原树的重心作为根，这样点 x 作为重心时，隔断的边一定不在 x 的子树内。判断重心：\(\max\{s_y\}\le \lfloor\dfrac{n}{2}\rfloor\)。
【CF1718C】Tonya and Burenka-179
只用考虑质因数。一个环长是一个合数，则可以划分为若干个环长是其因数的环，平均数大于等于原来的环，更优。因此只用考虑环长为质因数的环，设环长为 p，则有 n / p 个环。
3.3
【CF1768F】Wonderful jump
3.4
南科大校赛。阳光普照奖获得者之一。
3.5
\(\operatorname{cat}(n)=\dfrac{C_{2n}^{n}}{n+1}\)
卡特兰数：长度为 n 的合法括号序列数量，点数为 n 的二叉树数量
【CF1787D】Game on Axis
首先，这是个基环树森林 + 一颗树（把 0 作为树根，结束游戏的标志）（这时候就不要老想着置换的那一套东西了，这比置换要复杂些）。大致分两种情况讨论：不改变时 1 能结束游戏，不改变时 1 不能结束游戏。第一个满足 1 到 0 的路径上的点不往子树中连即可，第二个需要 1 能够到达的点中的一个点连向不能够走到环上的点。
【CF1787E】The Harmonization of XOR
猜出来了。首先判一下总异或和，\(1\sim n\) 的异或和应该等于 \(k\) 个 \(x\) 的异或和。把题意转化：恰好 \(k\) 个 \(\rightarrow\) 大于等于 \(k\) 个，可以选出来 \(k-1\) 个，剩下的全部并为第 \(k\) 个集合。贪心地枚举 \(1\sim n\)，选出 \(k-1\) 对 \(i\) 和 \(x\oplus i\)。证明正确性：设 \(x\) 的最高位为第 \(p\) 位，\(1\sim n\) 中第 \(p\) 位为 \(1\) 的数的个数为 \(t\)，能够得到的集合数量最多为 \(t\) 个。考虑一个在 1 - n 中第 \(p\) 位为 \(1\) 的数，它异或上 x 一定变小，并且不同的数异或上 x 一定不同，所以两两匹配最优且能够得到 t 个集合。
【CF1787G】Colorful Tree Again
一开始不会判颜色 c 是否一开始是合法的。实际上就是判若干条边能否组成一条链！一条链就判是否恰好有两个点的度数为 1 即可！
操作破坏一个点会影响的颜色分成两类，一种是 LCA 为该点的颜色，其次是连接该点的父亲和该点的颜色。稍微需要分讨一下，最后用 set 维护。
3.6
【HEOI2013】Segment
贺了个比较容易理解的李超线段树板子。李超线段树上的每个节点维护在 mid 处的最大值。设 u 表示原来存在该节点的线段，v 表示新加入的线段。分别比较两个线段在 l,r,mid 的值。由于最多进入一边，所以复杂度是 \(O(\log n)\)，因为是区间修改，修改复杂度为 \(O(\log ^2n)\)。
ldb calc(int id,int x){
return k[id] * x + b[id];
}
bool cmp(int u,int v,int x){//u < v
return calc(u,x) < calc(v,x) || calc(u,x) == calc(v,x) && v < u;
}
void upd(int id,int l,int r,int v){
int &u = Mx[id];
if(cmp(u,v,mid))swap(u,v);
if(cmp(u,v,l))upd(ls,l,mid,v);
if(cmp(u,v,r))upd(rs,mid + 1,r,v);
}
void update(int id,int l,int r,int x,int y,int v){
if(x <= l && r <= y){
upd(id,l,r,v);
return;
}
if(x <= mid)update(ls,l,mid,x,y,v);
if(y > mid)update(rs,mid + 1,r,x,y,v);
}
int query(int id,int l,int r,int x){
int res = Mx[id];
if(l == r)return res;
if(x <= mid){
int Ls = query(ls,l,mid,x);
if(cmp(res,Ls,x))res = Ls;
}
else{
int Rs = query(rs,mid + 1,r,x);
if(cmp(res,Rs,x))res = Rs;
}
return res;
}
【JSOI2008】Blue Mary 开公司
李超线段树板子。全局修改，会简单一些。
【CF915E】Physical Education Lessons
原来 ODT 就是指用 set 维护很多段区间然后复杂度是均摊的算法，在 NFLS 见过。直接用动态开点线段树碾了过去。998 ms。
【CF803G】Periodic RMQ Problem
动态开点线段树板子。写动态开点线段树要注意 pushup 时 ls[id] 或 rs[id] 不存在的情况。
【LuoguP6047】丝之割
当一条琴弦 \([u,v]\) 被令一条琴弦 \([i,j]\) 包含，即 \(i\le u\and v\le j\)，那它就没用了。去掉没用的琴弦后，一次操作消除的琴弦就是连续的了，就可以 DP 了。最后用李超线段树或斜率优化。
尝试过的题目--
【CEOI2017】Building Bridges
用李超线段树优化 DP。
【LuoguP5494】[模板]线段树分裂
按区间分裂的线段树分裂
【POI2010】PIL-Pilots
简单的单调队列 + 双指针
【POI2011】ROT-Tree Rotations
交换一个点祖先的左右子树不影响这个点左右子树的相对关系，所以贪心地交换每个点的左右子树，用线段树合并计算交换和不交换的逆序对个数并维护。
3.7
【CF955C】Sad powers
k >= 3，暴力，然后排序并去重。多组询问，二分求 k 大于等于 3 的数的个数。一个区间 [L,R] 内的完全平方数个数为 \(\lfloor\sqrt R\rfloor-\lfloor\sqrt{L-1}\rfloor\)。
【HEOI2016/TJOI2016】排序
线段树分裂用来拍序。
【CF558E】A Simple Task
线段树分裂用来拍序。
3.8
3.9
3.10
可重点 DAG 最小路径覆盖：Floyd 求出传递闭包后跑二分图最大匹配。
3.11 3.12
GDKOI
3.13
学习 cdq 分治。
3.14
【SDOI2011】拦截导弹
首先要明确一点：最长上升子序列方案数是指数级的。
DP 显然，用 CDQ 分治优化。先做完 \([l,mid]\)，求出 [mid + 1,r]，再递归入 [mid + 1,r]。处理 [l,r] 时要先按第一维排序，因为它作为右半部分时按第二维排了序。
3.15
【国家集训队】数颜色 / 维护队列
CDQ 分治做法。维护 (t,x,y,z)，每次单点修改转化为删除一个点 (t,x,y,-1)，和加入一个点 (t‘,x’,y‘,1)。用 set 维护单点修改时 pre 的变化。然后对于询问就是三维偏序问题：\(t'\le t,x<l,l\le y \le r\)，时间复杂度为 \(O(n\log ^ 2n)\)，优于 \(O(n^{\frac{5}{3}})\) 的分块和带修莫队。
【Ynoi2016】镜中的昆虫
想 + 写 1h，调试 2.5 h。操他妈 Mike。
同上题不同，变为区间修改。\(n\) 个元素，m 次修改后 pre 值改变的数的总量为 O(n+m)。因为修改一段连续段后，第一个需要特殊处理，其余的都为 i - 1。因此跨过其它区间的端点的总和不会超过 m，可以通过 ODT 维护，顺便证明了复杂度。有很多细节。把所有可能 pre 值变化的 i 都暴力维护即可，避免代码过于复杂。剩下的 CDQ 部分和上题无异。
3.16
【USACO20FEB】Swapity Swapity Swap S
考虑位置 \(i\) 经过 m 次操作后的成为了 \(a_i\)，对于 k 次这样的操作，每次都是将位置 i 的数移动到 a_i，也就是就是在置换环上移动 k 步。预处理 a 后，就可以 O(n) 求解了。
【CF508E】Arthur and Brackets
贪心。匹配第 i - 1 个左括号的右括号一定在匹配第 i 个左括号的右括号的后面。把左括号按顺序压入栈中，若栈顶未匹配，则栈内的括号无法匹配。考虑匹配当前栈顶括号，若当前括号串位置不满足 [L,R] 的条件则只能 skip，否则贪心地将它匹配，一定最优。证明：考虑满足条件仍不匹配的作用：放入新的左括号，多匹配一个，一定形如 ...(...()...)...，可以将新的括号放到外面匹配 ...(......)()... 同时不影响 i 的匹配，更优。
3.17
【CF1303F】Number of Components
连通情况从 A 变为 B 连通块变化数量为 x，B 变为 A 连通块变化数量为 -x。
【NOIP2018 提高组】保卫王国
\(f(i,0/1)\) 以 i 为根的子树，i 选/不选的最小代价。强制选/不选，其实就是将另一个状态强制变为 INF。\(f\) 值更改的点只有 \(a\)，\(b\) 两点到根的路径上的点。考虑点 \(x\) 怎么转移到点 \(fa_x\)，设 \(g(x,0/1)\) 表示扣掉 x 为根的子树，fa_x 选或不选的最小代价。\(\begin{bmatrix}f(x,0),f(x,1)\end{bmatrix}\times \begin{bmatrix}+\infty&g(x,1)\\g(x,0)&g(x,1)\end{bmatrix}\) ，倍增优化即可。同时维护 \(h(x,0/1)\) 表示所有点中扣掉除 \(x\) 以外，以 \(x\) 为根的子树，\(x\) 选或不选的最小代价。将 \(a,b\) 跳到 LCA 处，通过 \(h\) 计算总代价。
【NOIP2018 提高组】 旅行 加强版
当 m = n 时，暴力就是枚举断边，然后 O(n) dfs。考虑贪心地找到断边，从 1 出发，维护到达了点 x，选择断掉环上的下一条边后回溯回去到达的第一个点 y。首先，x 出发到达的环上的下一个点一定得是 x 出点中的最大值，然后再跟 y 比较大小，如果大于它就回溯，否则继续在环上走。要特判回溯后不要再回溯（调了一个小时）。
3.18
【CF1513D】GCD and MST
最小生成树，通过 Kruskal 思考，从小到大加入边。当考虑 \(a_i\)，满足条件需要区间内的数都是 \(a_i\) 的倍数。l,r 向两端扩展，区间 [l,r] 内的点显然都可以通过连接 [j,i] 的边并为一个连通块。再放入一个数 \(a_x\)，若它被其它 \(a_i\) 扫过，一定满足 \(a_x\) 是 \(a_i\) 的倍数，因为 \(a_x\ge a_i\) ，所以满足 \(a_x\) 比满足 \(a_i\) 更苛刻，\(l_x\) 一定大于等于 \(l_i\)，\(r_x\) 一定小于等于 \(r_i\)，不用再考虑。若 \(l_x\) 或 \(r_x\)，扫到其它被扫过的位置，合并两个连通块，同时停止即可（同上，需满足的条件更苛刻）。这一部分处理是线性的。
【省选联考 2021 A/B 卷】图函数
【LuoguP5960】[模板]差分约束算法
对于最短路上的一条边 \((x,y,z)\)，满足 \(d_y\le d_x + z\)，形似题目要求的 \(x_{c_i}\le x_{c_i'}+y\)。对于 \(x_{i}=y\) 的条件，可以表示为 \(x_i\ge y\) 且 \(x_i\le y\)。建超级源点 \(x_0\)，\(x_0\le x_i-y\) 且 \(x_i\le x_0+y\)。
【LuoguP4926】[1007]倍杀测量者
对于第一种 Flag，需满足 \(S_A\ge (k-T)S_B\)，第二种需满足 \(S_A > \dfrac{S_B}{k+T}\)。有人女装即存在不等式不成立，二分答案 + 差分约束判定。技巧：乘积，通过 \(\log\)，转成加法。
【省选联考 2021 A 卷】矩阵游戏
首先随意构造出一组 \(a\)。巧妙地构造：对第一行 \(+c_1-c_1+c_1-c_1\)，对第二行 \(-c_2+c_2-c_2+c_2\)，对第一列 \(-d_1+d_1-d_1+d_1\)，对第二列 \(+d_2-d_2+d_2-d_2\)，仍然满足条件。这样对于行列奇偶相同的格子需满足 \(0\le c_i-d_j+a_{i,j}\le 10^6\)，不同满足 \(0\le -c_i+d_j+a_{i,j}\le 10^6\)。就是差分约束的形式。
【CF1806A】Walking Master
\(y\) 只能增加，先考虑。如果 b > d，一定无解。先将 b 移动成为 d，a 变为了 a + d - b，再讨论即可。
【CF1806B】Mex Master
使 MEX 最小，相邻两数和尽量不出现 0。0 正 0 正 0，0 的数量小于等于 \(\lceil\dfrac{n}{2}\rceil\)，MEX 能取到 0；注意大于 \(\lceil\dfrac{n}{2}\rceil\) 时不一定能取到 \(1\)，还需要再讨论，看能否不出现相邻的 \(1\) 和 \(0\)（赛时因为这个挂了一发）。
【CF1806C】Sequence Master
任意一个长度为 \(n\) 的子序列的和等于其它 n 个数的积。条件很苛刻，估计一下可行的方案不会多。dfs 打表发现 n > 1 时，只有全为 0 的情况，当 n 为偶数时，有 (2n - 1) 个数为 -1，一个数为 n，分别计算最小的答案即可。
【CF1806E】Tree Master \(\color{red}\text{FST}\)
非常轻松地 Hack 我的做法。造两条链，链低端两个菊花，可以询问的点对是 \(O(n^2)\) 的，暴力跳的复杂度是 \(O(n)\) 的。错误做法记忆化方法对复杂度无优化作用。
3.19
【CF1270G】Subset with Zero Sum
很神的题，转化式子：\(i-n\le a_i \le i-1\)，\(1\le i - a_i\le n\)，\(i\) 向 \(i-a_i\) 连边，构成内向基环树森林。对于基环树上的一个环：有 \(\sum i=\sum i-a_i\)，得到 \(\sum a_i=0\)。
【NOI Online #1 提高组】序列
操作 2 可以使一个连通块在总和不变的前提下任意变换。再观察操作 1，可以通过 +1 +1/-1 -1 移动，黑白间隔染色后可以同颜色内任意变换。如果不能黑白间隔染色，一个连通块中存在奇环（不是二分图），则可以在环上绕，得到想要的颜色，即只要 \(\sum b\) 与 \(\sum a\) 的差值是偶数即可，否则修改一定一黑一白，需满足黑点需要的差值与白点相同。
【CF1537F】Figure Fixing
双倍经验同上，没有 2 操作。
3.20
【CF1566A】Median Maximization
设中位数为 \(x\)，非负整数数列的总和最小为 \((n-\lceil\dfrac{n}{2}\rceil+1)x\)，就是求该式小于等于 s 的最大整数解。
【CF1566B】MIN-MEX Cut
0 1 分在一起为 2，大于单独分 0 和 1。所以最优情况是分成若干段连续的极长的 0 和 1 或不分段。
【CF1566C】MAX-MEX Cut
两行不同一定单独分组，贡献为 2。两行相同，如果是 1 考虑和 0 合并。两列 1 和一列 1 没有区别，单独分成两列 0 优于合并两列 0，只用考虑相邻两列不同的情况，贡献为 2。
【CF1566D1】Seating Arrangements（easy version）
二维偏序，求比 i 早坐的人且坐在 i 前面的人的个数，m 很小，暴力即可。
【CF1566D2】Seating Arrangements（hard version）
其实直接贪心就好了。相同值的人的位置是连续的。完整的行安排显然。第一行是后缀，越早进入越好，碰到的人越少。最后一行是前缀，最晚进入越好，少影响其他人，因此按照时间顺序，从前往后排就好了，n、m 不大，直接模拟就好了。
【CF1566E】Buds Re-hanging
从下往上把所有能成为 bud 的部分都扣下来。然后依次接在叶子下面，没有 bud 了就把叶子计入答案。
【LuoguP6154】游走
第一想法是直接枚举每条边算贡献，算经过这条边的路径总数。其实直接 DP 也可以。
【CF1566F】Points Movement
去除冗余信息：已经被覆盖的线段，包含其它线段的线段。然后 DP。设 \(f_i,0\) 表示点 \(i\) 最终向左的最小代价，\(f_{i,1}\) 表示点 \(i\) 向左后回到 \(i\) 的最小代价。然后利用双指针转移。
【LuoguP2087】GTY的人类基因组计划2
用 xor Hash 判断某一个集合是否出现过。然后是区间做实验，区间清空，写了个势能线段树，直接用 set 暴力删复杂度也是对的。
【CF1806E】Tree Master
【CSP-S2019】划分
3.21
【CF1286B】Numbers on Tree
【CF1303E】Erase Subsequences
【CF1305F】Kuroni and the Punishment
【CF1307F】Cow and Vacation
【SP19786】GGD - Mr Toothless and His GCD Operation
【CF1804E】Routing
3.22
【CF1606A】
【CF1606B】
【CF1606C】
【CF1606D】
【CF1606E】
【CF1606F】
【CSP-S2019 江西】多叉堆
3.23
【USACO19DEC】Livestock Lineup B
【CF1304E】1-Trees and Queries
转化题意：找到一条从 x 到 y 的路径满足长度 <= k 且与 k 模 2 同余。新增边 (u,v) 后，从 x 到 y 的路径只有两种，原树上直接从 x -> y，经过新增的边 (u,v)（只有经过 (u,v)，原来路径长度的奇偶性才可能改变）。全部计算、考虑即可。
【CF1296E2】String Coloring (hard version)
【CF1307E】Cow and Treats
【CF559C】Gerald and Giant Chess
【UVA1638】杆子的排列 Pole Arrangement
【CF1761D】Carry Bit
【AcWing96】奇怪的汉诺塔
【AcWing307】连通图
3.24
【CF1594A】
【CF1594B】
【CF1594C】
【CF1594D】
【CF1594E1】
【CF1594E2】
【CF1594F】
3.25
启发式合并并查集：确实可以任意顺序删掉并查集上的一条边。
维护图：不能维护连接两个相同集合的边。
维护树：并查集上一条边 (u,v) 和它对应到原树上的边 (x,y)，并查集 (u,v) 割开得到的连通块并不一定对应到原树割开 (x,y) 得到的连通块（因为并查集直接将两个连通块的根连边）。
因此，并查集想要分裂只有两种可能：可持久化和撤销上一次操作。不要再想有的没的了。
【CF1681F】Unique Occurrences
算贡献。每种颜色 c 的贡献转为删掉颜色 c 的边，一条边的贡献就为连接两端的连通块大小之积。然后就可以直接分治做了。分治处理 [l,mid] 时把在 [mid + 1,r] 中的边加入。
【CF1442D】Sum
注意序列的性质：非负、递增。结论：最多只有一个序列只选了一部分，其余全选或不选。证明：考虑存在两个序列只选了一部分，设当前 \(a_i\ge b_j\)，因为 \(a_{i+1}\ge a_i\ge b_j\) 所以可以扔掉 \(b_j\)，改为选 \(a_{i+1}\) 更优，直到 \(a\) 全选或 \(b\) 不选，即为结论的两种情况。然后类似上题分治。找到只选一部分的序列，其余 0/1 背包处理。
【CF1594F】Ideal Farm
读错题了。重复一遍题意：给定 n、s、k 问是否对于所有的分配方式 \(\sum\limits_{i=1}^{n}a_i=s\)，\(a_i>0\)，都存在区间 \([l,r]\) 使得 \(\sum\limits_{i=l}^{r}a_i=k\)。数学题 + 构造题。将题意通过前缀和转换：给定 \(n+1\) 个数，其中 \(s_0=0\)，其余数满足 \(s_i<s_{i+1}\)，\(s_i\le s\)，求使得不存在 \(s_{j}-s_{i}=k\) 的 \(s\) 的最小值。构造 \([0,k-1],[2k,3k-1]\dots[2xk,2x+k-1]\)，可以 \(O(1)\) 计算 s 的最小值，与题目给定的 s 比较即可。
【LuoguP5787】二分图/[模板]线段树分治
【FJOI2015】火星商店问题
3.26
Codeforces 使用的 Elo Rating 算法来计算用户的 Rating，其计算公式如下：
\(R_{new} = R_{old} + K \times (S - E)\)
其中，\(R_{old}\) 为用户当前的 Rating，\(R_{new}\) 为用户预测的 Rating，\(K\) 为系数，\(S\) 为用户的得分，\(E\) 为预期得分。
预期得分 \(E\) 的计算公式为：
\(E = \frac{1}{1 + 10^{\frac{R_{opp} - R_{self}}{400}}}\)
其中，\(R_{opp}\) 为对手的 Rating，\(R_{self}\) 为自己的 Rating。
系数 \(K\) 的计算公式为：
\(K = \begin{cases} 50, & \mbox{if }N_{contests} \leq 10 \ 100, & \mbox{if }10 < N_{contests} \leq 20 \ 150, & \mbox{if }20 < N_{contests} \leq 30 \ 200, & \mbox{if }30 < N_{contests} \leq 40 \ 250, & \mbox{if }N_{contests} > 40 \end{cases}\)
其中，\(N_{contests}\) 为用户参加比赛的场次数。
【CF938G】Shortest Path Queries
P4151 [WC2011] 最大异或和路径 + 线段树分治。再次重复结论： x 到 y 的 xor 路径值被一颗生产树上的 d(x,y) 和图中若干个图中的环表示。线段树分治，预处理每条边出现的时间段，通过并查集找环并扔入线性基。
【CF678F】Lena and Queries
同理，处理出每对 \((k,b)\)，放到线段树上，通过李超线段树维护。李超线段树不能撤销，同时处理的是 max 这样的可以 O(1) 合并的信息，所以类似对线段树单点查询，但对链上每个点都求一次 max。感觉是树套数 + 标记永久化，而不算线段树分治。
【CTSC2016】时空旅行
与上题类似。通过 dfs 序拍平即可。注意一点，点 x 被删除可以是在多个不同的子树中被删除，需要用 vector 全部存下来，统一维护。
3.27
【USACO20DEC】Stuck in a Rut S
【LuoguP7889】Eert Tuc Knil
【LuoguP7888】Distinct Subsequences
【CF1192B】Dynamic Diameter
欧拉序。树上两点路径公式：\(d_a+d_b-2d_{\operatorname{LCA(a,b)}}\)。在欧拉序中，a、b 两点的 LCA 一定在它们之间并且 \(d\) 值最小。在欧拉序上建线段树，维护 \(d\) 的最大值，\(d\) 的最小值，\(d_a-2d_{\operatorname{LCA(a,b)}}\) 的最大值，\(d_b-2d_{\operatorname{LCA(a,b)}}\) 的最大值和 \(d_a+d_b-2d_{\operatorname{LCA(a,b)}}\) 的最大值。修改边权变为区间修改。lazytag 可以 O(1) 修改节点的权值，因为相同类型的值的变化量相同。
【AcWing355】异象石
树上的连通边集的最小总长度：将所有点按 dfn 排序，\(w=\dfrac{1}{2}\sum\limits_{i=0}^{n-1}\operatorname{dis}(a_i,a_{(i+1)\bmod n})\)。在本题中结合 set 使用。
struct cmp{
bool operator () (int x,int y)const{
return dfn[x] < dfn[y];
}
};
set<int,cmp> s;
set<int,cmp>::iterator it;
void Ins(int x){
it = s.insert(x).fi;
int a = it == s.begin() ? *s.rbegin() : *prev(it);
int b = it == (--s.end()) ? *s.begin() : *next(it);
ans += ds(a,x) + ds(b,x) - ds(a,b);
}
void Del(int x){
it = s.find(x);
int a = it == s.begin() ? *s.rbegin() : *prev(it);
int b = it == (--s.end()) ? *s.begin() : *next(it);
ans += ds(a,b) - ds(a,x) - ds(b,x);
s.erase(it);
}
3.28
板子复习：
【SDOI2012】任务安排（P5785）
李超线段树求形如 \(kx+b\) 的极值，优化 DP。李超线段树空间与插入线段总数线性相关。
【NOI2015】软件包管理器（P2146）
重链剖分板子。
3.29
【CF741D】Arpa’s letter-marked tree and Mehrdad’s Dokhtar-kosh paths
DSU on tree 板子。这个题只考虑 22 种颜色，注意读题。注意将桶清成负无穷。
【CF1798A】Showstopper （6min）
写的有点慢，可能是因为找 chatgpt 翻译和一开始想错了推倒重写了。不妨让 \(a_n=\min\{a_n,b_n\}\)，\(b_n=\max\{a_n,b_n\}\)。要使 a 中所有数都小于等于 \(a_n\)，那就让 \(a_i=\min\{a_i,b_i\}\)，\(b_i=\max\{a_i,b_i\}\) 就好了。
【CF1798B】Three Sevens（18min）
一开始读错题了。倒序来做。随意找到一个未在 \([i+1,m]\) 出现的数，把它作为 \(p_i\) 即可，结束后将第 \(i\) 天出现的所有数标记。证明也很简单，找到的数不可能更早获奖，因为它这一轮会被标记，再往前也用不了，只有在这一轮才能发挥价值。
【CF1798C】Candy Store（36min）
4.9
写 Dinic 求二分图最大匹配，写 + 调花了 25 min。
4.30
莫比乌斯反演
【POI2007】ZAP-Queries（LuoguP3455）
【HAOI2011】Problem b（LuoguP2522）
GCD（LuoguP2568）
YY 的 GCD（LuoguP2257）
【CF1780F】Three Chairs
5.2
圆方树
5.3
【P4630】[APIO2018] 铁人两项
【P4334】[COI2007] Policija
5.6
\(f_{i,j}=\max\{f_{k,j}\}\)
5.14
计算几何。
【CF487E】Tourists（未写代码）
【P2742】[模板] 二维凸包
【P9119】[春季测试2023] 圣诞树
7.4
尝试证明去重对求最长严格上升子序列是无用的。
错误证明：....x a b c d x.....，假设前面选的长度相同，选取前一个 x 后，剩下更长序列的可能性大于选后一个 x，只保留最前面的数即可。
初，我认为我错误的原因是证明过程中暗含条件一定选取了 x，但后一想发现该条件存在是无误的且应该存在，实际错误在于我没有考虑 a b c d 对选择后一个 x 的影响，因此有一个简单的 Hack：5 1 2 3 4 5，不选择第一个 5。
7.5
全国青少年信息学奥林匹克竞赛
National Olympiad in Informatics
【A】文件路径（P6843）
题意：给定一棵外向树，边有边权。对于每个叶子，询问在添加一条长为 \(s\) 的有向边后，能否得到一条从根到该点长恰好为 \(k\) 的路径。
【B】分组（P5861）
题意：
【C】情商修炼手册（7.12）
题意：大小为 \(n\) 的有根树森林，各节点初始权值为 \(0\)，每个点有限制 \((l_i,r_i)\)，一次操作定义为选择一棵子树，给子树内部所有节点权值加上任意整数，求最少操作次数使每个点的点权满足 \(l_i\le a_i\le r_i\)。数据范围：\(1\le n\le 5\times 10^5,-10^9\le l_i\le r_i\le 10^9\)。
7.10
【A】好朋友（P5882）
【B】文本编辑器（P4732）
【C】颜色
题意：大小为 \(n\) 的树，边有边权（\(\in [1,n]\)）。两个操作，将第 \(x\) 条边修改为 \(y\)，询问从 \(x\) 到 \(y\) 的路径上是否有边权相同。数据范围：\(1\le n,q \le 10^5\)。
7.11
【A】学物理（LOJ6490）
【B】幻想乡战略游戏（P3345）
【C】原神怎么你了？（CF251E）
7.12
【P1253】扶苏的问题
【LOJ115】无源汇有上下界可行流
【LOJ116】有源汇有上下界最大流
【P5192】[模板] 有源汇上下界最大流
【CF808F】Card Game
7.13
【A】黑客（P4734）
【B】拔河（P4733）
【C】散步（CF1322E）
7.14
【CF1322E】Median Mountain Range
【P9359】Cells Coloring
7.15
【P3177】[HAOI2015] 树上染色
【UVA1650】数字串 Number String
【P2467】[SDOI2010] 地精部落
【SP6779】GSS7 - Can you answer these queries VII
7.16
【P5999】[CEOI2016] kangaroo
【P3647】[APIO2014] 连珠线
【P4590】[TJOI2018] 游园会
7.17
【A】水壶（LOJ2876）
【B】日程管理（P4511）
【C】雪原
题意：对于 \(1\le i\le n\) 求出点度数强制为 \(1\) 的情况下最小生成树的最大边的权值。
7.18
杭电多校
7.19
【A】设计路线（P4201）
【B】袋熊（P5897）
【C】Vim（P6758）
7.20
【P5897】[IOI2013] wombats
7.21
【A】Zbox loves stack
【B】序列（P6740）
【C】静态仙人掌（UOJ158）
7.22
【A】鱼（P4684）
【B】梦想封印
【C】Travel
7.23
【P6740】[BalticOI2014 Day1] Sequence
【UOJ158】静态仙人掌
7.24
【P6758】[BalticOI2013] Vim
【P4511】[CTSC2015] 日程管理
7.25
【NFLSOJ】雪原
重新手写堆
7.26
7.30
【P9168】[省选联考 2023] 人员调度
【P8095】[USACO22JAN] Cereal 2 S
7.31
‘【CF1253F】Cheap Robot
【CF196E】Opening Portals
【P5688】[CSP-S2019 江西] 散步
【P5686】[CSP-S2019 江西] 和积和
【P5687】[CSP-S2019 江西] 网格图
8.1
【CF997E】Good Subsegments
多校 R5
8.2
【CF603E】Pastoral Oddities
【CF526E】Transmitting Levels
【CF319E】Ping-Pong
8.3
【CF464E】 The Classic Problem
else return qry(ls[id],l,mid,x,y) * pw[min(r,y) - mid] + qry(rs[id],mid + 1,r,x,y);
取 min 不要忘了！！！
多校 R6
8.4
NOIP2023训练赛1
【A】四子棋
在双人对弈游戏"四子棋"中,棋盘为4×4大小,双方棋子以x,o表示,x先行.
双方轮流在棋盘中空的位置下一子.
当一方下子后,达成某一行,或某一列,或某一对角线上都是己方的4个棋子,则获胜.
若所有位置下完,无人获胜,则为平局.
华哥经常和女友下棋,他需要根据场合来把控棋局走向.
有时需要获胜以显示自己的智商,有时需要失败以哄女友开心,有时需要平局来拖时间.
现在他正面对一个残局,请判断他是否一定能达成自己的目标.
记忆化搜索即可。
【B】悄悄话
题意：给 \(n\) 出个字符串 \(s_i\)，每个字符串有权值 \(v_i\)，现在要从这个字符串中选出若干个，按原顺序排列后，满足每个串被下一个串包含，并使其权值和最大，求最大权值和。
AC 自动机模板。将 \(s\) 扔到 AC 自动机上游走，到达的每一个节点的 \(\text{fail}\) 树上的祖先都是包含的串，用线段树维护即可。
【C】排列
题意：给定 \(m\) 个长度为 \(n\) 的排列。定义 \(f(l,r)\) 为考虑下标在 \([l,r]\) 之间的排列，每次取出任意一个排列最前面的数，使得不存在任意一个数全部连续出现的操作序列个数。排列在 \(n!\) 种排列中等概率随机。
\(O(m^2n^2)\) 枚举区间 \([l,r]\) 暴力计算，类似 CF559C Gerald and Giant Chess ，只不过变成 \(m\) 维的了。因为排列随机，设两个数 \(x,y\)，每当排列数增加 \(1\) 时，\(x\) 有 \(\dfrac{1}{2}\) 的概率不能在 \(y\) 前面，当排列个数为 \(p\) 时，有 \((\dfrac{1}{2})^p\) 的概率能从 \(x\) 转移到 \(y\)。因此维护能在前面的值，将不能转移的值踢去优化复杂度即可。
【D】树
题意：动态加叶子，动态询问求以 \(x\) 为根的子树的同构树的数量。
8.5
NOIP2023训练赛2
【A】糗大了
题意：动态删点，求删完点后所有连通块中点权和的最大值。
时光倒流 典题。
【B】快哭了
题意：定义 \(f(A)\)，\(A\) 为矩阵，\(f(A)_{i,j}=A_{i,j}\oplus A_{i+1,j}\oplus A_{i,j+1}\oplus A_{i+1,j+1}\)。多组询问，求 \((f(A)^k)_{0,0}\)。
单独考虑 \(A_{i,j}\) 对 \(A_{0,0}\) 的贡献。每次可以选择 \(i+1\) 或 \(j+1\) 或不动，因此贡献总次数为 \(\binom{k}{i}\binom{k}{j}\)。用 Lucas 定理 \(\binom{k}{i}=\binom{\lfloor k/2\rfloor}{\lfloor i/2\rfloor}\binom{k \bmod 2}{i\bmod 2}\bmod 2\)，得到结论 \((i|j) \&k=(i|j)\) 时 \(a_{i,j}\) 有贡献。
【C】色
题意：给定 \(n\) 条线段，将 \(n\) 条线段划分不超过 \(m\) 个集合，定义一个集合的权值为集合中所有线段的交的长度，求集合权值和的最大值。
当答案中有交集为空的集合时，选择前 \(m-1\) 长的线段单独一组，其余线段放入空集中即可。当答案中无交集为空的集合时，先将包含其他区间的线段去除，它们只有两种情况：单独一段，或放入包含线段的集合（相当于不用；如果相交则保留较长舍去较短的更优）。直接 DP 即可，此时交集为空的集合一定不优，\(l,r\) 都单调，取值是可算的，直接用前缀 \(\max\) 优化转移即可。
【D】发怒
题意：给定一棵大小为 \(n\) 的树，每个点有点权 \(a_i\)，求有多少个连通子集满足子集内所有点的点权积不超过 \(m\)。
乘积，设连通块乘积为 \(x\)，将 \(\lfloor \frac{m}{x}\rfloor\)，放入 DP 状态，只有 \(\sqrt m\) 中状态。若树形背包，该状态无法合并背包，转成 加单点 和 点分治优化。
\(\lfloor\dfrac{m}{jk}\rfloor=\lfloor{\dfrac{\lfloor\frac{m}{j}\rfloor}{k}}\rfloor\)
8.6
复习点分治。
8.7
NOIP2023训练赛3
【A】最小标号
强制在线多组询问 \((u,v)\)，求不在 \((u,v)\) 上的点的编号的最小值。
若 \((u,v)\) 不过 \(1\)，答案为 \(1\)。再讨论经过 \(1\) 的情况：简单、套路的树形 DP 处理。复杂度线性。
【B】地图
边仙人掌，点有点权。多次询问 \(x\) 若删去 \(x\) 到 \(1\) 的简单路经上的边后，小于等于 \(y\) 且出现次数为奇数或偶数（询问给定）的数的个数。
圆方树 + （莫队 + 树状数组）/ 线段树分治 / dsu on tree。
\(O(n\sqrt n\log n)\)，\(O(n\log n)\)，\(O(n\log ^2 n)\)。
【C】音乐
阿巴阿巴。
【D】字符串重排