2019-team11/0010
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
=== 补题 ===
题解：
A：
B：三子棋，状压深搜剪枝，判断条件一大堆，加个 set 去重，队友打表过的。
C：只有度少的点连向度多的点的边有效，将有效边建个新图，是有向无环图，直接记忆化搜索得最大值。
D：定义一个操作将数字按位拆分求平方和，问一个数字能不能通过这个操作变成1。直接暴力模拟，当操作后出现的数在之前已经出现过则该数不能变成 1 ，否则到 1 终止。除了第一个数其他出现的数都小于 9^3。
E：给一个图，对所有边求使其可能成为最小生成树上的一边所需要去掉的边的数量再求和，先做一遍最小生成树的大小，再分别求每条边先强制加入后生成的最小树的大小，如有不同则这条边不会出现在最小生成树里。对于每个不会出现在最小生成树里的边，将比它边权小的边连起来，求这个不会出现在最小生成树里的边两个端点之间的最小割，跑一个最大流得到这条边对答案的贡献。
F：类似分形。递归每一层求得下一层的相对坐标，再根据该点在这一层的所处位置变换坐标返回上一层。
G：按 x 坐标将图形分割，每个小方块分别求面积，存一下状态的变化方便计算对答案的贡献。
H：可以转化成字符串相匹的统计，将每一种字符分离出来就变成 01 串，答案等于每种字符 max(\sum{a_{i+offset}*b_i}) 翻转一下长的串，发现答案是 max(\sum{a_{n-i-offset}*b_i})，然后发现这个东西可以直接卷积，跑个 FFT 再在 0 到 n-1 中找最大值就是答案。
I：从后往前跑个魔改版的 KMP 求相同前缀长度，记 Next[i] 表示从 i 开始的后缀与从 Next[i] 开始的后缀匹配，递推的时候匹配失败跳转到 Next[i-1]+1 ，答案就是 i Next[i]-i 在 Next[i] 最小且 Next[i]-i 最小的时候。
J：
K：构造题，每条边判断头尾转向是否相同，相同输出 i，不同输出 1。
L：dp。F[i][j][k] 表示 第 i 个人 在 j 号点 待到 k 天 时的最小花费，递推 F[i][v][k+1]=F[i][j][k]+cost[i]< j->v > F[i][j][k+1]=F[i][j][k]+cost[i]< j->j > 天数不会超过情况数 所以每张图点数相乘就是最大天数，最后 F 中找答案即可。补题
题解：
A：
B：三子棋，状压深搜剪枝，判断条件一大堆，加个 set 去重，队友打表过的。
C：只有度少的点连向度多的点的边有效，将有效边建个新图，是有向无环图，直接记忆化搜索得最大值。
D：定义一个操作将数字按位拆分求平方和，问一个数字能不能通过这个操作变成1。直接暴力模拟，当操作后出现的数在之前已经出现过则该数不能变成 1 ，否则到 1 终止。除了第一个数其他出现的数都小于 9^3。
E：给一个图，对所有边求使其可能成为最小生成树上的一边所需要去掉的边的数量再求和，先做一遍最小生成树的大小，再分别求每条边先强制加入后生成的最小树的大小，如有不同则这条边不会出现在最小生成树里。对于每个不会出现在最小生成树里的边，将比它边权小的边连起来，求这个不会出现在最小生成树里的边两个端点之间的最小割，跑一个最大流得到这条边对答案的贡献。
F：类似分形。递归每一层求得下一层的相对坐标，再根据该点在这一层的所处位置变换坐标返回上一层。
G：按 x 坐标将图形分割，每个小方块分别求面积，存一下状态的变化方便计算对答案的贡献。
H：可以转化成字符串相匹的统计，将每一种字符分离出来就变成 01 串，答案等于每种字符 max(\sum{a_{i+offset}*b_i}) 翻转一下长的串，发现答案是 max(\sum{a_{n-i-offset}*b_i})，然后发现这个东西可以直接卷积，跑个 FFT 再在 0 到 n-1 中找最大值就是答案。
I：从后往前跑个魔改版的 KMP 求相同前缀长度，记 Next[i] 表示从 i 开始的后缀与从 Next[i] 开始的后缀匹配，递推的时候匹配失败跳转到 Next[i-1]+1 ，答案就是 i Next[i]-i 在 Next[i] 最小且 Next[i]-i 最小的时候。
J：
K：构造题，每条边判断头尾转向是否相同，相同输出 i，不同输出 1。
L：dp。F[i][j][k] 表示 第 i 个人 在 j 号点 待到 k 天 时的最小花费，递推 F[i][v][k+1]=F[i][j][k]+cost[i]< j->v > F[i][j][k+1]=F[i][j][k]+cost[i]< j->j > 天数不会超过情况数 所以每张图点数相乘就是最大天数，最后 F 中找答案即可。