前言

汇总了一些难度很高的题，以思维题为主。

代码拍卖会

由于每个小猪的出价都大于等于之前小猪，所以可以按照出价的多少写一个$n^8$的$dp$，

由于$P$很小，所以考虑剩余域压缩，数据范围可以定义一个 $11 × 500 × 500$ 的数组，所以不用滚动。

现在有两个问题，怎么计算剩余域以及如何递推。

我们不能枚举$n$，所以要找循环节，属性为数量，为了方便，我们将方案看作$9$个$01$串，由于都是$1$所以我们寻找$×10+1$的循环即可。

于是题目的意思就被转换成：从所有的 $cnt[i]$ 中找出（不超过）九个数，使得它们的下标之和能被 $P$ 整除！（为什么是下标之和？因为上面说了 $cnt[i]$ 中所有的形如 $1111…111$ 的数在模 $p$ 意义下为 $i$ ！）

考虑如何递推，不难发现我们需要枚举当前到第几个串、当前的后缀情况和要铺的后缀情况，以及要铺的后缀铺几个（有多个循环串），系数可以用隔板法得出。

总结一下，我们先处理$cnt[i]$表示$s[j]（注s[j]\%P==i）$个$1$连起来的方案数，

我们设$DP$数组$f[i][j][k]$ 表示考虑到$cnt[i]$，使用$k$个$111…11$形式的串之和对$P$取模为$j$的方案数。

Bears and Juice

熊想知道哪个酒桶里有酒，属于信息论，

先让我们对其进行建模，对于每个熊，它有一个桶的子集，这可以表示成一张方格表 (0/1矩阵)。

我们将这张方格表转置，即考虑对于每一桶饮料，喝过它的熊的集合。

首先，如果有一桶饮料，喝过它的熊的数量超过 $p′$，那么万一这桶饮料是酒，则 “喝醉” 的熊的个数就会超过 $p′$，则要么出现无床可睡的熊，要么所有熊都 “喝醉”，从而挑战无法成功。

其次，如果有两桶饮料，喝过它的熊的集合相同，且对应熊喝的天数也相同，则一旦 (恰好) 这些熊 “喝醉” 了，剩下的熊就无论怎样也无法知道到底哪一桶是酒，哪一桶是饮料，因此这是不行的。

经过这样分析，能 “辨别” 出现的饮料个数上界就容易确定了。

首先我们枚举一个桶由 $i$个熊去喝，那么我们就可以取一个熊的子集，对于子集中的每一只熊，都可以选择一个时间去喝，于是共有 $C^n_i × q^i$ 种方案。

当然，取 $i=0$ 也是可以的，这表示所有熊都没有喝这个桶中的饮料，此时如果所有熊都没 “喝醉”，就能推出这个桶中就是酒。

复杂度 $O(pq)$。

Train Tracking 2 P

从$c$序列相等的特殊情况推到朴素情况，

相等时可以直接合并，不相等时可以讨论管辖区间，由于区间互不干扰，乘法原理统计。

Grafting

从第一次操作开始考虑，由于结点只能操作一次，不妨将被操作过的叶子结点设为根，

那本题将转化成只有叶子结点可以动，且所有结点只能动一次。

显然我们要动的是不同构的结点，但这样显然没有涵盖我们上面的限制，

正确的思路是，一个点被操作，当且仅当它在两棵树中的父节点不同。

由上思路，可以总结出什么算法呢？

如果一个点不被操作，但是它的父节点要被操作，这是不可能的，因为它的父节点没有成为叶子的机会。

将思路具体化，就是$A$树一个点一定比父结点先动，在 $B$ 中，一个点一定比它的父节点更晚被操作。

那么我们把这个关系连边，如果可以成功拓扑排序，则自然有解，且拓扑排序的过程就构造了一个合法方案。

总结一下，就是$u$必须在$fa(u)$之前做，$fb(u)$之后做，偏序关系可以建图。

OKR-Periodicity

串 $s$ 有长度为 $l$ 的周期等价于其有长度为 $|s|-l$ 的 $border$。

不难想到按最短周期长度为$0$、$<=2/s$、$>2/s$和字符完全相同分类讨论。

首先由于是周期我们不能有不匹配的地方，所以直接循环，但是$<=2/s$的可能不能完整循环，不过我们可以取其前缀，至于$>2/s$，设 border 为 $t$，那么 $s$ 就可以表示为 $tat$ 的形式，其中 $a$ 是一个任意字符串，不能为空。

如果 $s$ 中所有字符相同，返回 $|s|$ 个 $0$ 构成的字符串；

如果 $s$ 周期集合为空，返回 $|s| - 1$ 个 $0$ 接上 $1$ 个 $1$ 构成的字符串；

Minimizing Edges P

题意:构造新图G’，边数最短的满足若在G上n点能从点1走k步到达，则G’上也应同样满足；且不存在点n，G’上能走k步到达而在G上不能

由于我们可以反复横跳，所以是否有值取决于奇/偶最短路的长度，当然二分图的情况可以特判为最小生成树。

① $i\leftarrow j,(x_i,y_i)=(x_j+1,y_j+1)$

② $x+1 < y.i\leftarrow j_1,j_2.(x_i,y_i)=(x_{j_1}-1,y_{j_1}+1)=(x_{j_2}+1,y_{j_2}-1)$

③ $x+1=y.i\leftarrow j_1,j_2.(x_i,y_i)=(x_{j_1},y_{j_1})=(x_{j_2}+1,y_{j_2}-1)$ $i$可能等于$j_1$

所以我们以$x+y$为第一关键字，$x$为第二关键字排序，从小往大贪心地选。大力讨论一下即可

机器人游戏

容斥，先把问题转化成统计不存在一个合法位置的方案数，接着统计有$k$个合法的，其它随便的方案数，系数为 $(-1)^k$。

考虑一个纸带：对于一个被钦定的每一个位置，要求输入经过这个机器人操作之后一定等于输出。仍然把输出表示成输入的形式，只不过这个输出可以以多种方式被输入表达。

对于每一个位置分类讨论：

1. 如果这个位置上表示成的结果 既有 0 又有 1 或 既有 x 又有 1-x：输入输出都为空。方案数为 $1$。
2. 如果不满足条件 $1$，这个位置上表示成的结果 有 0 或 1 且 有 x 或 1-x：输入输出都为空，否则输入输出就被固定了。方案数为 $2$。
3. 条件 1，2 都不满足：对于每一个输入都对应一个唯一的输出，方案数为 $3$。

这个纸带上每一个位置就是独立的了，最后把每个位置的答案乘起来即可。

由于机器人有且仅有 $c_i > n - r$ 的爆炸了，所以并不是每个都要记录下来。

最后$bitset(f[x])$优化即可，f[x] = f[x & -x] | f[x ^ (x & -x)]。

山河重整

计数有多少个元素在 $[1,n]$ 的集合，其 $01$ 背包能表示 $[1,n]$ 中的所有数

首先考虑从小到大加入数字，那么加入数字中途的每一个时刻，所能表示的都应是值域的一个前缀（因为加的数字越来越大）。

可以写一个$O(n^2)$的$DP$，考虑优化，

直接计数所有满足条件的序列看起来不那么容易，尝试钦定不满足条件的位置，然后进行容斥。确切来说，即找到一组不合法方案的，最小的 $i$，满足 $[1,i]$ 均可拼出但 $i+1$ 无法拼出，对这样的位置进行容斥。

不难发现 $[1,i]$ 均可拼出但 $i+1$ 无法拼出则总和恰好为 $i$，

其计算可以通过用 “所有方案” 减去 “$[1,i]$ 中存在元素无法拼出的方案”。前者是 $i$ 的互异拆分数，而后者可以通过之前的 $f$ 求得。

由于互异拆分拆分出的数字个数是 $\sqrt{n}$ 级别的，另一个容斥只有在 $i\ge j+(j+2)$ 时$f_ j$ 能贡献到 $f_i$（避免计数重复），所以复杂度是 $O(n\sqrt{n})$

Border 的四种求法

不会后缀，咕咕。

后文

没有人会希望看完了呆板的题目讲解，却没有一个好的道别。