2019-Sp045-lyk
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
[[Image(1.png,700px)]]
[[Image(2.png,700px)]]
[wiki:2019-team2 返回Runespoor]
wiki:2019-C11
[http://opentrains.snarknews.info/~ejudge/team.cgi?contest_id=010231 contest]
== 流水账 ==
== 总结 ==
'''zqq: ''' 我们还是开场很爆炸。I和J一开始我都没有想法，B题一个简单的费用流板子没有加优化TLE了，然后加了优化还写错了WA了三发。
G题我们的做法不是正解，但是幸运的过了。
A题当时heltion问我统计(n - x) XOR (x - 1) XOR (m - y) XOR (y - 1)，我连数位DP都没有反应过来。
我这几天精神状态比较差，再加上写题后很累，思维速度明显下降，D和B都写错了非常sb的地方，需要平静下来稍微写慢一点。
好多基本的套路题我们都没有想出来，但是用一个另外的做法把它艹过去了。比如J题就做麻烦了
被学军一队吊打，他们2h53m就9个题了
H题字符串构造不会，但是区域赛的时候最后50分钟是不能挂机的！
== 题解 ==
* A ： 递归和斐波那契数列求和原理类似,两维就是log_2_n.
* C ：每次找度数为2的点删除。一定可以删完。
* D ： 每次加一条边暴力更新可能更新的状态，每个点只会被更新n次，复杂度O(n * m )，不满
* F ： 整体二分。lyk的做法是按时间分块。
* G ： 正解：考虑补图，有2 / 3的独立集，我们需要选出1 / 3。枚举一条边，删除边连接的两个点，这样一定剩下至少1 / 3的独立集
我们的做法：把度数小于 < 2n / 3 - 1的点删去，重复操作直至删完。然后按度数排序能选就选
* H : 将所有border（前缀的一段 = 后缀的一段）求出来，就得到原串的所有周期集合。从小到大枚举border，考虑构造字典序最小。如果a[i - 1] * 2 >= a[i]则已经确定，a[i - 1] * 2 < a[i]则中间空出位置的一段。这一段填00...001是肯定合法的（因为开头是0）,现在只需要判断填00..00000是否合法。这个可以kmp维护fail数组，只需要判断填完后的周期不能恰好整除当前串。'''我们最后真的不应该放弃这道题，因为写一个暴搜真的就过了！'''
* I ：排序，扫过去的时候枚举每种颜色选择比它小但是最大的两个
* J ：首先找到一个不是叶子的点当根。
设size(u)代表u的子树里面有多少个叶子，fv(u)代表u到父亲的那条边的边权。
最小: 如果偶数个点，我们对每个size(u)=1的点，答案加上fv(u)。如果有奇数个点该怎么办呢？我们直接枚举删掉哪个，根据之前的算法，我们很容易找到一个删掉后，答案减少最多的。
最多: 用重心当根（重心为只有叶子权重为1的重心），那么如果叶子个数为偶数，答案就是所有叶子到根的路径长度和。否则我们找一个最小的删了。这样做可以因为如果个数是奇数个，我们删掉任意点，重心不变。
我们的做法：
统计一条边的贡献：w * min(a,b) , a , b为两边的叶子个数。有了这个性质就可以树形dp或者对每个叶子计算贡献了。
== 补题 ==
* H ： zqq
wiki:2019-C11
流水账
总结
zqq: 我们还是开场很爆炸。I和J一开始我都没有想法，B题一个简单的费用流板子没有加优化TLE了，然后加了优化还写错了WA了三发。
G题我们的做法不是正解，但是幸运的过了。
A题当时heltion问我统计(n - x) XOR (x - 1) XOR (m - y) XOR (y - 1)，我连数位DP都没有反应过来。
我这几天精神状态比较差，再加上写题后很累，思维速度明显下降，D和B都写错了非常sb的地方，需要平静下来稍微写慢一点。
好多基本的套路题我们都没有想出来，但是用一个另外的做法把它艹过去了。比如J题就做麻烦了
被学军一队吊打，他们2h53m就9个题了
H题字符串构造不会，但是区域赛的时候最后50分钟是不能挂机的！
题解
- A ： 递归和斐波那契数列求和原理类似,两维就是log_2_n.
- C ：每次找度数为2的点删除。一定可以删完。
- D ： 每次加一条边暴力更新可能更新的状态，每个点只会被更新n次，复杂度O(n * m )，不满
- F ： 整体二分。lyk的做法是按时间分块。
- G ： 正解：考虑补图，有2 / 3的独立集，我们需要选出1 / 3。枚举一条边，删除边连接的两个点，这样一定剩下至少1 / 3的独立集
我们的做法：把度数小于 < 2n / 3 - 1的点删去，重复操作直至删完。然后按度数排序能选就选
- H : 将所有border（前缀的一段 = 后缀的一段）求出来，就得到原串的所有周期集合。从小到大枚举border，考虑构造字典序最小。如果a[i - 1] * 2 >= a[i]则已经确定，a[i - 1] * 2 < a[i]则中间空出位置的一段。这一段填00...001是肯定合法的（因为开头是0）,现在只需要判断填00..00000是否合法。这个可以kmp维护fail数组，只需要判断填完后的周期不能恰好整除当前串。我们最后真的不应该放弃这道题，因为写一个暴搜真的就过了！
- I ：排序，扫过去的时候枚举每种颜色选择比它小但是最大的两个
- J ：首先找到一个不是叶子的点当根。
设size(u)代表u的子树里面有多少个叶子，fv(u)代表u到父亲的那条边的边权。
最小: 如果偶数个点，我们对每个size(u)=1的点，答案加上fv(u)。如果有奇数个点该怎么办呢？我们直接枚举删掉哪个，根据之前的算法，我们很容易找到一个删掉后，答案减少最多的。
最多: 用重心当根（重心为只有叶子权重为1的重心），那么如果叶子个数为偶数，答案就是所有叶子到根的路径长度和。否则我们找一个最小的删了。这样做可以因为如果个数是奇数个，我们删掉任意点，重心不变。
我们的做法：
统计一条边的贡献：w * min(a,b) , a , b为两边的叶子个数。有了这个性质就可以树形dp或者对每个叶子计算贡献了。
补题
- H ： zqq