这是本文档旧的修订版！
目录
Week 11
比赛简记
Max.D.
专题
学习了一点计算几何
比赛
一场atcoder,一场cf global round
rating小涨
题目
暂无
Hardict
专题
无
比赛
cf div2
题目
暂无
MountVoom
专题
无
比赛
打了atcoder，rating小涨。
题目
无
个人总结
陈铭煊 Max.D.
补题+学习
龙鹏宇 Hardict
补题+整理板子
肖思炀 MountVoom
补题，学点新东西
本周推荐
陈铭煊 Max.D.
来源：
标签：
思维题
题意：
给出一个$n(1\le n \le 10^6)$长的严格递增序列$h$，每一次找到满足所有$h_{i+1}-h_i\ge 2$的下标$i(1\le i< n)$，进行操作$h_i=h_i+1,h_{i+1}=h_{i+1}-1$，得到新的$h'$。然后再重复操作若干次，直到无法操作为止，求出最终的序列。
题解：
题意很简单，不过感觉真是想不到。
首先发现，每一次操作$1$的转移，顺序是没有什么关系的，或者说可以看做每一次随便挑选一对可变的$h_i,h_{i+1}$进行变换（这里变换是指让两者值最多相差$1$），然后再挑选一直到不能变为止。暂时不会证明，不过手动几个例子是很容易看出来的。
接下来我们安排一种变换轮次，每一次从左往右将新的$h_i$加入到轮次中来，到左边$1\sim i$序列无法变换，再加入下一个。对于每一个新加入的$h_i$，我们首先对$h_{i-1},h_i$进行一次变换，然后让序列$1\sim i-1$“消化”这个增加的$1$，接下来再变换$h_{i-1},h_i$…
很显然，考虑$1\sim i-1$中有唯一一对相邻相等元素$h_k,h_{k+1}$，消化的过程中，会消除了这对元素，产生了一对新的$h_{k+1},h_{k+2}$；考虑没有相邻相等元素，那么消化的过程中会在最左边产生一对新的相邻相等元素。
通过归纳，我们知道，因为一开始是没有相邻相等元素的，所以最后的相邻相等元素不会超过$1$对。
剩下的，就只用靠数学方法求解了。
评论：
赛场上其实想的很多，但没总结出这个最多一对的性质，其实打表已经比较明显了，以后还是注意好好观察。
龙鹏宇 Hardict
来源：
标签：
多项式卷积,NTT
题意：
先给定一个$f(x)=\sum_{i=0}^{n}c_{i}x^{i}$,然后求解$g(x)=f(x-\sum_{i}a_{i})=\sum_{i=0}^{n}b_{i}x^{i}$
输出$b_{i}$
题解：
$A=-sum{a[i]}$并取模变成求解$f(x+A)$少去正负计算
然后按$f(x+A)$每一项进行一个展开(会成一个三角表)
目标多项式系数$b_j=\sum_{i \geq j} c_i A^{i-j} C_i^j$
化解后有$j!A^jb_j=\sum_{i=j}^{n} \frac{c_{i}i!A^i}{(i-j)!}$
整体上$g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j=0}^{n-i}\frac{c_{i+j}(i+j)!A^{i+j}}{j!}$
这里令$k=n-(i+j),g(x)=\sum_{i=0}^{n}\frac{x^{i}}{A^{i}i!}\sum_{j+k=n-i}\frac{c_{n-k}(n-k)!A^{n-k}}{j!} =\sum_{k=0}^{n}\frac{x^{k}}{A^{k}k!}\sum_{n+k=i+j}\frac{c_{i}(i)!A^{i}}{(n-j)!}$
将$\frac{1}{j!}$当作一个翻转(两者都可),求$\sum_{i}c_{i}i!A^{i}x^{i}$与$\sum_{i}\frac{1}{(n-i)!}x^{i}$的卷积,然后取结果$n+i$项系数即可
肖思炀 MountVoom
来源：
标签：
树形dp，二分图最大权匹配，树哈希
题意：
给定两棵同构的树，需要找到一个对应关系使得相同的标号尽可能多。
题解：
树形dp，dp[i][j]表示把第一棵树的i结点和第2棵树的j节点对应起来所需要的最小花费。
转移的时候对它们的子树做一个二分图最大权匹配即可，这样总的复杂度仍然是$O(n^3)$
评论：
cmx鸽鸽写的时候树哈希被卡了，需要注意
