2021-team8-003
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
= 流水账 =
签到很快，H题花了一些时间想复杂度严格的算法，xqj表示尝试一发暴力，直接过了，很有启发意义。之后肝E和K，都想了挺久，K想出过几个有点假的算法，E越想越晕，最后1h时xqj恍然大悟K可以翻转对应过去，然后飞快过了，但E瞎猜无果，J难以下手，就此结束。
= 总结 =
多尝试暴力类似的做法。应该把题都读完。最好不要几个人都想一道题。过的人多或过的早的题一般确实很简单。
= 题解 =
A: 一位一位对在一起模拟
B:
C: “看懂题就会做”，构造出哈夫曼树就是不停往左走的一棵树，B树的深度是log级别的，所以需要的颜色数也是log级别的，f[i][j]表示以i为根的子树，i的颜色为j的方案数，按照W树的那个形状转移即可
D: 下标和值域互换，枚举区间看对应过去是不是小于等于两端，n=1特判
E: 考虑读入了一条边x<--y（x战胜y），此时每个点连出去的边数为f[i]。首先，如果y之前连出去的边都被割掉，那么他的值会传给x，于是需要确保在这之后x的值会传给1，也就是x需要再连k+1-f[y]条边。其次，最基本地，x需要连出至少k+1条边，也就是需要再连k+1-f[x]条边，于是可以将此时的f[y]变为min(f[x], f[y])，并将f[y]加1，最终需要让每个f都至少为k+1，不足的直接连到1号点即可，据此统计答案。（为什么我(rtx)当时怎么都想不出来而且特别晕呢？主要因为没有条理，搞不懂一条新的边对于两个点到底是什么影响，顺序问题没有搞清楚，所以就觉得很复杂。）
F: 二进制展开往上推即可
G:
H: 每个三元环缩成一个点，不停缩下去（直接暴力就能过）
I: 枚举下边界，枚举右边界，所有左边界对应的上边界单调，维护单调栈再维护一个和即可
J: 先考虑位似，就是要gcd，再考虑先旋转再位似，旋转可以看做是乘/除一个复数，于是就是找三条边对应复数的“复数gcd”，算这个东西要使用“复数取模”，也就是一个“整数复数”除以一个“整数复数”得到一个“整数复数”和一个余数。首先考虑怎么定义，需要让取模后的余数的模比除数（分母）的模小，然后就可以递归下去了。要实现这一点，先求出除法得到的有理数复数，把实域和虚域都四舍五入，去掉的小数部分模长肯定小于1，四舍五入剩下的就是整除结果，再用被除数减即可。
K: 分块，考虑如何计算所有数经过一个块后变成什么，首先值域是连续一段，如果与a_i不想交，直接翻过去，否则较小的一段可以对应到较大一段里面去（并查集），这样最多对应值域次流水账
签到很快，H题花了一些时间想复杂度严格的算法，xqj表示尝试一发暴力，直接过了，很有启发意义。之后肝E和K，都想了挺久，K想出过几个有点假的算法，E越想越晕，最后1h时xqj恍然大悟K可以翻转对应过去，然后飞快过了，但E瞎猜无果，J难以下手，就此结束。
总结
多尝试暴力类似的做法。应该把题都读完。最好不要几个人都想一道题。过的人多或过的早的题一般确实很简单。
题解
A: 一位一位对在一起模拟
B:
C: “看懂题就会做”，构造出哈夫曼树就是不停往左走的一棵树，B树的深度是log级别的，所以需要的颜色数也是log级别的，f[i][j]表示以i为根的子树，i的颜色为j的方案数，按照W树的那个形状转移即可
D: 下标和值域互换，枚举区间看对应过去是不是小于等于两端，n=1特判
E: 考虑读入了一条边x<--y（x战胜y），此时每个点连出去的边数为f[i]。首先，如果y之前连出去的边都被割掉，那么他的值会传给x，于是需要确保在这之后x的值会传给1，也就是x需要再连k+1-f[y]条边。其次，最基本地，x需要连出至少k+1条边，也就是需要再连k+1-f[x]条边，于是可以将此时的f[y]变为min(f[x], f[y])，并将f[y]加1，最终需要让每个f都至少为k+1，不足的直接连到1号点即可，据此统计答案。（为什么我(rtx)当时怎么都想不出来而且特别晕呢？主要因为没有条理，搞不懂一条新的边对于两个点到底是什么影响，顺序问题没有搞清楚，所以就觉得很复杂。）
F: 二进制展开往上推即可
G:
H: 每个三元环缩成一个点，不停缩下去（直接暴力就能过）
I: 枚举下边界，枚举右边界，所有左边界对应的上边界单调，维护单调栈再维护一个和即可
J: 先考虑位似，就是要gcd，再考虑先旋转再位似，旋转可以看做是乘/除一个复数，于是就是找三条边对应复数的“复数gcd”，算这个东西要使用“复数取模”，也就是一个“整数复数”除以一个“整数复数”得到一个“整数复数”和一个余数。首先考虑怎么定义，需要让取模后的余数的模比除数（分母）的模小，然后就可以递归下去了。要实现这一点，先求出除法得到的有理数复数，把实域和虚域都四舍五入，去掉的小数部分模长肯定小于1，四舍五入剩下的就是整除结果，再用被除数减即可。
K: 分块，考虑如何计算所有数经过一个块后变成什么，首先值域是连续一段，如果与a_i不想交，直接翻过去，否则较小的一段可以对应到较大一段里面去（并查集），这样最多对应值域次