洛谷P4781 题解公式 inline int FastPow(int x, int y) { if (y == 1) return x; if (!y) return 1; int tmp = FastPow(x, y >> 1) % mod; return tmp * tmp % mod * (y & 1 ? x : 1) % mod; } inline void Lagrange() { go(i, 1, n, 1) { up = down = 1; go(j, 1,
作者： 1016142506
洛谷P3834 教程视频 #pragma once #include<algorithm> #include<bitset> #include<cmath> #include<cstring> #include<cstdlib> #include<cstdio> #include<complex> #include<fstream> #include<iostream> #include&
题目传送门 性质 删除重心后所得的所有子树，节点数不超过原树的1/2，一棵树最多有两个重心；2.树中所有节点到重心的距离之和最小，如果有两个重心，那么他们距离之和相等； 两个树通过一条边合并，新的重心在原树两个重心的路径上； 树删除或添加一个叶子节点，重心最多只移动一条边； 一棵树最多有两个重心，且相邻。 思路 如果找到只有一个重心，那么直接删一个重心的直连边然后加回去就好了。 如果找到两个重心，那么在其中一个重心上找到一个直连点不是另一个重心，删除连另外一个就好了。 如何求树的重心？ 先任选一
原理 https://blog.csdn.net/alexfaker/article/details/90199074 模板 https://www.cnblogs.com/iloveori/p/12526461.html#%E8%A7%82%E5%89%8D%E6%8F%90%E7%A4%BA%EF%BC%9A%E8%AF%B7%E4%B8%8D%E8%A6%81%E5%9C%A8%E8%B4%9F%E6%9D%83%E5%9B%BE%E4%B8%AD%E7%86%9F%E7%BB%83%E7
原题链接 https://codeforces.com/contest/1406/problem/D 思路 样例中a=2,-1,7,3; 差分为-3,8,-4; 设(b[1]=x)+(c[1]=y)=a[1]; ∵b[1]=c[2]>=…>=c[n] x+(y-3)=(x-1)+(y-2)=(x+1)+(y-4)=…=a[2] ∴b[2]=x c[2]=y-3为最优解 其他的解都会导致b[n]或者c[1]变大 使最后答案不是最小 即:差分>0时,将差分的