TopCoder
SRM630
Easy
如果有边答案至少为2，枚举根节点每个子树只能上来一个点，统计统计就行了。
Medium
考虑相邻的两个后缀，如果把他们同时去掉头一个字符的顺序就反了，就意味着这两个字符有严格偏序关系。
SRM631
Easy
把中间两行一行染黑一行染白就能满足，答案至多为2，暴力枚举一下即可。
Medium
排好序从左到右考虑，维护一个当前最后一只猫的位置以及最后一坨猫的位置，如果当前区间内有一个位置有一坨猫就可以都跑到那里去而不增加答案，否则就看能不能铺平，能铺平尽量往左省空间，不能铺平就往右集中。
Hard
LCT裸题，更简单的做法是把询问分块，每次对一块内的被询问过的所有点暴力建虚树，然后暴力做完这部分的询问。
Hard
SRM632
Easy
连续一段数一定每隔一个有一个2的倍数，每隔3个有一个4的倍数……每次把不是2的倍数的数提出来，剩下的数不断除2就行了。
Medium
贪心，从大到小考虑每条边，首先每条边的流量要大于比它小的流量之和，所以如果加了这条边之后源和汇可以联通就把它流满，否则在图中插入这条边。
Hard
考虑暴力DP，设f[x][y]表示所在行有x个点，另一行有y个点，则转移是选择对面的连续一段点都走掉，走长度为k的一段点方案数是$2^{k-1}$。这样做是$O(n^3)$的，转移式子写出来使劲推一下可以优化到$O(n^2)$。
SRM633
Easy
问题等价于木棒能否形成多边形，等价于判断长度之和要不小于最大值的两倍。模拟一轮，一轮过后最大值就不变了。
Medium
枚举根，设根节点是必选的，那么选任何一个节点都必须要选这个节点的父亲。所以构成最大权闭合子图模型，最小割解决。
Hard
单独考虑每一个质数，就变成了知道某两个数的最大值/最小值是多少求有没有解。最大值为某个值等价于要么这个数等于值且另一个数不大于这个值。以一个数等于某个值且另一个数不大于/不小于某个值作为变量，处理出其中的矛盾后，剩下的就是2-SAT问题。
SRM634
Easy
从小到大枚举有几个炒鸡顾客，然后让他们使劲买。看剩下的能否分配给其他的顾客即可。
Medium
把连线当作点做最小割即可，模型更应该说是一个二分图带权最大独立集。
Hard
经典的转转转问题。
SRM635
Easy
枚举相似折线的两个起点，再直接check即可。
Medium
如果现在已经知道了要重排哪些比赛的名次，很明显应该对应该重排的places和cutoff排序，按照这个顺序来一一匹配。现在places[i]>cutoff[i]的比赛一定是要重排的。然后不一定满足排序后places能不大于cutoff，这时就要贪心地选择一个满足places<当前cutoff的一个比赛，且cutoff最大，将这个比赛加入需要重排的集合。
SRM636
Easy
直接枚举横纵切法。
Medium
得到的图的结构是一个环加内向树的结构，所以联通块的期望数量就变成了环的期望数量，而容易想到环只可能是二元环。接下来问题就简单了，利用期望的线性性，枚举成环的两个点，再考虑剩下点有多少个是不能取的，将其对应的概率累加到答案里即可。
SRM637
Easy
对于对手已知的牌，从小到大排序后，如果手里有当前比他大的牌，就拿其中最小的管上。否则拿手里最小的牌去送。最后剩下的牌随机概率求出期望即可。
Medium
题目保证初始有一条路径，博弈的过程可以看作一个区间DP求子游戏的SG函数，但这样复杂度太大，可以发现障碍将游戏划分成了数个没有障碍的游戏，这样DP就可以少了一维。
SRM638
Easy
先把肯定没有的方块挖掉，再考虑每个联通块，看如果只保留这一块三视图是否一致。如果不存在联通块需要特判。
Medium
如果最小值+最大值>size，最大的就不能移动。否则最小值可以任意移动。这两种情况都是可以继续递归的。
Hard
最后燃尽的地方要么是一个端点要么是一个边的中点，端点也可以规约到边的情况。枚举一条边，BFS出两边的叶子到这条边的距离。再枚举两边点燃的距离不小于多少的叶子，只需要check在这些情况下最后燃尽的是否是枚举的这条边即可。
SRM639
Easy
有解的条件是x+y是完全平方数而且x,y都不等于2，之后贪心就好了。
Medium
首先行和列可以独立计算方案之后只要乘起来，假设计算行，先把每列的字符串离散化，这样就变成了一个一维的问题。
设$f[i][j]$表示最后是否可能只剩下$[i,j]$这一段，转移就枚举左边或右边往内翻多长，转移需要check一个子串是否是回文串，这个只需$O(n^2)$预处理出每个串是否是回文串即可。总体复杂度为$O(n^3)$。
SRM640
Easy
最小生成树
Medium
不妨设$n_1 > n_2$ ，则如果$ans=n_2$答案为$n_1n_2$。
左侧有$n_2-ans$个未匹配点，右侧有$n_1-ans$个未匹配点，匹配数不再增加意味着不能再有增广路，首先意味着未匹配点之间不能连边，再者对于每一个匹配，两侧节点不能同时与对应侧的未匹配节点相连。
接下来还有$d$的限制，即每个点的度数至少为$d$，且$d$不为$0$。意味着对于每个未匹配节点，都必须与至少d个匹配点连，故当$d+d>ans$时无解。
综上设$ans$个匹配中有$P$个左侧匹配点与右侧每个未匹配点相连，$Q$个右侧匹配点与左侧每个非匹配点相连，所以总边数即$P^2+Q^2+P(n_1-ans)+Q(n_2-ans)$，又因$P+Q=ans$，所以最后化简为$P^2+(n_2-n_1-ans)P+ans*n_1$。因为$n_1>n_2$，可以看出$P=d$即最大值。
SRM641~650
SRM651~660
SRM661~670
SRM671
Easy
f[i][j][k]表示前i个字符且有了j个空的表情和k个非空的表情，转移显然。
Medium
考虑折半，实际上是要让${a \over b} = {d \over c}$，枚举$c , d$的位置，拿一个map记录前面$a \over b$的方案即可。
SRM672
Easy
游戏实际上是有个$i$在不断增加，如果$i|n$且$i<n$，$n$加1，如果$i|(n - 1)$且$i<n-1$，则$n$减1。
所以做法只需先正着枚举$n$的约数$i$，再去倒着枚举n的约数$n \over i$。
Medium
先不考虑联通也不考虑标号，通过暴力等方法可以得出$n$个点有$2^{\frac{(n-2)(n-1)}{2}}$种图所有点的度数是偶数，证明也很好想，$n$个点一共$\frac{n(n-1)}{2}$条边，如果没有限制就有这么多自由度。现在强制让$n$个点的度数为偶数，相当于最后自由度少了$n-1$(总度数之和是偶数)，所以就是$2^{\frac{(n-2)(n-1)}{2}}$。
然后就是用经典的方法DP出考虑联通和标号的数量，这个只算出了都是偶度的情况，答案需要乘上$1+\binom{n}{2}$。意思是要么不变，要么选两个点连上或者删掉。
SRM673
Easy
枚举第一个人选什么马之后，剩下的是一个完备匹配计数的问题，然而每个人能匹配的马都是从小到大的一段。所以只要按人的权值从大到小选就能避免重复计数。
Medium
容易想出设$f[i][j][k]$表示$i$个点，根是第$j$个点，当前得分为$k$的方案数。直接暴力dp是$O(n^6)$的，暴力dp如下。
如果设$g[i][i-j+k] = \sum{f[i][j][k]}$，$h[i][j+k+1] = \sum{f[i][j][k]}$，上式可化为
这样dp就是$O(n^4)$的了。
SRM674
Easy
度数和必须为2n-2而且至少要有两个叶子，每多一个叶子会让直径少1。
Medium
经典问题，蚂蚁的相对顺序不会变，问的就是某时刻第K大的坐标，二分就行。
Hard
将物品二进制分组，变成一个01背包问题，而且每个物品的重量和价值需要再乘个2的幂次。
这是就能把相同的2的幂次放在一块转移，因为物品的重量很小，就可以设状态为还剩多少重量时的最大价值，这个重量不用存非常大。转移到第$2^k$层的时候也只用存所有$2^k$倍数的状态，稍微压压就可以了。
SRM675
Easy
构造，枚举几个部分有几个点。
Medium
把数值分块，这样就可以知道每个询问在那一块里面，再遍历一遍数组就可以知道具体的值。时间复杂度$O(Q(n+\sqrt{M}))$，空间复杂度$O(\sqrt{M})$。
SRM676
Easy
简单二分。
Medium
SG函数，找规律。
Hard
见费用流的对偶建模。
SRM677
Easy
枚举翻了几次倍，然后贪心。
Medium
枚举直径是多少，然后利用树DP计算直径不超过某个值的树有多少种。
DP的时候设$f[x][d]$为以$x$为根的子树且子树内的节点到根的距离不超过$d$的方案数，转移只需要枚举一下最深的那个儿子是谁以及深度是多少，就能利用直径长度的限制计算出其他儿子对答案的贡献。
SRM678
Easy
一轮排列至多把一个位置往前移动$n-D$格，所以把所有需要往前移动的距离除$n-D$的上取整的最大值更新答案。
Medium
先把点之间的包含关系去掉，留下一条x递增y递减的链。然后二分答案，可以知道T固定下每个点能覆盖的范围。贪心看所需的最小点数和m的关系即可。
Hard
设$a_i = x_i , b_i = \log p_i$，则要使得$\sum{a} \cdot e^{\sum{b}}$最小，由于这个函数的等值线是凸的，所以可以转化为$\sum{a} + k \sum{b}(k \geq 0)$，这个问题只需要考虑$k$的取值对物品的顺序的影响。
SRM679
Easy
简单树DP
Medium
预处理出所有三角形是否合法和内部的点数，枚举凸包的最左下方的点，然后DP。
Hard
最暴力的是$O(n^2m^2)$的，然而把其中的一个贡献可以拆开来分配从而得到$O(nm(n+m))$的做法。
SRM680
Easy
瞎DP一下最方便
Medium
显然当$2^k > n$时是无解的，可以先用小边构出来长度为$2^k$的链，然后把剩下边随便和某一个点连着就行。而长度为$2^k$的链本身就很好构造。
SRM681
Easy
二分答案后贪心，贪心即把区间排序后每次用能用的结束最早的区间。
Medium
生成序列的函数是可逆的。枚举重心暴力往两边扩的复杂度就是$O(n \log n)$。
Hard
考虑两个下标为$x , y(y - x > 1)$的数对答案的贡献。它们左边有$x$个数，中间有$y-x-1$个数，右边有$n-y-1$个数，若想要$v_x \cdot v_y$有贡献，必须要把它们中间的数字都干掉。所以有DP设$f[i][j][k]$表示左右各有$i,k$个数，中间有$j$个数时把中间的数字全部干掉的概率，转移就看被这一轮被干掉的是哪边的并计算对应概率即可。
SRM682
Easy
不合法的情况只有很少种，直接暴力。
Medium
如果是树答案是n-1-叶子数，树上多一条边考虑以环为根，能统计出一个叶子数。如果环上每个节点都有分支那么环必须缩成一个点，否则存在一点没有分支，这个节点就可以不合并从而形成一个二元环，也满足要求。
SRM683
Easy
环形均分纸牌，直接暴力枚举断点就行了。
Medium
两个数做变换实际上就是把每个质因子的幂次大的都移到LCM上，小的都移到GCD上。要让和最大也就是最大的数应该有所有质因子最大的幂次，次大的有次大的幂次，以此类推。
SRM684
Easy
枚举选择数的最大值和最小值，就知道了极差的最大值，也就知道了极差的最小值。然后在范围里面dp。
Medium
数字因数分解之后幂数的集合相等的数转移都是一样的可以合并，这样一个就只有100多种数字，就可以矩阵快速幂了。
SRM685
Easy
枚举初始元素，然后迭代。
Medium
标程的做法：按照Kruscal的方法，当某条边加入两个图都会减少连通块数时枚举一下加在哪边。这样枚举量只有$C(20,10)$。
Hard
一个图生成树为A，另一个为B，只需让它们之间连一条边生成树数量就可以变成A*B。所以随机生成2000个20个点的连通图，分别算出生成树数量。期望用4个这样的图乘起来得到答案，只需要折半枚举就可以了。实测这样做通过了所有数据。
SRM686
Easy
折半枚举
Medium
求$\sum_{k=1}^{n}{S(n, k)k^m}$，利用老方法变成递推$f[i][j] = \sum_{x}{\binom{S(i,x)}{j}}$，最后复杂度为$O((n+T)m)$。
SRM696
Easy
倒过来思考染色的过程，一旦某条边的一个端点没了色，它就不计入在此之后的代价。所以直接状压每条边是否满足有端点没颜色，转移就是枚举点取消它的染色。
Medium
挺麻烦的一个题，首先把点尽可能平分，使得?边都在左侧，先预处理右测每个子集的最大团，然后同样预处理左侧，把?先当做1。枚举左侧的团，然后就可以知道右侧能选的点集从而知道现在可以有的最大团。等价于如果左侧的团内的?边都取1，这个团的大小就能更新答案。最后这一部分暴力即可。
SRM697
Easy
$b_i$实际上是告诉了这个数至少占所有数乘积的$\frac{1}{b_i + 1}$。所以$\sum \frac{1}{b_i + 1}$ 若大于 1 肯定无解，小于 1 肯定有解，等于 1 的情况如果 $b_i$ 有重复，$a_i$就做不到不重复，所以无解。否则有解。
Medium
考虑计算每一个 $q_i$ ，拆开平方后需要枚举$j , k$两个小于 $i$ 的数，但是比较两个数的时候只要看第一个不同的位，所以可以枚举这两个数是从哪一位开始和 $a_i$ 不一样的，预处理这个数量后，再统计有多少个$d$满足 $a_i \otimes d > a_j \otimes d$，$d$只有$a_j , a_k$ 这两个数与 $a_i$ 第一个不相同的至多两个位是固定的，数量也很容易统计出来。
SRM698
Easy
枚举断点，DP求两个串的编辑距离。
Medium
求补，两个相离的凸包有且仅有两条内公切线，所以只要算切线的条数，枚举两个点求一下直线两边各有多少个点，就能算出这条直线会是多少种情况下的内公切线。
| Round | Easy | Medium | Hard |
|---|---|---|---|
| SRM630 | √ | √ | |
| SRM631 | √ | √ | √ |
| SRM632 | √ | √ | √ |
| SRM633 | √ | √ | √ |
| SRM634 | √ | √ | √ |
| SRM635 | √ | √ | |
| SRM636 | √ | √ | |
| SRM637 | √ | √ | |
| SRM638 | √ | √ | √ |
| SRM639 | √ | √ | |
| SRM640 | √ | √ | |
| SRM641 | √ | √ | |
| SRM642 | √ | √ | |
| SRM643 | √ | √ | |
| SRM644 | √ | √ | |
| SRM645 | √ | √ | |
| SRM646 | √ | √ | |
| SRM647 | √ | √ | √ |
| SRM648 | √ | √ | |
| SRM649 | √ | √ | |
| SRM650 | √ | √ | |
| SRM651 | √ | √ | |
| SRM652 | √ | √ | |
| SRM653 | √ | √ | |
| SRM654 | √ | √ | |
| SRM655 | √ | √ | |
| SRM656 | √ | √ | |
| SRM657 | √ | √ | |
| SRM658 | √ | √ | √ |
| SRM659 | √ | √ | |
| SRM660 | √ | √ | |
| SRM661 | √ | √ | |
| SRM662 | √ | √ | |
| SRM663 | √ | √ | |
| SRM664 | √ | √ | |
| SRM665 | √ | √ | |
| SRM666 | √ | √ | |
| SRM667 | √ | √ | |
| SRM668 | √ | √ | |
| SRM669 | √ | √ | |
| SRM670 | √ | √ | |
| SRM671 | √ | √ | |
| SRM672 | √ | √ | |
| SRM673 | √ | √ | |
| SRM674 | √ | √ | √ |
| SRM675 | √ | √ | |
| SRM676 | √ | √ | √ |
| SRM677 | √ | √ | |
| SRM678 | √ | √ | √ |
| SRM679 | √ | √ | √ |
| SRM680 | √ | √ | |
| SRM681 | √ | √ | √ |
| SRM682 | √ | √ | |
| SRM683 | √ | √ | |
| SRM684 | √ | √ | |
| SRM685 | √ | √ | √ |
| SRM686 | √ | √ | |
| SRM687 | |||
| SRM688 | |||
| SRM689 | |||
| SRM690 | |||
| SRM691 | |||
| SRM692 | |||
| SRM693 | |||
| SRM694 | |||
| SRM695 | |||
| SRM696 | √ | √ | |
| SRM697 | √ | √ | |
| SRM698 | √ | √ | |
| SRM699 |