“X大爷，怎么快速提高姿势水平啊”

“做100道TC的hard！”

嘛...那就做做试试看吧，虽然好像一道都不会做的样子T^T

[upd 6.22]最近进度略慢..上午做完题了之后下午就不想写题马上就要会考了多校题还没有出..感觉药丸啊

[upd 6.23]各种deadline缠身啊..会考前抽时间再尽可能多做几题吧..会考后应该就要花时间补补计算几何网络流做做历届题目什么的..这个坑填完我就要回老家结（种）婚（田）辣..断更预定

[upd 6.24]脸黑..怪我喽

[upd 6.25]算上TCO的题差不多算是做到了100道hard？姑且算是撒一下花..以后再做到SRM的题还是会更到这个博客上的> >

现在做了几题

【SRM658】DancingForever 直接跑匈牙利算法，当一个点无法匹配的时候说明前面已经形成了一个满足条件的匹配，直接输出就好了。如果存在完备匹配则最终的匹配结果就是答案。感觉还是挺巧妙的，时间复杂度[tex]O(n^3)[/tex]

【SRM657】RookGraph 如果两个棋子之间存在同一行同一列关系，那么在他们之间连上一条边。对于每一个联通块分开来考虑，一个联通块我们假设相邻的两个棋子在同一行，那么就可以还原出这一个联通块有几行几列（如果在同一列就反过来），最后就是一个普及组DP了，注意特判孤立点的情况。代码写的简直要死，时间复杂度[tex]O(n^3)[/tex]

【SRM656】ForkliftTruckOperator 把连续的相同的合并起来，可以发现当段数很多的时候可行的操作唯一，段数为2的情况可以先预处理出来，段数为3的时候移动中间那段只可能移动到两段比较优，段数为3-5的情况讨论所有可行的移动方法（段数为3移动中间那段的时候贪心），直接搜就好了。

【SRM654】TwoEntrances 开始预处理出把两个入口路径上的每一个点延伸出去的子树放满的方案数以及子树大小，然后[tex]dp_{i,j}[/tex]表示已经放满了路径上第[tex]l[/tex]个位置到第[tex]r[/tex]个位置已经延伸出去的子树的方案数，转移的时候用组合数乘一下，时间复杂度[tex]O(n^2)[/tex]

【SRM653】RockPaperScissorsMagic 可以设出九个变量（012位置上的石头剪刀布数量），列出所有约束条件可以得到七个等式，所以可以枚举其中两个变量的值，然后高斯消元得到每一个变量的值，判断合不合法，如果合法组合数求出答案，可以先把系数矩阵预处理成上三角矩阵，复杂度是[tex]O(9^3+9^2n^2)[/tex]

【SRM650】LegendOfAdlez 开始把所有不经过锁上的边就可以相互到达的点集缩成一个点，这样就得到了一棵树，然后把以终点为根的子树删掉，这个子树里的点的钥匙可以随意摆，最后的答案乘上2的幂次就好了。令[tex]dp_{i,j}[/tex]表示以[tex]i[/tex]为根的子树最多可以消耗掉[tex]j[/tex]把钥匙的方案数（包括打开[tex]j[/tex]到它的父亲那条路的钥匙），用一个[tex]O(n^3)[/tex]的DP就可以得到答案了。

【SRM649】CartInSupermarket 和去年PKUSC的一道题有点像，首先二分答案，接着对于每一个数，求出在限定时间内消完的最少分裂次数，这个同样可以二分，即要计算限定分裂次数最少需要多少时间消完，这个是可以直接贪心的，即分裂是以类似完全二叉树的形式分裂，暴力出分裂的深度直接算就好了，复杂度是[tex]O(n\log^3 a_i)[/tex]。

【SRM648】Fragile 反正就是花样DP...先DP出大小为[tex]n[/tex]的连通图个数，令[tex]A_{i,j,k}[/tex]为1号点所在边双大小为[tex]i[/tex]点数为[tex]j[/tex]边双个数为[tex]k[/tex]的图的个数，暴力转移就可以得到大小为[tex]n[/tex]桥个数为[tex]j[/tex]的无向联通图个数了，最后再跑一遍DP即可得到答案，时间复杂度[tex]O(n^5)[/tex]

【SRM647】ConvenientBlock 感觉我真的只有普及组的网络流水平啊..首先把不能被出发点到达的点以及不能到达终点的点删掉，然后每一条边[tex](u,v,cost)[/tex]连上两条边[tex](u,v,cost)[/tex]以及[tex](v,u,inf)[/tex]（限定了存在到达关系的两条边不能同时割），跑最小割就是答案了。

【SRM645】AquaparkPuzzle 考虑容斥，先要算出集合[tex]U[/tex]出现次数不到两次的方案数[tex]f_U[/tex]，可以先只考虑取的集合和[tex]U[/tex]有交的取法，令[tex]dp_{i,j}[/tex]表示取了集合[tex]i[/tex]用了[tex]j[/tex]次操作的方案数，直接枚举子集DP即可，最后再排列组合算出[tex]f[/tex]数组，再容斥一下就可以得到答案了，时间复杂度[tex]O(n4^n)[/tex]。

【SRM644】SquareOfSquareMatrix 把矩阵当成邻接矩阵，相当于要计算最长链为1的有向图个数（形状就是二分图）。可以把图分成和给定的边相关联和不关联两部分（如果不考虑方向的话就是联通和不连通），令[tex]f_i[/tex]为大小为[tex]i[/tex]和给定边不关联的图的个数，[tex]dp_i[/tex]为在与给定边相关的点上再加上[tex]i[/tex]个点后的图的个数，容斥+DP就好了，时间复杂度[tex]O(n^2)[/tex]。

【SRM642】WheelofFortune 令[tex]dp_{i,j,k}[/tex]表示[tex]i[/tex]轮后，第0个位置为[tex]j[/tex]时，第[tex]k[/tex]个位置期望是多少，[tex]f_{i,j}[/tex]为[tex]i[/tex]轮后，第[tex]0[/tex]个位置为[tex]j[/tex]的概率，直接暴力DP就好了。时间复杂度是[tex]O(n^3)[/tex]

【SRM641】BitToggler 1000分的题好难啊感觉根本不会做...把答案的期望拆开，每一次只考虑把指针从[tex]i[/tex]移动到[tex]j[/tex]的贡献。这时其他[tex]n-2[/tex]个位置可以视为相同的，令状态为[tex](a,b,c)[/tex]表示其他[tex]n-2[/tex]个位置和[tex]i[/tex]值一样的个数，[tex]j[/tex]是否和[tex]i[/tex]一样，指针是否在[tex]i[/tex]这个位置，高斯消元即可得到每一个状态到终止状态期望产生多少次[tex]i[/tex]到[tex]j[/tex]的移动，最后累加答案就好了，时间复杂度[tex]O(Tn^3)[/tex]

【SRM640】TwoNumberGroups 一道难度全在算复杂度的1000分。考虑每一个质因子把答案的贡献拆开，那么[tex]A_i-B_j[/tex]是[tex]p[/tex]的质数当且仅当[tex]A_i \mod p=B_j \mod p[/tex]，于是直接枚举小于[tex]\sqrt{10^9}[/tex]的所有质数，对于每一个指数把模数相同的位置分到一组统计答案，最后再把差值中剩下的大于[tex]\sqrt{10^9}[/tex]的部分加上，这样复杂度是[tex]O(nm \log A_i)[/tex]的，因为每一对[tex](i,j)[/tex]只会被枚举到它们差值的质因子的个数次。

【SRM638】CandleTimer 答案只可能取为两个叶子节点之间的距离或者距离的一半。枚举哪两个叶子节点之间的距离（或一半）作为答案，剩下的叶子在不影响到选定叶子之间路径的情况下能点就点，最后求一遍当前方案能量出的时间与枚举的答案比较一下，如果相同说明就是可行的。至于求一个方案烧完的时间可以通过把所有选定的叶子节点作为起点跑最短路，然后分每一条边求这条边上最晚被删除的节点更新答案得到。时间复杂度[tex]O(n^3)[/tex]

【SRM637】ConnectingGame 先把图转成八连通，相当于询问是否存在一条从最左端到最右端的路径以及一条最上方到最下方的路径使得这两条不想交，可以发现如果是四联通的话一定是会相交的，枚举路径在四联通情况下相交的那个[tex]2\times 2[/tex]方格，问题就变成了判断是否可以从这个方格的四个小格出发得到四条分别到四个边界的互不相交的路径，这个可以拆点网络流。时间复杂度为[tex]O(nmA^2)[/tex]其中[tex]A[/tex]为颜色集大小。

【SRM636】Sortish 开始一直在想奇怪的状压DP，一看到题解的复杂度就清醒了T^T奇怪的meet in middle。首先把14个位置划分成两个大约相等大小的部分，这样至多有[tex]\binom{14}{7}[/tex]种划分，然后每一个部分爆枚排列计算对逆序对的贡献，把前半段丢进map后半段在map里查询，预处理一下每一个位置取哪个对答案的贡献就好了，复杂度挺玄学的就不写了。

【SRM635】ColourHolic 开始一直在想着奇怪的DP，然后好像还要容斥什么的复杂度飞起...计数题我怎么可能会做呢只好去膜题解了。把颜色两两分组，那么方案肯定可以表示成两种颜色交替的一段，另两种颜色交替的一段交替出现。枚举方案最开头的两种颜色，去掉开头一段只有一个的情况，然后再枚举方案有几段，就转化成了把两种颜色分成交替出现的若干段的方案数，再枚举长度为奇数的段数，用组合数算一下就好了，因为至少两种颜色不多于200，所以去掉一些显然不可能的循环之后复杂度可以降到[tex]O(aN)[/tex]，其中[tex]a[/tex]为出现较少的两种颜色数量和。

【SRM633】GCDLCM 玛雅我居然能自己想出来1000分..把每一种质因子分开来考虑，然后把每一个位置建若干个点，如如果选取了[tex]f_{i,j}[/tex]这个店表示第[tex]i[/tex]个位置的幂次小于[tex]j[/tex]，如果不选说明大于等于[tex]j[/tex]，然后随便YY一下建图就可以上2-sat了。复杂度似乎是[tex]O(nm\log C_i)[/tex]。

【SRM631】TaroTreeRequests 裸LCT居然有1000分..加边删边权在边上的路径最小值，每条边新建一个点跑LCT就好了。

【SRM629】CandyDrawing 令[tex]dp_{i,j}[/tex]为前[tex]i[/tex]堆取了[tex]j[/tex]颗糖果的方案数，那么有[tex]dp_{i,j}=i \times dp_{i-1,j-1}+dp_{i-1,j}[/tex]，那么可以发现[tex]dp_{n,k}[/tex]是关于[tex]n[/tex]的[tex]O(k)[/tex]次多项式，暴力跑一些然后插值出多项式就好了。时间复杂度[tex]O(k^2)[/tex]

【SRM628】DoraemonPuzzleGame 先按照[tex]Y_i[/tex]从小到大排序，令[tex]dp_{i,j}[/tex]为后[tex]i[/tex]个level中有[tex]j[/tex]颗星的概率，那么当level数足够的时候显然是直接取到有星为止，当level数不够的时候则都要取到两颗星，记忆搜即可。

【SRM627】LaserTowersDiv1 神最小割...把所有出发点按照横着和竖着分成源和汇，然后边权是在这条边之后可以取到的最大值减去割掉这条边之后的最大值，为了防止出现多次转弯的情况把每一个点拆成两个点分别连横着的边和竖着的边，具体题解可以看官网http://apps.topcoder.com/wiki/display/tc/SRM+627

【SRM626】ReflectiveRectangle 大家喜闻乐见的900分题..式子写出来反演一下可以得到答案是[tex]\sum_{d|n}d^2 \mu (d) \frac{m(m+1)(2m+1)}{6}(x^2+y^2)[/tex],其中[tex]n[/tex]是反射次数+2，[tex]m[/tex]是[tex]\frac{n}{d}[/tex]，特判反射数为奇数的情况（无解），莫比乌斯函数直接暴力算，时间复杂度似乎是[tex]O(n^{\frac{3}{4}})[/tex]

【SRM625】Seatfriends 听说当了B队队长精神亢（萎）奋（靡），什么题都做的（不）出来了...一道傻逼题思考人生了一个小时最后还去看了题解简直人生污点..令[tex]dp_{i,j}[/tex]表示前[tex]i[/tex]个人坐到位置上一共有[tex]j[/tex]段，空隙长度可以直接当做一，然后最后再把剩余的长度给插进去，所以就可以直接DP了，时间复杂度[tex]O(n^2)[/tex]

【SRM624】TreeColoring 和HNOI那道数据结构题差不多...然后就裸上树剖就行了。

【SRM622】FibonacciXor 数位DP，令[tex]dp_{i,j,k}[/tex]，[tex]f_{i,j,k}[/tex]分别表示考虑前（后）[tex]i[/tex]位，当前数和原数大小关系为[tex]j[/tex]，最后（前）一个数是[tex]k[/tex]的方案数的奇偶性，处理出来这两个数组之后直接合并就好了。

【SRM621】StringsNightmareAgain 先处理处后缀数组，然后对于后缀数组上每一个位置[tex]l[/tex]先二分从这个位置开始最长的满足条件的子串的长度，假设当前二分的值为[tex]i[/tex]，可以再二分出字典序最大的和这个后缀的LCP长度大于等于[tex]i[/tex]的后缀，假设在sa中的位置是[tex]r[/tex]，那么只要满足[tex][l,r][/tex]中下标最小值和下标最大值之间的差大于等于[tex]i[/tex]，[tex]i[/tex]就是可行的，统计答案的时候把之前出现过的减掉就好了，时间复杂度[tex]O(n\log^2 n)[/tex]

【SRM620】PerfectSquare 大家喜闻乐见的800分傻逼题。每一个位置取还是不取设一个变量，然后分每一个质因子考虑就可以列出一些异或方程，解有几个自由元就好了。

【SRM619】SimilarSequencesAnother 陈老师讲过这题然而我根本没听，然后就习惯性的以为是容斥了..结果居然是DP of DP。先考虑求LCS的DP，然后可以发现考虑第[tex]i[/tex]位的时候只需要考虑DP数组中的五个位置的值以及两个字符串最近两个位置（共四个位置d）的大小相等关系。然后就压一下数组DP就行了，超神的一道题。

【SRM618】MovingRooksDiv1 按照列编号从大到小的移动到目标位置，假设当前我们要把[tex]i[/tex]从[tex]l[/tex]移动到[tex]r[/tex]，可以采用贪心的策略，每一次找到[tex][l,r][/tex]中权值小于[tex]i[/tex]的最大值的位置[tex]where[/tex]，然后把[tex]i[/tex]移动到[tex]where[/tex]，正确性还是挺显然的？没有仔细想证明。

【SRM617】FarStrings 感觉这道800分挺难的？先逐位枚举答案，然后相当于要判断确定了一个前缀的情况下的是否可以产生一个可以得到编辑距离为给定值的字符串，可以发现一定有一个字符没有出现过，所以可以产生的最大编辑距离为后面所有待定字符都是空缺字符，最小则为全部和原串一样。所以就可以枚举最后和原串一样的后缀有多长，中间全部填上空缺字符，然后算编辑距离看是不是和给定值相等。时间复杂度是[tex]O(26n^5)[/tex]，应该是可以进一步优化的。

【SRM616】ThreeLLogo 感觉和书法家神似啊..如果有一根扫描线从上往下扫过整个图形，可以发现每一个L都有四个状态，令[tex]dp_{i,j,k,k1}[/tex]为当前扫描线在第[tex]i[/tex]行，三个L的状态分别为[tex]j,k,k1[/tex]时的方案数，[tex]m+1[/tex]表示已经放完了，0表示还没放，其余表示当前位置，最后一种状态横着一条暴力枚举后就变成[tex]m+1[/tex]了所以不必压入状态，然后暴力DP就好了，注意去一下重。

【SRM615】AlternativePiles 似乎满足条件的序列当且仅当任意一个前缀中R的个数都要比G的个数多0到[tex]m[/tex]个..然后就可以直接DP了，时间复杂度[tex]O(nm^2)[/tex]

【SRM614】TorusSailing 这个1000分还是挺简单的..关键的两行只有出发点所在行和终点所在行，而中间走的过程每一行是完全相同的，可以直接预处理出走[tex]i[/tex]行横向移动[tex]j[/tex]个单位的概率，然后直接高斯消元即可。

【SRM613】TaroCheckers 大家喜闻乐见的900分傻逼题。令[tex]dp_{i,j,k}[/tex]表示当前是第[tex]i[/tex]列，有[tex]j[/tex]个分配给L限制的格子还没有被取走，有[tex]k[/tex]个R限制还没有放入棋子，然后直接转移就好了。

【SRM612】LeftAndRightHandedDiv1 大家喜闻乐见的900分傻逼题。如果既有L也有R最小值一定为1，枚举哪一个R不移动，那么其他的所有R一定是贪心的移动到这个R的两边，维护分界线，可以发现随着枚举的下标的增大分界线是单调的，预处理个前缀和直接算就好了，时间复杂度[tex]O(n)[/tex]

【SRM611】ElephantDrinking 去年队爷们清华集训之前的模拟题里有，那个时候自己是想出来的然而现在已经忘了，似乎是枚举分界线然后花样DP？

【SRM610】MiningGoldHard 显然横坐标和纵坐标是可以拆开的，所以分别考虑。令[tex]dp_{i,j}[/tex]为现在是第[tex]i[/tex]天，人在第[tex]j[/tex]个位置的最优值，可以发现[tex]dp_{i}[/tex]是一个一次分段函数，至多只有[tex]i+1[/tex]段，就直接维护每一段就行了，时间复杂度[tex]O(n^2)[/tex]。

【SRM609】LotteryTree 好难写的题啊..令[tex]dp_{i,j,k}[/tex]表示以[tex]i[/tex]为根的子树，最开始一段为[tex]\frac{j}{k}[/tex]是否可行，然后合并的时候可以用匹配来实现，枚举开头的一段，如果第[tex]a[/tex]个孩子可以放在第[tex]b[/tex]个位置就连一条边，如果存在完备匹配说明这个状态是可行的，状态数可以证明是[tex]O(np)[/tex]的然而我不会。

【SRM608】OneDimensionalRobot 大家喜闻乐见的900分傻逼题，先枚举[tex]l[/tex]再从大到小枚举[tex]r[/tex]，显然如果一个点触碰到了边界，在[tex]r[/tex]接下来的枚举过程中它就将一直触碰到边界，所以只要维护当前最后一个边界的位置就行了。预处理一个后缀最小值和最大值的位置，每一次贪心的走到那个位置，时间复杂度[tex]O(n^2)[/tex]

【SRM605】AlienAndPermutation 令[tex]dp_{i,j,k}[/tex]表示当前DP到第[tex]i[/tex]个位置，值为[tex]j[/tex]用了[tex]k[/tex]次修改的方案数，枚举下一个位置用什么数字，然后判断一下能不能放就好了，[tex]O(n^4)[/tex]居然只要0.5s也是挺惊讶的，听说可以优化到[tex]O(n^3)[/tex]但是既然已经过了就没有去看。

【SRM603】SumOfArrays 大致就是求[tex]\sum_{i=0}^n \max (A_i,B_{n-i})[/tex]，可以每一次值考虑每一位中第[tex]i[/tex]个1的贡献，设一个阈值[tex]key[/tex]，当[tex]i \leq key[/tex]的时候直接跑FFT，否则直接暴力。复杂度挺玄学的但是跑的挺快。

【SRM602】BlackBoxDiv1 公式题..感觉不错哦..

【SRM601】WinterAndShopping 大家喜闻乐见的950分傻逼题，令[tex]dp_{i,j,k}[/tex]为当前时刻为[tex]i[/tex]，当前开的唯一一家店还有[tex]j[/tex]个第一种气球，[tex]k[/tex]个第二种气球，然后有两家店同时开的时候可以直接排列组合把中间一段算好又变成只有一家店开的情况，分类讨论一下直接推过去就好了。

【SRM600】LotsOfLines 大家喜闻乐见的900分傻逼题，只要求[tex]y=ax+b[/tex]与[tex]y=ix+j(i \leq a, j\leq b)[/tex]的交点个数就行了，即求[tex]\frac{b-j}{a-i}[/tex]的取值个数，只要预处理出[tex]k1 \in [1,i],k2 \in [1,j][/tex]且[tex]\gcd (k1,k2)=1[/tex]的对数就行了。

【SRM599】SimilarNamesCustom 把给定字符串的前缀关系表示出来可以得到一棵树，令[tex]dp_{i,j}[/tex]表示以[tex]i[/tex]为根的子树对约束的满足状态为[tex]j[/tex]时的方案数，每一个约束的状态有三种：0.两端均不在子树中。1.较长的在子树中。2.都在子树中。然后直接转移就好了，时间复杂度大约是[tex]O(n6^m)[/tex]。

【SRM598】TPS 枚举一个位置放，然后以这个位置为根，深度不同的节点一定不同。一个节点的两个孩子是不同的当且仅当这两个孩子的子树中至少有一个位置放了定位。所以就可以直接DFS一遍推得答案。

【SRM597】LittleElephantAndBoard 这种题居然只有900分。。感觉我的计数水平没什么救啊。除了第一列以外其他列一定有一个必须放的颜色，用哪个颜色来表示这一列可以得到一个序列，可以发现每一个这个序列对应着两种合法方案，可以枚举序列最开始的颜色以及序列中相邻的这种颜色的间隔长度为奇数的段数，用排列组合算就好了。

【SRM596】SparseFactorial 要计算对于每一个[tex]i[/tex]，满足条件且模[tex]p[/tex]为[tex]i[/tex]的最小的数，可以分每一个质因子考虑，这样就只需要算模[tex]a^b[/tex]的答案。可以从小到大枚举[tex]k[/tex]，再枚举和[tex]k^2[/tex]同余的所有[tex]i[/tex]，把[tex]i-k^2[/tex]中的[tex]a[/tex]的个数累加到[tex]i[/tex]中，如果此时[tex]a[/tex]的数目已经大于等于[tex]b[/tex]了，那么只要模[tex]a^b[/tex]为[tex]i[/tex]的数[tex]n[/tex]大于等于[tex]k^2+1[/tex]，它就是满足条件的。时间复杂度[tex]p\log p[/tex]。

【SRM595】Constellation 感觉是很老的思路了..不过这题也够老了。枚举每一条边，它在凸包上当且仅当它的一侧没有点且这条边上没有点，然后分哪一侧没有点分别计算贡献（叉积的顺序不一样）。

【SRM593】WolfDelaymasterHard 大家喜闻乐见的1000分傻逼题，暴力DP是[tex]O(n^2)[/tex]的，可以发现右端点为[tex]i[/tex]时，左端点可行的取值区间不超过[tex]O(\log n)[/tex]段，用个双向链表维护这些区间就好了。

【SRM592】SplittingFoxes2 好神的题..感觉对DFT有了新的了解..作为一个背代码选手感觉自己的姿势水平实在捉急。先DFT，然后对每一个位置开方，对每一个得到的数组都IDFT然后判断是不是合法。这样最多有[tex]2^n[/tex]个要判断的数组，可以发现如果最终的答案是对称的，DFT得到的也是对称的，所以只要枚举[tex]2^{\frac{n+1}{2}}[/tex]种数组就好了。

【SRM591】StringPath 大家喜闻乐见的900分傻逼题，轮廓线DP，状压每一列已经DP过的最后一行的那个格子分别能不能被两个串到达，然后分这个位置两个串的字符是不是一样这两种情况暴力DP，时间复杂度[tex]O(nm2^{2m})[/tex]。

【SRM590】FoxAndCity 和切糕几乎一模一样的网络流题，每一个点拆成[tex]n+1[/tex]个分别表示最终和1号点的距离，然后每个点拆出来的点连成一条链，出边边权设为当前距离的代价，如果两个节点直接存在边，那么限制是如果一个点的距离为[tex]i[/tex]，另一个点的距离不得大于[tex]i+1[/tex]，连上边直接最小割就好了。

【SRM589】FlippingBitsDiv1 大家喜闻乐见的900分傻逼题，虽然写的意外的辛苦..分[tex]m \leq \sqrt n[/tex]和[tex]m > \sqrt n[/tex]考虑，前者可以状压最近[tex]m[/tex]字符进行DP，后者可以枚举每一个[tex]k[/tex]是否翻转然后贪心。

【SRM588】GameInDarknessDiv1 大家喜闻乐见的1100分日狗题，想了半天记忆搜结果是结论题...如果存在一个点距离A的距离至少比B大2，且以这个点为根的时候存在至少三颗深度大于等于三的子树..证明看起来好烦就没有看..

【SRM587】ThreeColorability 把Z当成1，N当成0，那么一个局面可行当且仅当可以给每行每列分配一个权值使得每一个格子的值为它所在行异或上所在列，所以直接诸位枚举然后DFS判断就好了。

【SRM586】StringWeight 一个串是满足条件的当且仅当这个串中出现的字母种类数尽可能的多且每种字母都是连续的一段。令[tex]dp_{i,j,k}[/tex]表示前[tex]i[/tex]个串，用了[tex]j[/tex]个字母，用完了[tex]k[/tex]个字母，每一次枚举当前串有多少种字母是开头，多少种是结尾，多少种既是开头也是结尾然后贪心的转移，时间复杂度似乎是[tex]O(26^5n)[/tex]然而跑的飞快（2ms）。

【SRM584】FoxTheLinguist 大家喜闻乐见的900分傻逼题，把图建出来跑斯坦纳树就好了。

【SRM583】RandomPaintingOnABoard 期望题好难啊..把问题转化成每一个时刻没有放完的概率和，然后再容斥一下，每一次枚举较小的一维哪些没有放完，然后DP另外一维求出不能选的格子的和为[tex]i[/tex]，不能选的行列和为奇数（偶数）时的方案数，统计答案就好了。

【SRM581】YetAnotherBoardGame 感觉我现在的智商也就只能做做这种傻逼题了...枚举第一行的所有数是否翻转，然后DFS每一列，每一列哪些位置需要翻转是确定的，可以暴力枚举这一列翻转的数是哪一种操作然后递归下去，当出现冲突的时候就可以剪枝了，时间复杂度是[tex]O(2^{n+m}m)[/tex]但是常数很小。

【SRM580】WallGameDiv1 可以发现一定存在一种最优方案每一时刻每一层的障碍是一个连续的区间，令[tex]dp_{row,i,j,k,a,b}[/tex]为棋子在第[tex]row[/tex]行第[tex]i[/tex]列，区间[tex][j,k][/tex]无法到达下一层，棋子可行的移动方向集合为[tex]a[/tex]，当前是[tex]b[/tex]的回合的最大值，然后DP即可。 

【SRM579】RockPaperScissors 然而概率题完全不会做..令[tex]dp_{i,a,b,c}[/tex]表示已经摇出了[tex]a[/tex]个石头，[tex]b[/tex]个剪刀，[tex]c[/tex]个布后第[tex]i[/tex]个骰子依然存在的概率，这个可以用一个[tex]O(n^5)[/tex]的DP求出来，然后累加答案就好了。

【SRM578】DeerInZooDiv1 这题和某场弱省互测的题很像（或者应该反过来说？），直接枚举割边分成两棵树，然后枚举两棵树的根然后跑DP就好了，转移用最大权匹配来实现。为了降复杂度可以记忆搜，令[tex]dp_{a,b,c,d}[/tex]为一棵树处于[tex]a[/tex]点另一棵树处于[tex]b[/tex]点，[tex]a[/tex]的父亲为[tex]b[/tex]，[tex]c[/tex]的父亲为[tex]d[/tex]的答案，时间复杂度挺玄学的我懒得（不大会）算。

【SRM577】BoardPainting 虽然肯定是网络流但是好难啊QAQ还有什么方法可以拯救我普及组级别的网络流水平...如果把每一次的起止边当成割边的话，可以发现每一个合法方案把所有和白色相邻的横边与和白色相邻的纵边割开了。所以把每一条边的流量设为一跑最小割就好了。

【SRM576】CharacterBoard 给定的字符中可能会产生冲突的字符串长度不超过[tex]nm\sqrt W[/tex]个，所以可以先统计其他长度的答案，再枚举这些可能会产生冲突的长度暴力验证一下。

【SRM575】TheTilesDivOne 这种题目只能是最大流了..把黑点拆成两个点中间连一条流量为1的边，然后每一个行数为1的白点向相邻的黑点连一条流量为1的边，源连过来一条边，其它点从相邻的黑点连过来一条边再向汇连一条流量为1的边。跑最大流就是答案了。

【SRM573】WolfPack 主要是每一次两维只改变一维没有办法拆开来比较蛋疼..可以把点[tex](x,y)[/tex]变成[tex](x+y,x-y)[/tex]，这样就可以把两维坐标分开来考虑了。然后就可以枚举坐标然后用组合数算算就好了。

【SRM571】CandyOnDisk 难的写一道计算几何题..结果就被鬼畜的精度给日了一脸不明液体...总之起始点到达每一个圆的位置一定是一个圆环，于是就记当前圆环跑一个类似SPFA的东西就好了..最后精度实在卡不过去就特判了，可能几天后就被hack敢死队做掉了吧。

【SRM570】CurvyonRails 去年走大爷讲过这题..先黑白染色，然后把每一个点拆成横向和纵向两个点，如果是拐弯的那么这两个点经过的流量都是1，因为存在不拐弯的情况，所以在这两个点之间连两条用来交换流量的边，如果这个点有限制那么交换的代价就是1否则就是0，跑费用流就好了。

【SRM569】MegaFactorial 其实这题不算难？现场无人A应该是被前两题卡码力了吧。在[tex]B \leq 10[/tex]的范围内只需要统计[tex]B[/tex]的最大质因子[tex]p[/tex]出现次数就好了。搞一个矩阵记[tex]n=p^i[/tex]的答案，然后就可以转移了。因为答案可能是会除以一个数的（8的答案是2的出现次数除以3），所以在矩乘的时候要拆开来记整数部分和余数。

【SRM568】DisjointSemicircles 分未确定的位置数是比12多还是比12少来考虑，反正分别暴力一下都可以转成二分图判定问题..写起来简直像是被喂翔> >而且988个数据是闹咋样，卡常数是闹咋样..报复社会的出题人真可怕..

【SRM567】Mountains 大力出奇迹..不对日的都死了按照编号从后到前放，显然当前状态只有每一列的高度是对以后的选择是有影响的，所以直接开个map存一下有用的状态转移一下就好了。看了一下题解发现可以证明状态数的上界是[tex]m2^n[/tex]的。

【SRM524】AxonometricProjection 把权值相同的行列取出来一起做，每一次DP的时候是一个L形区域（和比它权值大的行列有交），暴力DP出这些区域摆放的方案数然后乘起来就好了。