S2题单：NOIP前建议做的题

删掉了一些没意思的题

P3449 [POI2006]PAL-Palindromes

首先有一个结论， $A,B$ 为回文串， $A+B$ 也是回文串当且仅当 $A,B$ 的最小循环节相同

现在假设是长度为 $n$ 的字符串 $S$ 和 长度为 $m(n \ge m)$ 的字符串 $T$ 拼在一起，现在有 $S+T$ 是一个回文串，所以 $S$ 一个长度为 $T$ 的前置u一定也是回文串，所以 $S+T$ 可以写成 $T+P+T$ 的样子，这样递归下去会变成 $xT+Q+xT$ 的样子，然后我们只保留 $Q+T$ ，现在肯定 $Q$ 的长度小于 $T$ ，对 $Q+T$ 继续重复上述操作直到无法操作，发现肯定是 $Q$ 是 $T$ 的约数的时候停止，不难发现 $Q$ 一定是 $S,T,S+T$ 的循环节，所以 $Q$ 的最小循环节一定是 $S,T$ 的最小循环节

剩下的就很好做了，直接按最小循环节分类就好了

P3158 [CQOI2011]放棋子

发现我选哪一行那一列不重要，我只要知道选了多少就行了，所以设 $f_{i,j,k}$ 表示考虑了前 $i$ 中颜色的棋子，已经 $j$ 行 $k$ 列有棋子占用了，转移就枚举我当前棋子要用几行几列，再乘上将这些行这些列全部占满的方案数就行了

现在问题是怎么算方案数，发现这玩意一脸容斥样子，设 $g_{i,j,k}$ 表示用 $i$ 个棋子占满 $j$ 行 $k$ 列的方案数，首先先算出 $i$ 个棋子随便放的方案数，然后减去只放满 $x$ 行 $y$ 列的方案数就行了

code

CF314E Sereja and Squares

shabby题

正解 $O(n^2)$

注意题目里说了，输入只有小写字母和问号

首先有一个显然的 $dp$ ，将小写字母看成左括号，大写字母看成右括号，设 $f_{i,j}$ 表示考虑前 $i$ 个字符，有 $j$ 个左括号的方案数，但是这个常数太大了过不去

发现只要对于任意的长度为 $i$ 的前缀，里面右括号数量小于 $\frac{i}{2}$ ，就一定能满足题目条件，所以设 $f_{i,j}$ 表示考虑前 $i$ 个字符，有 $j$ 个右括号的方案数，要是小写字母不用管，要是是问好就考虑他填成什么，要是是左括号就是 $f_{i,j}=f_{i-1,j}\times 25$ ，要是是右括号就是 $f_{i,j}=f_{i-1,j-1}$ ，滚动数组就可以过了

code

CF685B Kay and Snowflake

不知道怎么入选这个题单的

直接暴力就好了

首先叶子节点的重心一定是本身，考虑不是叶子的怎么求，发现就是我的重儿子的重心往上跳一跳，跳到他上面的子树大小小于等于点数一半，发现每条边最多被跳一次，所以复杂度正确

code

P3451 [POI2007]ATR-Tourist Attractions

不是很难的状压，设 $f_{s,i}$ 表示我现在走过的点集合为 $s$ ，我现在在点 $i$ 的最小代价，转移就枚举下一个点是什么点就好了，时间复杂度 $O(2^n n^2)$ ，但是这样空间是 $80MB$ ，用信号传递的卡空间技巧随便卡卡就好了，我的卡法是把 $S$ 去掉点 $i$ ，这样空间小一半，就能过了

code 抽象

CF1043F Make It One

想到了答案 $\le 7$ ，但是去想根号分治了然后误以为 $\sqrt n$ 内质数只有 $6$ 个

首先答案 $\le 7$ 很显然，考虑要是求出一个有 $8$ 个数的答案，考虑这个数有用当且仅当存在一个质因数只有我没有并且其他数都有，而 $3e5$ 最多只有六个质因数，加上一个特殊情况 $3\times 5\times 7\times 9\times 11\times 13 \times 17$ （即前六个没有 $17$ ，这个没有 $2$ ），所以最多只有 $7$ 个质数，又因为只能我有，所以一个质数最多让答案变大 $1$ ，所以答案 $\le 7$

现在考虑怎么求这个玩意，因为答案 $\le 7$ ，可以先枚举一手答案大小，发现我还是不会算 $\gcd=1$ 的，但是我会算 $\gcd$ 是 $x$ 的倍数，具体来说就是要是有 $sum$ 个数是 $x$ 的倍数，方案数就是 $sum \choose k$ （ $k$ 为枚举的答案），然后容斥就好了

code

[AGC013E] Placing Squares

考虑组合意义，现在等于是有 $n$ 个盒子，你要放插板把盒子分隔成若干段，每两个插板中间要恰好有一个黑球和一个白球，可以放在一个盒子里，求方案数

考虑 $dp$

$f_{i,0}=f_{i,0}+f_{i,2}$ 第一个表示不放球不插板，第二个表示不放球插板

$f_{i,1}=2f_{i,0}+f_{i,1}+2f_{i,2}$ 第一个表示放球（两种球都可以）不插板，第二个表示不放球不插板，第三个表示放球插板

$f_{i,2}=f_{i,0}+f_{i,1}+2f_{i,2}$ 第一个表示放球（两个都放这里）不插板，第二个表示放球（只剩一个了）不插板，第三个表示放球（两个都放这里）插板或不放球不插板

同理不能插板的也一样，把上面有插板的转移去掉就行了

这玩意显然可以矩阵快速幂优化，时间复杂度 $O(m\log n)$ 常数有 $27$ 😔 ，预处理出所有 $2$ 的整次幂然后用矩阵乘向量应该能优化掉一个 $3$ ，但是我摆了

code

P3643 [APIO2016] 划艇

首先肯定不能直接记下来每个学校有多少划艇，肯定是要离散化的，设 $c_i$ 为离散化后的数组 ，设 $f_{i,j}$ 表示第 $i$ 个学校派划艇，并且我的划艇数目是在 $[c_{j-1},c_j)$ 的方案数，但是我们还是不知道离散化后 $f_{i,j}$ 能不能从 $f_{k,j}$ 转移过来

然后就有了一个神奇的东西：给一个长度为 $n$ 的数组 $a$ 赋值，其中 $0 \le a_i \le m$ ，是其中的非 $0$ 项递增的方案数是 $n+m \choose n$ ，首先假设不能选 $0$ ，那么显然就是 $m \choose n$ ，现在可以不选，就等于在前面加上 $n$ 个 $0$ ，也可以选 $0$ 表示不选这个数，所以是 $n+m \choose n$

现在就很好 $dp$ 了，考虑我在转移 $f_{i,j}$ 的时候枚举一个 $k$ ，让 $(k,i]$ 的学校派的划艇都在 $[c_{j-1},c_j)$ 中，注意这段中有可能 $[a_x,b_x]$ 不包含 $[c_{j-1},c_j)$ ，还有就是因为状态钦定了第 $i$ 个必须在 $[c_{j-1},c_j)$ 中，所以组合数是 $n+m-1 \choose n$

转移方程：$f_{i,j}=\sum\limits_{k=0}^{i-1}{sum+c_j-c_{j-1}-1 \choose sum} \sum\limits_{t=0}^{j-1} f_{k,t}$ ， $sum$ 是 $[a_x,b_x]$ 包含 $[c_{j-1},c_j)$ 并且 $x < i$ 的 $x$ 的个数

这样是 $O(n^4)$ 的，前缀和优化一下就好了

code

P3452 [POI2007]BIU-Offices

P3188 [HNOI2007]梦幻岛宝珠

CF1166E The LCMs Must be Large

CF1045H Self-exploration

P3474 [POI2008]KUP-Plot purchase

CF1032F Vasya and Maximum Matching

[ARC087F] Squirrel Migration

首先先思考一下答案上界，对于每条边考虑贡献，断掉这条边后这棵树分成两棵树 $S_1,S_2$ ，不妨设 $|S_1|<|S_2|$ ，不难发现这条边的贡献最多是 $2|S_1|$ ，盲猜一首答案就是 $\sum\limits_{(u,v)} 2|S_1|$ ，不难发现这个是肯定能取到的，下面有一个构造方案

从点 $1$ 到点 $n$ 依次寻找 $p_i$ ，对于点 $i$ ，先转到根，$p_i$ 就是从 $i$ 开始的重链的另一头的点，$p_i$ 的 $p_{p_i}$ 就是 $i$，然后将 $p_i$ 删去

P5307 [COCI2018-2019#6] Mobitel

$SSH$ 的 $Karry5307$ 的

没见过 😔

首先有一个非常 $naive$ 的方程就是设 $f_{i,j,k}$ 表示我到达了$i,j$ 这个点，现在权值是 $k$ 的方案数，但是这样是 $O(rsn)$ 的，直接寄，但是乘除有一个很神奇的东西，整除分块，现在我们换一个状态， $f_{i,j,k}$ 表示我到达了$i,j$ 这个点，现在权值至少乘 $k$ 的才能到达 $n$ 方案数，因为 $\lfloor\frac{\lfloor \frac{a}{b}\rfloor}{c}\rfloor=\lfloor\frac{ \frac{a}{b}}{c}\rfloor$ ，所以这个转移显然是可以进行的，发现有用的 $k$ 只有 $\sqrt n$ 个，所以复杂度变成了 $O(rs\sqrt n)$ 可以通过

卡空间，记得滚动数组

code 代码是屎