做题1
2022.2.7
CF1634E
题意：
给定一些数组，长度都为偶数，需要将每个数组的元素划分到两个可重集合里，要求两个集合相同，问方案或输出无解，\(n,m=10^5\)。
思考：
考虑每个数组单独划分，不太行，所以不能一个数组一个数组的考虑，显然有解的必要条件是每个数字个数为偶数。所以一个数字一个数字的考虑，其实也不太行，因为这和刚刚那种方法是本质上一样的。
注意到也保证每个数组长度为偶数（这不是废话吗），都是偶数，不由得让我们想到欧拉回路，所以尝试建图，每个不同的数和数组视为一个点，由数组向数连边，数组内存在一个数，就由数组向这个数连一条边，现在需要给图定向为一张欧拉图，我们将数组向数连的边是为将这个数分到第一个集合，反之则为第二个，构造欧拉图即可。
实现上的问题：
存边用 set 存，不然 TLE 没商量。
图不一定联通，所以一定要多起点。
20220209
22020208考试 T1
题意：
定义矩阵 \(Mat_n\)
- \(n = 0\) 时，为一个 \(1\)
- \(n > 0\) 时，左上角为 \(0\) 矩阵，其余部分为三个 \(Mat_{n-1}\)。
在一个平面上画出两个 \(Mat_n\)，左下角分别为 \((0,0),(x,y)\)，求都为 \(1\) 的位置有多少个。
思考：
考虑旋转矩阵转化为位运算计数问题，转化为求整数对 \((i,j)\) 满足
(i&j) == 0 and ((i+x)&(j-y)) == 0
考场上看到要高精就润了，没有认真思考。
实际上可以考虑类似 数位dp 的算法，也不难。
22020208考试 T2(后缀自动机复习)
题意：
给定一个字符串 \(s\) ，\(q\) 次询问 \(l,r\)，表示所有 \([l,r]\) 开头的子串中本质不同的子串个数。
\(n,q = 2 \times 10^5\)
思考1：
考虑后缀自动机求本质不同子串个数的方式，发现它可以在线完成。
所以反着建后缀自动机。
对于 \(r=n\) 的部分分，显然先离线，可以建后缀自动机时统计下每一个结尾的答案，输出即可。
如果 \(r \neq n\)，那么不妨仍然考虑在后缀自动机上如何统计答案。
后缀自动机本质上维护的是 \(endpos\) 集合，对于一个询问，如果一个 \(endpos\) 集合中包含一个位置 \(x\in[l,r]\)，那么这个 \(endpos\) 集合所代表的子串应该被计入贡献。
后缀自动机上每个子串仅在一个 \(endpos\) 集合中出现，所以可以求出至少有一个元素被包含的集合，并直接加和。
考虑对于每个询问该如何统计答案，限制一共有两个 \(l,r\)，并不好做，然而我们发现后缀自动机是在线构建的，所以如果将询问离线，那么限制就只剩下一个 \(r\) 了。我们在构建后缀自动机的同时只需要记录每个 \(endpos\) 集合最小的元素 \(val\)，查询时查询所有满足 \(val \leq r\) 的集合的子串数量和即可。考虑维护一个数组 \(c\)，\(c[i]\) 表示 \(val = i\) 的 \(endpos\) 集合子串个数和，用 \(BIT\) 查前缀和，现在只剩下修改了。
考虑 \(endpos\) 树的性质，发现修改操作是把一段到根的路径赋值，同时还有修改父亲等操作，于是考虑动态树，我们不难发现一段实链上的集合，\(val\) 都是相同的，所以在每个节点维护一下 \(val,sum\) 值即可，注意 \(push\_down\) 操作时需要把赋值也 \(push\_down\) 下去。
这样做未免显得有些麻烦，我们考虑最终构建的后缀自动机，倒序激活 \(endpos\) 中每一个点，这样就不需要 \(Link\) 和 \(Cut\) 操作，只需要写 \(access\) 就行。
实际上未必需要用后缀树来实现，通过激活点的方式，树已经时静态的了，这本质上还是一个区间染色问题，我们完全可以直接重链剖分，在每条重链上开个栈维护断点，记录下前缀和。
复杂度都是 \(O(nlog_n^2)\)，个人认为类似动态树的方法会好写一些。
思考2：
考虑使用后缀数组，回想后缀数组统计不同子串个数的方式，实际上就是排序后减掉相邻两个的
\(lcp\)，于是对原串后缀排序，然后离线询问莫队，拿个
set 维护当前所有串的排名集合，再来个 \(ST\) 表计算 \(lcp\)，插入和删除都很好写，复杂度 \(O(n\sqrt n \ log_n)\)，难以通过本题。
考虑优化，有一个技巧，这种需要查前驱后继的东西，实际上可以用链表搞，加入相对困难一些，因为我们不知道到底应该放在哪里，但删除就很容易了，双向链表上直接删就完事了，所以可以回滚莫队，非常无脑，时间复杂度 \(O(n\sqrt n)\)。
稍加卡常即可通过，\(ST\) 表查询常数相对较大，卡常应考虑尽量减少查询次数。
20220210
20220208考试T3
恶心的题意
思考
发现由于编号连续，所以最后经过的一定是一段连续区间。想到可以枚举右端点，二分左端点。
一个区域到另一个区域的路径可以分为区域到中转站和中转站到中转站两部分，区域到中转站的情况可以只计算到左右两边最近的中转站，所以容易计算。
我们按照右端点顺序激活中转站，问题就是要最小化左端点。
两个中转站只能通过同一条线连接，把最低点也看成中转站，所以可以认为从一个中转站到另一个的代价为两者所在区域编号的较小值。
中转站到中转站的距离可以 Floyd
暴力，我们就已经计算出了每对中转站点相互抵达的代价，所以二分都不需要了，我们可以直接用这个代价计算出最终答案。
实现细节
Floyd
的时候，因为加入的中转站并不是按下标顺序，所以需要整个跑一遍。
20220211
20220211 测试 T1
题意
思考
这道题算是考场上想出来的，考场上摸了一会儿鱼，发现有个地方假了的时候只剩 \(5min\) 了，所以紧急修复成了\(50pts\)，实际上不管直接交有 \(80pts\)。
先把最上面那些没有的行删掉。
考虑每一行的可能性，只有穿过和不穿过两种，穿过又可以分为去的时候穿过和回的时候穿过。
来的时候穿过，回的时候一定不会穿过，因为一定不优，于是三进制枚举穿过状态，大的路径框架已经被构建出来了，现在要考虑经过那些没有穿过的点。
被穿过的行不用管，现在就剩没穿过的行，每一行可以从左到右，也可以从右到左，如果两边都有经过，还可以两面包夹，算出每一行的结果，然后加上去就行。
这样可以拿到 \(80pts\)，因为它处理不了这种情况。
1 | 3 7 |
它会穿过第一行和第二行，到第三行后穿过或者是走到底再回来，实际上在穿过第一行走到第二行的时候就应该上去拿掉右上角。
所以把大的路径画出来后，记录每一个边缘位置是否到达过，还要自下而上 \(dp\) 一遍求出经过所有未经过的点的最小代价。
提供一种思路，设 \(dp[i][j][k]\) 表示到第 \(i\) 行，左右最前面的可以已经经过的点为 \(j,k\) 的最小代价，转移的时候看 \(j,k\) 是否大于 \(i\) 或者 \(i\) 的两端是否已经经过，如果可行，就选经过一行三种方案的最小值，如果不行，因为一定有一边已经经过，所以只考虑另一边是否补全和从经过的点走一遍再回来的情况，补全的方案有两种，从上面和从下面，直接转移即可。
时间复杂度 \(O(n^3 * 3^n)\)，实际上剪枝后跑的飞快，\(10ms\) 就跑完了。
20220212
20220212测试T2
题意
思考:
考虑直接 \(dp\) 转移，设 \(dp[i][j][k][0/1]\) 表示考虑前 \(i\) 个数， 正色子已经用了 \(j\) 个，反色子已经用了 \(k\) 个，是否已经赢了的方案数，直接转移是 \(O(n^4 * t)\) 的，可以拿到 \(20pts\) 的好成绩。
考虑优化，转移式子是：
1 | for(int i1=0;i1<=n;i1++) |
转移目标
dp[i][i1][i2][1]
前面一部分
1ll*dp[i-1][j1][j2][0]*C[n-j1][i1-j1]
和后面一部分
C[m-j2][i2-j2]
只有前一部分依赖 \(j1\)，考虑能不能预处理前一部分的转移，然后优化一个 \(n\)
显然是可以的，手推一下式子可以得到一个新的转移。
1 | for(int j1=0;j1<=n;j1++) |
优化到了 \(O(n^3*t)\)，记此时的常数 \(k = 1\)，它需要约 \(15s\) 通过数据规模最大的测试点。
这份代码可以拿到 \(50pts\) 的好成绩，感觉上已经不太能优化复杂度了，我们考虑卡常。
第一步，发现 \(n=6\) 的时候只需要转移 \(dp[6][n][m][1]\)
第二步，发现 \(n=1\) 的时候被转移的只有 \(dp[0][0][0][0]\)
常数变为 \(k = \dfrac{2}{3}\)
此时可以拿到 \(70pts\) 的好成绩。
继续考虑卡常。
发现其实在 \(i>=t\) 时转移 \(dp[i][i1][i2][0]\) 没有意义，直接剪掉。常数没有变化。
发现 \(dp[i][i1][i2][1]\) 实际上可以由 \(dp[i][i1][i2][0]\) 直接得到，所以只转移 \(dp[i][i1][i2][0]\) ，记作 \(dp[i][i1][i2]\)，常数变为 \(k = \dfrac{1}{3}\)
1 | if(i<=t) |
此时的成绩还是 \(70pts\)，但我们可以观察一下代码，在 \(i>t\) 后的转移实际上没有任何意义，可以直接计算，优化这一部分，可以拿到 \(90pts\) 的好成绩。
1 | for(i=2;i<=min(t,5);i++) |
最后的 \(10pts\) 可能需要一些卡常技巧。
我们发现实际上复杂度的瓶颈在数组寻址和取模，考虑优化其中之一，被寻址的数组经过循环变量的调整已经相当连续了，我们考虑优化取模。
用 long long 存 \(dp\)，每 \(8\) 次加法取一次模，可以通过本题。
一个很常见的，在取模运算较多时的优化技巧。
20220211 测试T3
题意
思考：
这道题暴力思路无非就二进制枚举和容斥。正解的做法很神仙。
在这种 \(\text{NP}\) 问题中，我们完全可以考虑将枚举的部分减少，这道题的思路是对稀疏图删点变为森林，然后二进制枚举一些删掉的点的状况再进行树形 \(dp\)，着实是一个很有启发性的思路。
20220212
CF1637F
思考:
对于这种条件为最小值的覆盖问题，我们不妨考虑最大的那个点是如何被覆盖的，首先有一个结论是只会在叶子有基站，证明简单，略去。然后考虑最大的那个点是如何被覆盖的，把它看作根，一定来源于它不同儿子的两个叶子，所以我们考虑其它点的时候一定可以认为这个根上的值为 \(\text{INF}\) ，理由不多说了。所以每个点 \(u\) 的包含的叶子至少有一个最大值为 \(h_u\)，贪心即可，最后决策最大值的点应该放在哪里，同样的贪心。
实现较为简单，没什么说的。
20220225
haltoj116
思考：
考虑团和独立集的性质，我在考场上就想到了答案一定不多，极大概率无需取模这一特性，于是用类似分治的方式得到了 \(60pts\)，如果我们找出了一个合法解，那么其它合法解的构造也是简单的，考虑合法解的性质，不妨设团的大小为 \(s\) ，那么因为独立集只能向团连边，所以独立集中的点最大度数为 \(s\)，而这样又导致了团中的点最小度数增加，所以我们不难发现团中的点一定是度数最大的那一段前缀。
对于度数相同的点，看似无法下手，但是我们知道边的构成是团内加上团和独立集之间，团内的边数我们是知道的，而如果记录一下团中点的总度数，我们可以很轻松的推出独立集间是否有边，我们设团内点的总度数为 \(p\),团的大小为 \(i\)，团内边数为 ，那么其他点之间的边数就为 \((2*m-2*p+i*(i-1))/2\)，所以我们考虑满足 \(2m + i * (i-1) = 2p\) 这个条件的选择有什么性质，因为这是成立的必要条件，考虑证明这也是充分条件。如果团内边数不足 \(i*(i-1)\)，那么我们发现 \(p\) 这边会减小。考虑如果独立集内边数有边，那么 \(p\) 这边一样相对减少，所以这也是充分条件。
这道题结束了。
haltoj117:
思考：
考虑在原序列中是前缀 \(max\) 的点，它们在新划分的序列中一定也是前缀 \(max\)，如果新增了前缀 \(max\)，那么我们可以很轻松的改变划分情况去除这个前缀 \(max\)，所以如果原序列中前缀 \(max\) 的数量为偶数，就一定可以。如果为奇数，我们不妨考虑只有一个序列有新增的前缀 \(max\) 的情况。我们考虑从原序列中抽出一个新序列出来，设两个序列的权值之差为 \(k\)，如果抽了一个原先的前缀 \(max\)，那么 \(k\) 减少 \(2\)，如果新增了一个前缀 \(max\)，\(k\) 减少量为 \(1\)，所以我们将原先是前缀 \(max\) 的数的权值视为 \(2\)，其余的视为 \(1\)，问题就是是要选一个上升子序列，使得权值和为前缀 \(max\) 的个数，这个问题就相当简单了。
20220228
ABC215H(子集容斥的另一种思路)
考虑霍尔定律，枚举不满足条件的子集 \(mask\)，可以用 \(\text{FMT-DP}\) 计算出必须由 \(mask\) 供给的白菜数量，考虑减少一个子集中的白菜使得不满足条件，就可以计算出最少需要吃多少个。问题变成了统计答案，我们发现对于一个 \(mask\) 直接组合数计算然后相加会算重，又因为答案不是全集所以并不能简单容斥。而暴力计算强制每种白菜都选一个的复杂度是 \(O(3^n)\) 的，我们仍然考虑应用 \(\text{FMT-DP}\) 计算答案。事实上，这种组合数问题都可以考虑这种方式。
设 \(f_{mask}\) 表示所选白菜集合被 \(mask\) 包含的方案数，设 \(f'_{mask}\) 表示所选白菜种类集合恰好为 \(mask\) 的方案数，列有等式。 \[ f'_{mask} = f_{mask} - \sum\limits_{x \sub mask} f'_{mask} \] 令 \(f[i][mask]\) 表示当前子集为 \(mask\) ，低 \(i\) 位不一定存在，但高位都严格符合要求的方案总数，列有
1 | for(i=n-1;i>=0;i--) |
从 \(i+1\) 推到 \(i\) 的过程中，因为高位已经强制存在了，所以我们减去的就是 \(f[i][mask]\) 中所有不存在第 \(i\) 位，但高位符合要求的情况。
最后计算出来的 \(f[0]\) 就是上述的 \(f\)。
然后这道题就好做了。
20220301
考试 T1(SAM的进一步理解)
题意：
给定一颗字符在点上的 \(\text{Trie}\)，求 \(\text{Trie}\) 代表的所有字符串本质不同子串个数，顺便询问钦定字符大小关系后第 \(k\) 小的子串，保证 \(\text{Trie}\) 上字符随机且答案长度和不超过 \(800KB\)。
思考：
考场上想到可以类似 \(\text{SAM}\) 一样乱搞，然后就写了 \(\text{dfs}\) 构建 \(\text{SAM}\)，\(lst\) 指针被置为它父亲插入后的 \(p\)，这个做法在数据随机的情况下是没有问题的，但是如果出现构造数据，它会没掉。
首先是如果拉一条 \(a\) 链，链上每个点再挂一个 \(b\)，然后 \(dfs\) 回跳的时候重置 \(q\) 的来边到 \(np\) 时时间复杂度是 \(O(n^2)\) 的。
我所理解的 \(\text{SAM}\) 时间复杂度正确性基于两个东西，一个是 \(p\) 的深度变化情况，这证明了第一次构建边的时候时间正确。在 \(dfs\) 构建 \(SAM\) 的时候，大量回溯操作会导致 \(p\) 深度的异常变化，这样就不对了。第二个是重置 \(q\) 的来边的循环，这个可以分析 \(p\) 的 \(fa\) 所代表最短字符串长度来理解，每次重置 \(q\) 的来边，我们都认为是找到了一个更短的 \(np\) 所代表的字符串，不妨看成一个指针在插入的字符串上移动，它只会向右。重置完 \(p\) 的来边再插入下个点的过程中，我们至少会跳到 \(np\) 处（只针对单个串），然后重设的 \(p'\) 的 \(fa\) 的最短长度一定可以从 \(np\) 那里继承过来，所以指针只会右移。\(dfs\) 加入时同样导致了这个指针在 \(\text{Trie}\) 上乱跳，复杂度就没有了保证。
然后是正确性相关的问题，这种 \(\text{SAM}\) 写法会导致无效的空节点建立，比如说插入的时候就碰到了满足 \(a[lst].ch[c]\) 存在的情况，这样新建出来的点实际上是无效的，在绝大部分题目中这个无效点是不影响答案的，但是少部分写法会导致爆炸。
接下来讨论下 \(\text{BFS}\) 建树的正确性。由于是按深度加点，所以 \(a[lst].ch[c]\) 一定是不存在的，因此绝不会导致无效节点的建立，时间复杂度证明不会，省略。
时间复杂度我并不会证明 emmmm.
ABC241H
思考：
生成函数套路题。
20220302
ARC136E
思考：
显然偶数链是很好走的，所以考虑从偶数边怎么到另一个节点，显然偶数只能选一个，我们先考虑不选偶数的情况。
定义 \(f[x]\) 为 \(x\) 的最小质因数，\(x\) 能走到 \(y\) 的充要条件是 \(y>x,x+f[x]\leq y-f[y]\)，如果 \((x,y) = 1\)，那么显然，因为 \(x\) 第一步至少走 \(f[x]\)，到 \(y\) 的最后一步至少走 \(f[y]\)。如果 \((x,y) \neq 1\)，设 \(x = p \times f[x]\)，则 \(y\) 至少为 \((p+2)\times f[x]\)，故结论仍然成立。
由此可以 \(x\) 走不到 \(y(y>x)\) 的充要条件为 \(x+f[x]>y-f[y]\)，将每个点视为 \((x-f[x],x+f[x]])\) ，题目就是要求出一些区间的集合，使得所有区间有公共点，要求权值最大，不妨枚举公共点，然后差分计算即可。
考虑下偶数，实际上做法类似。
20220303
AGC027E&&haltoj119
思考：
观察不变量是这种变换题的思考方向之一，我们设 \(a\) 的权值为 \(1\) ，\(b\) 的权值为 \(2\)，总能发现权值和对 \(3\) 取模的结果不变。
先考虑一个字符串在什么情况下可以变成另一个字符串，权值相同显然是必要条件，其次，源串 \(s\) 不能是交替串 \(abababa\) 这类，这有点困难，不妨先考虑变成一个字母的情况。
充要条件为权值相同且不交替，证明考虑归纳法。
现在考虑目标为一个字符串的情况。我们先贪心的匹配，用最少的字母构造出目标串，然后考虑调整剩下的部分使得它满足条件。如果特判掉交替串，我们发现只要权值相同且源串的一个前缀能和目标串贪心匹配上，那么一定可以变成目标串，于是考虑 \(dp[i]\) 表示考虑到前 \(i\) 的源串字母，能贪心的对应上多少不同串，显然这样的贪心对应是不重不漏的，转移分为匹配 \(i+1\) 和不匹配 \(i+1\) 两种，预处理一个类似 \(nxt\) 的东西可以做到线性。
20220304
CF917D&&haltoj122(初探二项式反演)
思考：
考场上已经观察出原题需要求一张完全图有多少棵最小生成树与给定树至少有 \(n-k-1\) 条边相同。\(prufer\) 序列有一个结论，\(n\) 个点 \(k\) 个连通块的图构成有标号无根树的方案总数为 \[ n^{k-2}\times\prod_{i=1}^{k} sz[i] \] 显然我不会证明。场上看到 \(n\) 仅为 \(50\) 就想乱搞，误打误撞弄了一个容斥 \(dp\) 出来，实际上正解差不多就是这个。我们考虑钦定选了 \(k\) 条边一定存在的方案总数 \(f(k)\)，由二项式反演的套路可以得知恰好 \(k\) 条边存在的方案数 \(g(k)\) 满足 \[ g(k) = \sum_{i=k}^{n-1}(-1)^{i-k}\times C(i,k) \times f(i) \] 其中 \(C(i,j)\) 表示组合数。
显然我仍然不会证明，但是可以感性理解下，首先 \(f(k)\) 满足以下式子 \[ f(k) = \sum_{i=k}^{n-1}C(i,k) \times g(i) \] 这个很好理解，枚举实际上选了多少条边，钦定 \(k\) 条边的方案数就是从实际选的边中钦定一些出来。注意这个钦定和至少有区别，不是简单的后缀和，因为实际选一条边的方案可以被多种钦定的情况包含。
我不会证明二项式反演的式子，所以我们从容斥的角度来考虑 \(g(k)\)，第一项为钦定 \(k\) 条边，然后减去被多考虑了的存在 \(k+1\) 条边的情况，依此类推。组合数的存在则是因为 \(f(i)\) 会被额外考虑 \(C(i,k)\) 次。
\(f\) 肯定比 \(g\) 好算，我们现在需要计算的是选 \(k\) 条边，然后得到的联通块组成不同有标号无根生成树的方案数。注意到生成树计数公式中 \(n^{k-2}\) 与怎么选边完全无关，所以只需要记录一下 \(\prod sz_i\)，这个就可以 \(dp[i][j][k]\) 表示考虑以 \(i\) 为根的子树，选了 \(j\) 条边，\(i\) 所在连通块大小为 \(k\) 的方案数。优化的话，可以考虑 \(\prod sz_i\) 的组合意义。于是就是需要在每个连通块内选一个代表元，于是状态第三维简化为是否选了代表元，复杂度 \(O(n^2)\)。