====== Week 11 ====== ===== 比赛简记 ===== ===== Max.D. ===== ==== 专题 ==== 学习了一点计算几何 ==== 比赛 ==== 一场atcoder,一场cf global round rating小涨 ==== 题目 ==== 暂无 ===== Hardict ===== ==== 专题 ==== 无 ==== 比赛 ==== cf div2 ==== 题目 ==== 暂无 ===== MountVoom ===== ==== 专题 ==== 无 ==== 比赛 ==== 打了atcoder，rating小涨。 ==== 题目 ==== 无 ====== 个人总结 ====== ===== 陈铭煊 Max.D. ===== 补题+学习 ===== 龙鹏宇 Hardict ===== 补题+整理板子 ===== 肖思炀 MountVoom ===== 补题，学点新东西 ====== 本周推荐 ====== ===== 陈铭煊 Max.D. ===== ===来源：=== [[https://codeforces.com/contest/1392/problem/F|Codeforces Global Round 10 F. Omkar and Landslide]] ===标签：=== 思维题 ===题意：=== 给出一个$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 ===== === 来源： === [[http://acm.hdu.edu.cn/showproblem.php?pid=6061|HDU 6061]] === 标签： === 多项式卷积,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 ===== === 来源： === [[https://atcoder.jp/contests/abc175/tasks/abc175_d|D - Moving Piece]] === 标签： === 枚举，贪心 === 题意： === 给定步数和诸多环，求在某个环上走的最大收益。 === 题解： === 枚举每个点作为起点然后分类讨论，如果步数不够一圈就模拟一下找一个最大值。 如果够一圈则在模拟走一圈内的最大值和走多圈和余下步数的最大值取个最大值即可。 === 评论： === 分类没有处理好WA了很多发，这种简单题也要注意细节。