A
质朴的想法，每一行都放 ryxyryx...，然后因为有 \(40\) 列所以最后一列完全没用，所以把那一行竖着放进去，算一下有 \(2223\) 个。
然后枚举填多少行，如果数量多了就在最后一行选一个位置插入字符（这样后面就没有斜着的贡献了）。还多就从后往前覆盖 y。然后总可以构造出来。
B
5k 翻译版题面：
同学的策略形如 \(\{p_n\}\)，其中 \(p_i\) 表示救 \(i\) 房间里的人的概率，而且显然有 \(0\le p_i\le 1,\sum p_i\le 1\)。
求最小的 \(m\)，使得存在一种同学的策略，满足无论老师刀哪个房间的人，刀掉的期望人数都不超过 \(m\)。
学生选 \(i\) 的概率是 \(p_i\)。那么老师选 \(i\) 的期望人数是 \((1-p_i)a_i\)。
二分答案，学生要使老师选任何房间的期望都 \(\le mid\)，如果 \(a_i > mid\)，学生需要分配一个概率使 \((1-p_i)a_i\) 恰好等于 \(mid\)。最后合法的要求是 \(\sum_{i=1}^n p_i \le 1\)。
C
考虑给你一个排列 \(p\)，如何快速计算所有的 \(F\)。可以将所有 \(p\) 按从大到小的顺序加入，那么假设加入了 \(\ge k\) 的 \(p\) 后最大连续段长度为 \(L\)，我们令 \(F(L), F(L - 1),\dots F(1)\) 都对 \(k\) 进行 chkmax 即可。
反过来，如果有了 \(F\)，那么相当于一些限制条件：加入了所有 \(\ge k\) 的 \(p\) 后，最大连续段长度恰好为 \(L\)。考虑逆向操作，即删除 \(< k\) 的 \(p\)（从小往大删除）。维护当前的连续段情况，每次即选择一条连续段裂开，长度减一。这样做的好处是连续段之间不作区分，可以排序，总状态数即为划分数。直接 DP 即可。
D
省集原神。
感觉省集题面亲民多了。
省集：
有 \(n\) 个宠物在进行宠物对战，每只宠物是水（\(A\)）、火（\(B\)）、佬（\(C\)）、菜（\(D\)）四种属性之一。宠物分别编号为 \(1\) 到 \(n\)。
属性克制关系如下：
- “水”和“火”互相克制
- “佬”分别克制“水”“火”“菜”三种属性
- “佬”“水”“火”三种属性都克制“菜”
- 其它上述没有提到的都不克制
很显然，这是个极度不平衡的游戏，所以大家两两对战若干场之后就再也没人玩了，只留下了一份比赛中克制关系的记录。
现在你拿到了这份残缺不全的记录，也就是 \(n\) 只宠物之间一部分对战场次的克制关系。你想要从中恢复这 \(n\) 只宠物各自的属性信息，不过因为符合条件的属性信息可能有多种，你只需要输出任意一种解即可。
第一行两个非负整数 \(n,m\) 依次表示宠物个数和已知的克制关系条数。
接下来 \(m\) 行每行三个整数 \(x,y,z\) 表示一条记录。其中 \(z=0\) 表示已知 \(x\) 号不克制 \(y\) 号，\(z=1\) 表示已知 \(x\) 号克制 \(y\) 号。
形式化题面：
给定一个 0/1 权有向图，给每个点赋权
ABCD中的一个使每条有向边 \((u,v,w)\) 都满足 \(w=1 \Leftrightarrow (a_u, a_v) \in \{(A.B),(A,D), (B,A), (B,D), (C,A), (C,B),(C,D)\}\)。
发现佬和菜是很强的，如果一个点能填佬菜那么填上不会亏。
填完佬菜就是平凡染色问题了。
考虑怎么填佬菜。0 边的反图和 1 边的图是相似的，但是 1 边的图限制更强，0 边的反图可以相等，1 边图不行。
考虑 0 边的反图和 1 边的图，一个点可以填佬当且仅当在两个图里没有入度，但是 0 边可以相等，所以对 0 边反图缩点之后拓扑，对于当前没有入度的强连通分量，里面的每一个点在 1 边图都没有入度，那么这个连通分量都可以是佬。
菜是类似的，要求没有出度。
P6764
P6764 [APIO2020] 粉刷墙壁
观察数据范围：令 \(f(k)\) 表示喜欢第 \(k\) 种颜色的承包商数量，\(\sum f(k)^2\le400000\)。
小啊，很小啊（
设 \(f_{i, j}\) 表示在 \(i\) 让 \(j\) 承包商开始刷最远刷多远。那么 \(f_{i, j} = f_{i + 1,(j + 1)\bmod m} + 1\)。
然后枚举对每个 \(i\) 只枚举喜欢 \(C_i\) 的承包商，然后用滚动数组优化。根据数据范围时间复杂度可以接受。
然后对于每个 \(i\)，如果存在一个 \(j\) 使得 \(f_{i, j} \ge m\) 那么这个起点就是合法的。
知道哪些起点合法就是简单贪心了。
P3354
P3354 [IOI2005] Riv 河流
根据树形 dp 经典讨论，肯定有一维是 \(x\)，有一维表示子树内建了 \(k\) 个厂，0/1 表示根是否建厂。
但是这些状态不太能算花费，如果在 \(x\) 建厂时结算。把运费放状态里更是扯淡。
所以考虑在出发时就把终点定好。
设 \(f_{x, u, i, 0/1}\) 表示考虑到 \(x\) 点子树内最近的建厂祖先是 \(u\)，子树内一共建了 \(i\) 个厂，\(x\) 是否建厂的最小花费。
由于转移时和最后求答案都不关注根节点的建厂情况，所以可以在处理完 \(x\) 后把 \(1\) 状态统一并入 \(0\) 状态简化转移时的讨论。
现在对于子节点 \(f_{y, u, i, 0}\) 表示子树内最近的目标是 \(u\)，建了 \(i\) 个厂的最小花费。
for (int u = x; ~u; u = fa[u]) {per(j, k, 0) {f[x][u][j][0] += f[y][u][0][0];f[x][u][j][1] += f[y][x][0][0];rep(l, 0, j) {chkmin(f[x][u][j][0], f[x][u][j - l][0] + f[y][u][l][0]);chkmin(f[x][u][j][1], f[x][u][j - l][1] + f[y][x][l][0]);}}
}
最后将 \(1\) 状态并入 \(0\) 状态，注意上面算的时候没有把建在 \(x\) 的厂统计进状态。
for (int u = x; ~u; u = fa[u])rep(j, 0, k) {f[x][u][j][0] += w[x] * (dis[x] - dis[u]);if (j >= 1) chkmin(f[x][u][j][0], f[x][u][j - 1][1]);}
P3647
P3647 [APIO2014] 连珠线
换根 dp。
如果指定起始珠子（指定根节点），那么合法蓝线一定是跨 \(fa_x -x-son_x\)。
设 \(f_{x, 0/1}\) 表示 \(x\) 是否是蓝线中点的最大得分。
转移时 \(0\) 的转移平凡，\(1\) 的转移枚举选那个儿子转移最大。
现在不指定根，考虑换根，在 \(x\) 成为 \(y\) 的儿子时，首先失去了 \(y\) 子树的贡献，其次如果 \(x\) 有父亲的话还有从父亲转移过来。
\(y\) 减少的贡献一是对 \(f_{x, 0}\) 的贡献，二是如果 \(f_{x, 1}\) 从 \(y\) 转移也不能用了，所以还需记录 \(1\) 的转移的次大值。
在转移时注意 \(1\) 的转移还要和 \(fa_x\) 的贡献取 \(\max\)。
学到一种新的写法，在第一遍 dfs 是处理出 \(x\) 对于每个儿子的 dp 数组和最大值，第二遍 dfs 时可以直接拿来用了。
P3554
P3554 [POI2013] LUK-Triumphal arch
原题面的故事挺有趣的。最坏情况确实可以等价于 B 采取最优决策博弈。
答案显然满足可二分性。考虑如何判断一个 \(k\) 是否合法。
B 采取最优决策显然不会走回头路，那么是一路从根走到叶子。
A 输了也就是 B 在 \(x\) 时 A 未将 \(x\) 的所有儿子染黑。
那么 \(x\) 的儿子数 \(> k\) 时就需要祖先救一下，设 \(f_x\) 表示 \(x\) 子树内需要祖先提前染多少点。
那么 \(f_x = \max(0, soncnt_x - k + \sum f_y)\)。
如果最后 \(f_1 = 0\) 那么 \(k\) 合法，不然不合法。
这套题单里代码最好写的紫，但是想不到。
弦化
经典 subtask 随便绑导致随机部分分。
考到衡中一年前的原题然后被一年前的 int_R 和 5k 踩爆了/kk
考试时一道题开了两个链式前向星四个 vector 吓得我下午在 DP 题里完成了存图的缺省源/jk
namespace GRAPH {const int N = 3e5 + 10, M = 3e5 + 10;struct Edge {int y, nxt; long long w;};struct Graph {Edge e[M << 1]; int ly[N], ltp;void add(int x, int y, long long w = 0) {e[++ltp] = {y, ly[x], w}; ly[x] = ltp;}Edge &operator[](int x) {return e[x];}};
}
using GRAPH::Graph;
#define redg(i, e, x, y) for (int i = e.ly[x], y; y = e[i].y, i; i = e[i].nxt)
Graph e;
说到弦化其实我觉得小画家不戴眼镜比戴眼镜好看。
