Codeforces623B
核心: 质因子必定是两边的数(+1, -1, 0) 不能全部取走。
然后直接暴力扫维护最小值。
暴力扫的时候写法很烦，边界出错导致挂了几次。
Codeforces621D
取两次对数，简单分情况讨论。
全部小于1的情况讨论错误，然后优先级一个地方维护错误，考场上fst.
新的idea: 系统Power函数可以支持到200^200左右上限的实数模糊比较精度，但还是最好不要冒风险用这个。
Codeforces618C
直接二关键字排序，依次取直到找到一个非0的输出即可。
对极角序理解出了问题，考场上强行乱搞惨遭fst
Codeforces618E
线段树维护坐标变换矩阵乱搞。
考场上完全推出了矩阵，然后用了树状数组，没出样例。
树状数组由于奇怪的累加机制，不能够支持矩阵这种左乘右乘不同这种情况，线段树维护懒标记可以轻松处理。
精度问题有点劲，全开long db会T，可以考虑部分中间过程开long db来一定提高精度。
Codeforces617D
没什么好说的题。
考场上赶时间直接YY情况上去，忽视了一种Case，惨遭fst
Codeforces615C
没什么好说的题。
双hash非溢出很慢的，400W左右的级别就不要强用了，尤其是用map维护的情况下。
TLE惨遭fst
Codeforces605C
线性组合->平面表示->凸包。
到某个点->到某个点的右上方(添加x,y坐标最大的两个点)
Codeforces487D
分块。
路径运输问题如果是定向的(记忆化搜索样)，直接对某一维分块，维护从这个块的一端到另一端的转移。
询问的复杂度与修改重构的复杂度的平衡。
Codeforces489F
Dp。
棋盘类问题的Dp可以写成现在在第i行，一些这一行的状态，每一行每一行整体转移。
f[i][j][k] 第i行，有j个1，k个0，每次一次性枚举2怎么分配，组合数转移。
Codeforces528E
n^2求三角形面积期望。
面积计算公式(点坐标)(AB + B C + C * A)/2
对于三项拆开，考虑叉积的分配率，前缀和维护。
Codeforces484C
置换后平移再置换可以看做是一个普通置换和全局shift置换的结合(当时没想到)
然后找找循环节就OK
Codeforces30E
Manacher+kmp
kmp可以求出s[i-k+1..i]与S[1..n]匹配的最大的k，扩展kmp则是求出s[i…i+k-1]与S[1..n]匹配最大的k
两种最基本的应用。
Codeforces482B
并查集删除一段数技巧，直接把l…r依次并到下一个的根上，每个数getfa之后得到的是它最右边未被删除的数。
Codeforces623D
最优化期望问题。
考场上完全想偏->HNOI2013那道题… 以为求出一个大概的询问循环节，然后排序乱搞。
sol出乎意料，暴力模拟T轮，每次拿出一个当前贡献期望最大的出来询问。
每次取出最大的元素可以用堆暴力维护，询问之后简单更新一下。
对此仍然持有贪心正确疑问，但是感觉很对(笑
Codeforces623C
二分技巧。
取的肯定是连续的一段，二分答案M。
连续一段O(n)check，其余的点必须投射到y轴。维护前缀和后缀y坐标极值。
二分的check必须小心写。
Codeforces623E
FFT优化Dp
Dp的合并是卷积形式，快速幂+fft加速。
fft取模任意质数的方法: 因为中间结果不会超过PPN，取三个日常用的fft取模质数相乘大于这个结果的。
对于每一个质数做一次fft，每做完一次乘法CRT合并一次还原。
可以通过奇妙的技巧避开高精度。
Codeforces622F
自然数幂和问题。
idea1: 直接拉格朗日插值法暴力即可，其间用奇妙技巧维护那个式子，复杂度O(k)。(没有及时想到的方法)
idea2: 问题转化为预处理伯努利数的前n项，直接多项式求逆搞。
UPD:由于模1e9+7，用模任意质数的方法，FFT常数乘以3，事实上，由于求逆过程中每一层实际上有两次高精度乘。
- 4 prime搞
- 3 prime 每一层合并两次。
事实上这些方法都不用管，(因为10^6即便朴素的fft都直接T掉) idea2并不很work.
idea2的会光荣的TLE在第8个点，事实上k稍微小一点(5w级别.. 51nod 序列V4)，跑得稍微比idea1快一点。
Codeforces626E
注意到中位数取两个一定比中位数一个劣。(两个缩成一个过程中，中位数变小，平均数不会变小)
然后贪心的原则肯定只取(n-d+1,n), (i-d+1,i)
二分平均数，分数规划二分出可能最大的平均数的d，check即可。
精度有点坑，开long double, 第一次二分60次左右可过。
惨遭fst
Codeforces626F
精妙的Dp(对我来说
首先将所有的数排序，每一个组的不平衡值之和最小和最大值相关。
于是每一个组可以看做2种状态: 有了最小值没有最大值(open), 有了最小值也有最大值(close)
于是枚举每个人，要么随便选择前面一个open组加上去，要么新开一个open组，要么选择把前面的一个close掉。
精妙之处在于状态的不平衡值是最小不平衡值(即用当前枚举的这个强行封口的值)
这样的话f[i][j][k]表示到了第i个数，有j个open, 最小不平衡值k的方案，可以发现最后更新的一定是f[n][0][i]
这样的话，没有open的组，所求的不平衡值也就是精确值了。
转移显然。
Codeforces625D
好想难码的数位乱搞题。
考虑枚举i位填几，由于对称性，可以求出n - i +1位的答案。
考虑到进位需要存是否进位的状态(从前往后扫的need和从后往前扫的res)
f[i][need][res]，到了第i位，目前需要i+1位往前进need的进位值，给n - i进了res的进位值, i扫到(n+1)/2就够了。
转移的时候trick是，如果n为奇数，那么(n+1)/2位所求出来的上下数的值必须一样。
然后考虑到可能两个数相加进位的情况，我写了两遍Dp(大体差不多，copy一下就可以。)
然后对于n为偶数的情况，最后只有f[(n+1)/2][1][1]和f[(n+1)/2][0][0]的答案可以被接纳(进位和需求必须相同)
奇数的话就[0/1][0/1]都可接纳(无关向
vp下写的，wa了几次finaltest(test14 2次，test26 1次)估计现场又要惨遭fst.
Codeforces618F
鸽巢原理。
记录两个数组的前缀和ai, bi，对于每个ai找到一个最大的bj满足bj<=ai
这样每个ai-bj一定都在0到n-1的范围内(需要fix的是如果an>bn，那么可能有很多个ai取了bn，从而影响取值范围，导致鸽巢原理失败，交换a,b即可)
而一共有n个ai-bj，因此一定会存在p,q满足ai-bj=ap-bq => ai-ap=bj-bq
这便是答案了。
感觉这题事后并不是很难，但是比赛的高压下加上题序偏后，这种转化并不很常见导致现场低ac率(严肃
突然又想起一些序列鸽巢原理的经典题好像都是前缀和转化然后定范围(噗
Codeforces620D
不知道自己在干什么系列。
简单变换一下交换两次的贡献就可以独立统计a，b了。
太常见的技巧，太显然的做法。
论脑子短路的严重危害。
Codeforces620F
暴力艹std系列。
看完sol最直接的感觉就是，我对莫队算法了解实在是浅薄。
莫队算法是可以去掉删除(左端点右移，右端点左移)
方法大概就是
对于左端点在同一个块的询问，单独拿出来，保持右端点递增。
我记录左端点的max值，每次处理询问时，只把max->r的这一段添加。
添加的过程中维护答案，这样可以处理处max->r对max->r这一段的贡献。
在添加完本次询问的max->r这一段后，我暴力扫l->max这一段就可以获得l->max到max->r的贡献。
这上面两步的复杂度都是保持了nsqrt(n)的。
最后暴力处理l->max到l->max的贡献，因为每一块的询问，左端点值的偏差不会超过sqrt(n)，所以这样复杂度也是对的。
这样就可以处理很多因为需要消除贡献而变得棘手的询问题。
这道题很明显可以用trie这么搞，复杂度就是nsqrt(n)logn
然后
我被n^2的短小精悍的暴力艹成sb.
Codeforces613C
并不难的构造题。
首先可以发现性质，假设有一条对称轴，那么如果出现了另一条对称轴，会在与第一条为中心对称的位置出现另一条对称轴。
所以这样做下去就可以发现最后的样子一定是均分的块(显然
和为偶数的时候，对称轴都不会经过某个珠子，这样暴力枚举分几份就好。
奇数的时候，对称轴必定经过珠子，且多条对称轴经过的珠子颜色相同，枚举经过哪种颜色的珠子，再枚举分几份就好。
实在是非常好想且写起来舒服的题目。
高压环境下的心态调整系列。
Codeforces630P
卡傻逼题上太久没当场A掉的题。
没什么意思，注意可以用大圆减去空白部分。
剩下的就是一些正弦定理和弓形面积公式的问题了。
WC 挑战NPC
前部分看vfk的题解搞完的。
后部分用了摇曳的黑科技带花树算法。
如果i,j有边，ran一个0到1的随机小数，a(i,j)=x, a(j,i)=-x
然后有很大概率这个矩阵的秩等于一般图的最大匹配。
完全适用于OI骗分嘛。求秩反而没有带花树直接艹快。
时限一紧，都只能随机一次qwq
调了调seed=2333才卡时限过掉。
ProjectEuler530
既然超过100人过了就随便写写好了。
第一步统计每个因子的贡献，变成sigma(gcd(d,i))的形式。
然后稍微变一下可以变出一个奇怪的东西，那个东西是可以n^(1/3)算出来的。
然后对这个求个积分，总复杂度大概是n^(2/3)，挺慢的。
Codeforces629E
当场打的时候1个小时左右发现周围景物开始旋转，再打下去药丸
提前一个小时弃疗，也就没搞这题。
事后看起来
也就一道树形Dp sb题罢了。
首先考虑每次询问的live地点和work地点的关系。
两种情况。
- live地点为work地点的祖先(先按深度swap一下)
很容易发现从live地点到work地点以后，折返的路线所添加的额外边的一端必须是work地点的子树内部的点(包括work地点)，另一端必须是全树节点减去live->work这一条链(包括所连的子树)节点的那些节点(画一张图就完事)
2.非上述情况，则他们会有一个lca，这样折返的路线的两段都必须是live地点的子树节点和work地点的子树节点。
因为要统计路径长度和，所以对于每个点都要Dp出其他点到它的距离和。
这个向下Dp一遍算出子树节点到它的距离和，再向上Dp一遍累加父亲方向上的答案即可。
然后两种情况都可以减减加加算出总答案，除个总方案数算出期望就可以了。
感觉最近改题期手感爆表，基本写完就能1Y。
Codeforces613D
残念题。
当时很明显知道是虚树，然后Dp想了很久不会转移。
后来还是想了很久，晚上硬着头皮乱写了一个，居然A了。
建出虚树后,
f[i][0]表示这个点没有与子树内的任何重要点相连的最小代价。
f[i][1]表示这个点只和子树内1个重要点相连的最小代价。
因为如果和子树内两个以上重要点相连，不管这个点是不是重要点，都会形成联通块。
特别的，如果i点本身是重要点，那么f[i][0]即是要把i连向虚树的父亲节点(中间可能有非重要点)的那条边的某个非重要点炸掉，f[i][1]则是爆掉所有的与i相连的重要点炸掉。
转移还是很复杂。
如果i是非重要点。
f[i][0]
有两种转移1.我的虚树的儿子全部取f[i][0],这样的话不用炸掉i就可以。2.虚树的儿子取min(f[i][0], f[i][1]),这样的话最后炸掉i就可以了(同时防止儿子子树形成重要点的联通块)f[i][1]
这样的话，就最多取一个儿子的f[i][1]，其他全部取f[i][0]于是先默认儿子全部取f[i][0]，然后找一个最小的f[i][1] - f[i][0]加上就可以了。
如果i是重要点。
那么其子树的所有点都不能有重要点相连(不然会形成联通块)，故全部取儿子的f[i][0]
然后如果是要f[i][0],那么我仍然需要付出炸掉i点与虚树上父亲的路径的某个非重要点的代价(这个可以预处理)
然后balabala写了170+行，居然也1Y了(一种树形Dp很好的错觉
Codeforces616F
拼接在一起->子串问题->后缀数组->height数组上乱搞。
其实转化之后就是一个裸的单调栈题。
写这题折腾了我挺久，犯了两个问题。
1.认识不清。每个极大矩形都可以被其代表元不重不漏的访问，不会因为底层而出现非最优情况。(是不重不漏枚举而不是贪心)
2.加的分隔符不能相同(很久没写了犯的一个巨大错误。
惨痛8Y
Codeforces628F
其实没什么好说的题。
注意询问区间如果是前缀区间的话，其实是可以算出每一个区间的固定值的。
然后暴力建图最大流。
Codeforces632D
直接埃式筛法那样把每一个数的约数出现了多少次记录下来就好。
然后比较约数出现次数最多的，如果相同，必定取较小的那一个(lcm对应)
最后更新答案就好了。
Codeforces632F
其实a[i][j]的本质就是i到j的路径的最小值的最大值。
于是找出这张图的一颗最小生成树，查看每一对(i, j)的路径上的最大值是不是等于a[i][j], check一下就好。