这是本文档旧的修订版！
目录
Week 11
比赛简记
Max.D.
专题
学习了一点计算几何
比赛
一场atcoder,一场cf global round
rating小涨
题目
暂无
Hardict
专题
无
比赛
cf div2
题目
暂无
MountVoom
专题
无
比赛
求求来点正常cf div1
遇见类似原题的题不要被轻易影响
题目
无
个人总结
陈铭煊 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
来源：
标签：
莫比乌斯反演
题意：
$G_u(a,b)=\frac{\varphi{ab}}{\varphi{a}\varphi{b}}$
求解$\sum_{i=1}^{n}\sum_{j=1}^{m}G_u(i,j)$
题解：
$gcd(a,b)=d,\varphi(ab)=\varphi(a)\varphi(b)\frac{d}{\varphi(d)}$
$G_u(a,b)=\frac{gcd(a,b)}{\varphi(gcd(a,b))}$
$ans=\sum_{d}\frac{d}{\varphi(d)}\sum_{a,b}[gcd(a,b)==d]$，可以看出是经典莫比乌斯反演问题
时间比较紧，需要线性预处理$1\sim n$逆元，进一步$\sum_{a=1}^n \sum_{b=1}^m [gcd(a,b)==d]=\sum_{i=1}^\frac{n}{d}\sum_{j=1}^\frac{m}{d}[gcd(i,j)==1]$，可以整除分块进一步优化
肖思炀 MountVoom
来源：
标签：
树形dp，二分图最大权匹配，树哈希
题意：
给定两棵同构的树，需要找到一个对应关系使得相同的标号尽可能多。
题解：
树形dp，dp[i][j]表示把第一棵树的i结点和第2棵树的j节点对应起来所需要的最小花费。
转移的时候对它们的子树做一个二分图最大权匹配即可，这样总的复杂度仍然是$O(n^3)$
评论：
cmx鸽鸽写的时候树哈希被卡了，需要注意
