清华集训滚了一波大粗...感觉如果彻底成为养老选手的话可能会身败名裂，于是在养老的同时抽点时间来做做SRM吧..

学习一下鏼司机的模式整套整套的做吧..

[12.28]因为一些特殊原因，先跳过SRM518到SRM524，之后再折回来做。

[1.6]听说有一个智障在B站直播被SRM虐..

[1.10]感觉SRM做的差不多了，先停一停吧..完结撒花owo

[1.13]掉rating了嘤嘤嘤..

现在做了几题

【SRM500 A】MafiaGame 被淘汰概率最大的一定是最开始被指向最多的人，模拟游戏的进行，每一轮减去这个人不是票数最多的人的概率就行了。

【SRM500 B】FractalPicture 分形体似乎只能搜搜搜？因为精度只要求[tex]10^{-9}[/tex]所以直接搜前[tex]n[/tex]层就行了，可以发现每一次搜索最多递归到两个子问题，所以复杂度是[tex]O(2^n)[/tex]，我取了[tex]n=25[/tex]就过了。

【SRM500 C】ProductAndSum 只要知道了每一个数字出现了多少次就能算贡献了。所以就枚举每一种可能的数字出现次数，这个是不超过[tex]p2^2p3^2[/tex]的，然后再分别计算对答案的贡献就好了。

【SRM501 A】FoxPlayingGame 所有加的操作一定是连续的一段，所以枚举每一种可能的操作序列取最优的就好了。

【SRM501 B】FoxAverageSequence 令[tex]dp[i][j][k][pd][/tex]表示当前是第[tex]i[/tex]位，前面所有数之和是[tex]j[/tex]，第[tex]i-1[/tex]位是[tex]k[/tex]，第[tex]i-1[/tex]位和第[tex]i-2[/tex]位是否相等，暴力DP就好了。

【SRM501 C】FoxSearchingRuins 状态是当前走到了哪个珠宝的位置以及用了几次左右移动的操作，用树状数组优化一下转移就好了。

【SRM502 A】TheLotteryBothDivs 把无用的串都删掉（即至少有一个后缀在集合中），这样集合中每一个串的贡献都是[tex]10^{-|S|}[/tex]，累加起来就好了。

【SRM502 B】TheProgrammingContestDivOne 如果已经确定了做题的集合，那么做题的顺序一定是按照[tex]\frac{requiredTime}{pointsPerMinute}[/tex]递增的，排序之后再DP就好了，状态是当前的题目和已用的时间。

【SRM502 C】TheCowDivOne 一道很有趣的题目（虽然好难QAQ）。令[tex]f[a][b][c][/tex]为满足[tex]\sum_{i-1}^{a-1}x_i+b \times x_a \equiv 0 \pmod{c}[/tex]的方案数，其中[tex]x_i[/tex]为[tex][0,n-1][/tex]的整数且两两不同。令[tex]g=\gcd(b,c)[/tex]，考虑前[tex]k-1[/tex]个数的每一个存在解的方案，可以得到递推式：[tex]f[a][b][c]=f[a-1][1][g] \times \frac{ng}{c}-f[a-1][b+1][c] \times (a-1)[/tex]，记忆搜即可。

【SRM676 A】WaterTank 二分答案然后模拟即可。开始把[tex]10^6[/tex]看成[tex]10^5[/tex]，光荣FST。

【SRM676 B】BoardEscape 每一个棋子显然时独立的，只要求出sg函数就好了。sg函数在若干步之后应该是模[tex]4[/tex]循环的，先模拟[tex]nm[/tex]步然后用循环来求即可。

【SRM676 C】Farmville 还不是很会..先坑着

【SRM503 A】ToastXToast 如果有解，答案只可能为1或2。分别求出两个数组的最大值和最小值，就能够判断了。

【SRM503 B】KingdomXCitiesandVillages 考虑每一条边的贡献，求出这个点出发长度比当前边小的以及长度相同的边数。然后排列组合算算建的是这条边的概率，把贡献累加起来就是答案了。

【SRM503 C】KingdomXEmergencyStaircase 每加入一条边，都把当前图形分割成了两个子图形。可以发现每一个子图形最多有四条楼梯边，所以子图形的状态数时有限的（只有[tex]O(HW^3)[/tex]个）。直接把当前要处理的是哪个子图形当做状态，记忆搜就好了，细节很多写起来很蛋疼。

【SRM504 A】MathContest 每一时刻剩下的球一定是初始序列中的一个区间，模拟一下就好了。

【SRM504 B】AlgridTwo 第一行是确定的，然后就可以模拟程序运行的过程，存一下当前[tex](i+1,j)[/tex]是否被确定以及被确定的值，这样就能判断是否有解并求出网格中不影响结果的方块的个数[tex]x[/tex]，那么答案就是[tex]2^x[/tex]。

【SRM504 C】Stackol 只要求出每一个区间作为一次输出时的方案数就好了。可以枚举这一段在输入中最后一个字符是A还是B，这样就可以得到第一个栈输出的字符个数以及第二个栈输出的字符个数，判断一下就好了，稍微有点细节。

【SRM504.5 A】TheNumbersWithLuckyLastDigit 只需要考虑个位的贡献就好了，多出来的可以直接分配给其中一个数的高位。随便设一个阈值跑一下背包就行。

【SRM504.5 B】TheJackpotDivOne 若干步之后所有人的钱都变得一样了，可以先暴力模拟，当所有人的钱都变得一样的时候就可以直接计算终止状态了。要注意总和可能会爆long long，我用的方法是存储所有人的钱数和除[tex]n[/tex]的余数和模数。

【SRM504.5 C】TheTicketsDivOne DP，对于转移的环可以先把其它部分的贡献计算出来，然后列一个方程解出DP值。

【SRM505 A】RectangleArea 新建一个[tex]W+H[/tex]个点，没有边的无向图。如果询问了[tex](x,y)[/tex]，就在第[tex]x[/tex]个点和第[tex]W+y[/tex]个点之间连一条边，最后的答案是这张图的联通块个数-1。

【SRM505 B】SetMultiples 设阈值[tex]lim=10^5[/tex]，对于所有小于等于[tex]lim[/tex]的数，直接判断在这个区间内是否存在它的倍数。否则枚举倍数[tex]i[/tex]，计算出满足[tex]ix[/tex]在区间内且[tex]x>lim[/tex]的[tex]x[/tex]的取值区间，排序之后去一下重就好了。

【SRM505 C】PerfectSequences2 答案序列有两种情况，第一种是存在一个0，此时数列的和为0，枚举哪一个数变成0然后贪心即可；第二种情况是没有数位0，那么数列一定由一个所有数的绝对值都大于1的数列补上正负1得到，可以发现所有数的绝对值都大于1且补1之后可能得到合法数列的数列是有限的，可以先把这些数列都搜出来，然后枚举补几个1（剩下的都是-1），得到序列之后排序一下然后贪心即可。

【SRM506 A】SlimeXSlimesCity 排序之后贪心判断每一个编号能不能作为答案：最优情况下一定是从小到大地和其它城镇合并。统计满足条件的编号数即可。

【SRM506 B】SlimeXGrandSlimeAuto 求出使用每一辆车可以让每一段路程节约多少时间，然后就是一个最小权匹配了。

【SRM506 C】SlimeXSlimeRancher 令[tex]f[a][b][c][/tex]为考虑了所有满足第一个人的值不超过[tex]a[/tex]，第二个人不超过[tex]b[/tex]，第三个人不超过[tex]c[/tex]的所有属性的答案，[tex]num[a][b][c][/tex]为满足这个的属性个数，然后枚举下一次加入的属性是哪一个，直接转移就好了。

【SRM507 A】CubeStickers 如果颜色种数大于等于6种一定有解，其余情况就可以直接爆搜了。

【SRM507 B】CubePacking 设三边长为[tex]x,y,z[/tex]，那不妨设[tex]x \leq y \leq z[/tex]，因为答案在int范围内，所以可以枚举[tex]x[/tex]和[tex]y[/tex]，然后算出合法的[tex]z[/tex]的最小值，更新答案就好了。

【SRM507 C】CubeBuilding 开始看错题了，还以为南北两面都有限制，花了好久码了一个[tex]O(n^6)[/tex]的DP发现过不了样例...既然只有一面的限制怎么DP都行了，垃圾题目毁我青春。

【SRM508 A】DivideAndShift 把质因子预处理出来然后直接搜就好了。

【SRM508 B】YetAnotherORProblem 挺经典的数位DP，记录一下当前的位数，进位，当前位有几个1，只考虑已经确定的位数时每一个数和它的限制的大小关系，随便转移就好了。

【SRM508 C】BarbarianInvasion2 先二分答案，能到达每一个城市的点在一个圆内，所有城市代表的圆把多边形边界分成了若干段，每一段能够到达的城市数目是相同的，然后连边跑最大流判断就好了。

【SRM509 A】LuckyRemainder 10的幂次模9都是1，所以只需要考虑每一位出现了多少次就行了，每一位的贡献都是[tex]2^{n-1}[/tex]，算一下数位和乘一下就是答案了。

【SRM509 B】PalindromizationDiv1 SXBK的FST题。建一个空点表示不存在，那么插入和删除都可以看做字符和“不存在”之间的修改，然后跑Floyd求出修改的最优值，然后进行区间DP。要注意的是转移并不只有插入删除和修改，因为边都是单向的，所以可能出现在一边修改在另一边插入或者两边一起修改之类的情况。

【SRM509 C】NumberLabyrinthDiv1 阅读理解题，开始没看到给定点坐标都大于0，然后就蛋疼了。既然给定点坐标都大于0，那么最短距离一定就是[tex]xFinish+yFinish[/tex]，方案数的话随便容斥一下就好了。

【SRM510 A】TheAlmostLuckyNumbersDivOne 只有16位，满足条件的数字最多也就只有[tex]2^{16}[/tex]个，搜一搜就好了。

【SRM510 B】TheLuckyGameDivOne 把所有满足条件的数先求出来，只有[tex]2^{10}[tex]。这样就可以把区间分成[tex]2^{10}[/tex]段，每一段中所有位置作为第二个人的左端点效果都是相同的。然后枚举第一个人选择的左端点算出结果更新答案就好了。

【SRM510 C】TheLuckyBasesDivOne 枚举在那个进制下每一位的值，这样复杂度是对的，所有可能的进制表示只有[tex]2^{16} \times 16[/tex]种，我开始直接枚举然后用二分答案解方程，T飞了。实际上可以枚举所有满足[tex]x^3 \leq n[/tex]的[tex]x[/tex]作为答案，暴力检验一下。对于剩下的数，进制表示最多只有三位，要解的就只有一个二次方程，这样就可以[tex]O(1)[/tex]算了。

【SRM511 A】Zoo 出现的数一定是从0开始的连续一段，其中它的一个前缀出现了两次，判断一下就行了。方案数的话就是2的出现两次数的个数次方，如果有数出现了1次，那么还要乘2。

【SRM511 B】FiveHundredEleven 如果所有数的异或和不是511，那么游戏在卡片取完的时候结束，根据卡片奇偶性判一下就好了。否则游戏在异或和变成511时结束，可以把状态表示成取了[tex]i[/tex]张，异或和是[tex]j[/tex]，算算sg函数即可。

【SRM511 C】GameOfLifeDivOne 类似某次CF的A题。连续的一段01一定不会变，会变的只有01相间的一段，如果是序列的话就是傻逼DP。至于环，可以随便找一个11单元从中间剖开，然后在DP状态中加入11单元个数，这样每一个出现了[tex]i[/tex]个11单元的贡献就是[tex]\frac{1}{i}[/tex]，没有11单元的时候就找00单元剖开，之后就只剩下[tex]n[/tex]是偶数时所有位置都是01相间的情况，特判一下就行了。

【SRM512 A】MysteriousRestaurant 二分一下答案，然后求出第1到7天每天吃每道菜的代价，贪心选最小的加起来就好了。

【SRM512 B】SubFibonacci 枚举两个位置，同时枚举第二个数是斐波那契数列的第几项，这样就能解出来一个唯一的斐波那契数列，找到它在给定数组中出现的值存下来，同时记录从每一个位置出发长度最长的斐波那契数列有多长。这样得到了[tex]O(n^3)[/tex]个长度至多为[tex]O(n)[tex]的选择。枚举小的那个斐波那契数列是哪一个，从小到达枚举第二个数列的开头，算出答案更新就好了。

【SRM512 C】PickAndDelete 把S排序之后，原数列要满足小于[tex]S_i[tex]的数字个数不小于[tex]i[/tex]，随便DP一下就好了。

【SRM513 A】YetAnotherIncredibleMachine 对于每一个板子暴力枚举每一个位置可不可行，然后方案数乘起来就是答案。

【SRM513 B】PerfectMemory 开始把题目看成了同时翻，非常蛋疼的写出来后才发现原来是一个一个翻。令[tex]dp_{i,j}[/tex]为从已经翻了[tex]i[/tex]个，消掉了[tex]j[/tex]个这个状态出发直到游戏结束的期望操作次数。翻出来第[tex]i+1[/tex]个后，如果是已经出现过的就直接消，否则再翻一个。如果恰好相同就直接消掉，否则看一下第二个的颜色是不是已经出现过的。这样就能转移了。

【SRM513 C】Reflections 每一维是可以拆开的。考虑只有一维，从[tex]x[/tex]出发，假设依次经过坐标为数组[tex]A[/tex]的镜子的反射，那么最后到达位置的坐标就是[tex]2A_1-2A_2+2A_3...+(-1)^n \times x[/tex]，所以一定是最开始就移动然后通过反射达到目标地点。可以枚举每一个镜子选不选以及贡献是1还是-1。但是这样可能的情况有[tex]3^{20}[/tex]种，所以要加一个meet in middle。

【SRM514 A】MagicalGirlLevelOneDivOne 如果[tex]n[/tex]是偶数，那么什么点都能达到，否则只有两维坐标差为偶数的点才能达到。

【SRM514 B】MagicalGirlLevelTwoDivOne 可以把每一个位置都“移动”到左上角[tex]n \times m[/tex]的方格中，出现冲突就是误解。然后搞一个状压DP就好了。

【SRM514 C】MagicalGirlLevelThreeDivOne 傻逼分形题，显然只有前几百个串是有用的，然后搜搜搜码码码就好了。

【SRM515 A】RotatedClock 枚举时间，判断一下是否存在一种旋转方案满足条件就好了。

【SRM515 B】NewItemShop 状压DP，记录当前的时间，卖出了多少个，以及哪些客人来过了。因为只需要记录可能在至少两个时间点来的客人的状态，所以最多只要压12个人的就好了。

【SRM515 C】MeetInTheMaze 枚举F和R的出发点，新建一系列的点[tex]S_i[/tex]，[tex]S_i[/tex]到[tex]S_{i+1}[/tex]连边，然后对于每一个点，如果它到两个点的最短路之和为[tex]d[/tex]，就从[tex]S_{d-1}[/tex]到它连边。最后从[tex]S_0[/tex]出发BFS，到每一个点的距离就是以这个点为[tex]L[/tex]的答案了。

【SRM516 A】NetworkXOneTimePad 枚举一下两个串是匹配的，然后就可以把密钥算出来了，这样就能得到了所有的答案集合，看一下是不是包含就好了。注意要去重。

【SRM516 B】RowsOrdering 先通过每一列选取的排列最小化每一列单独产生的代价，然后再最小化总代价，随便贪就好了。

【SRM516 C】LexSmallestTour 字典序最小就逐位枚举，然后把已经确定的路径加一个虚点缩起来。接下来就是欧拉回路的判定了，除了一般的欧拉回路判断条件以外，每一个点连出去的同一种颜色的边不能超过它度数的一半。要注意的是起点需要特判，比较方便的方法是加一个虚点，然后向0号点连两条颜色和其它都不同的边。

【SRM517 A】CompositeSmash 就是判断存不存在不经过[tex]target[/tex]的拆分方法，直接记忆搜一波就行了。

【SRM517 B】AdjacentSwaps 感觉有点难理清楚的题目。可以通过模拟swap的进行把操作分成若干段，其中每一段都必须从左到右依次进行，连接两段的操作必须要在左右两个操作都进行完之后再进行（要注意某一段长度为1的情况）。模拟一下看看是不是存在合法解，然后就是一个丝薄DP了。

【SRM517 C】ColorfulBoard 要么每一行都被刷一遍，要么每一列都被刷一遍，假设每一行都被刷了一遍。最开始是能删行就删行，到不能删的时候，考虑当前能删的列，有两种情况，一种是把这些列都删完，这时就递归到了一个子问题；另一种情况是保留一种颜色，这时加上了剩下的每一行刷的颜色都是这种颜色这一个限制，可以递归到一个不同的子问题。直接暴力递归就好了。

【SRM525 A】DropCoins 预处理一下二维前缀和，枚举最后剩下的是哪个矩形，判断一下是不是满足条件然后更新答案就好了。

【SRM525 B】Rumor 枚举每一个人优先讲哪一种谣言，然后开始模拟：假定当一个人同时知道了两个谣言且一个都没有讲过的时候，就讲他优先的那一种，其它情况就讲没有讲过的那一种。模拟出来达到目标状态的天数更新答案即可。

【SRM525 C】MonochromePuzzle 交换结束之后相当于得到了一个排列[tex]P[/tex]，使得在对行列应用了置换[tex]P[/tex]之后黑色格子的位置和题目中给出的一样。可以枚举[tex]P_0[/tex]，通过它所在行的黑色格子位置枚举[tex]P_{n-1},P_{\frac{n}{2}-1},P_{\frac{n}{2}}[/tex]，然后就可以推出排列[tex]P[/tex]了，check一下是否满足条件之后用[tex]n[/tex]减去循环个数来更新答案即可。

【SRM526 A】DucksAlignment 枚举最后鸭子的位置，然后就是一个普及组贪心了。

【SRM526 B】PrimeCompositeGame 预处理一波奇数和合数，然后再对每一部分分成赢的状态和输的状态两种，分别用单调队列来优化转移。要注意1既不是质数也不是合数，不然会FST。

【SRM526 C】DengklekMessage 当选取的字符串的数目大于好串的长度时，每增加一个字符串后答案的增加值应该是相同的。所以小范围DP然后大范围直接算就好了。

【SRM527 A】P8XGraphBuilder 就是一个背包，记录一下子树大小和根的度数就行了。

【SRM527 B】P8XMatrixRecovery 逐位确定，判断一个局面可不可行可以用二分图匹配来解决。

【SRM527 C】P8XCoinChange 是最近某场SRM的hard的ex版本..把方案中的硬币序列排序，DP出开头是[tex]value_l[/tex]，末尾不超过是[tex]value_r[/tex]的和为[tex]value_i[/tex]的硬币序列数目，转移的时候可以用矩阵乘法进行。然后同样使用矩阵乘法就能求出答案了。

【SRM528 A】Cut 贪心一下，把长度是10的倍数的拿出来按照从小到大的顺序优先切，之后再来切剩下的。

【SRM528 B】SPartition 经典题目，直接meet in middle。

【SRM528 C】ColorfulCookie 直接DP，状态是考虑了前[tex]i[/tex]堆，然后前面留下来还没有配对的有[tex]a[/tex]次减[tex]C1[tex]，[tex]b[/tex]次减[tex]C2[/tex]时的最优值。然后转移的时候就枚举当前堆怎么分，然后能配对就配对，这样就能保证状态数很少了，不过要注意的是不一定只和还没有配对的操作进行匹配，也可以和已经匹配的交换一下匹配对象。

【SRM529 A】KingSort 普及罗马数字的题目，按照题意sort一下。

【SRM529 B】MinskyMystery 可以推出来一个柿子，然后就可以直接算了..要注意特盘0和1的情况。

【SRM529 C】BigAndSmallAirports 枚举一下[tex]B[/tex]和[tex]S[/tex]，然后当[tex]N[/tex]大于[tex]B[/tex]的时候显然有解，其他情况直接枚举大飞机场的个数然后算一下至少要几个小飞机场就行了。

【SRM530 A】GogoXCake 经典题，直接从左上到右下模拟就好了。

【SRM530 B】GogoXMarisaKirisima 贪心，每一次找一条起点到终点的最短路，然后把这条路径上的边都删掉并把这条路径上的点都缩起来，直到不存在起点到终点的路径为止。

【SRM530 C】GogoXBallsAndBins DP，只考虑重新排列之后编号变大的位置，这样就能把绝对值拆掉了。排序之后，状态为最大的[tex]i[/tex]个位置，有[tex]j[/tex]个空位，代价和为[tex]k[/tex]时的方案数，转移就直接枚举当前为止是放到前面，后面还是不变就好了。

【SRM531 A】NoRepeatPlaylist 每一个位置能够选择的音乐个数是一定的，乘起来就好了。因为求的是每首歌都听过的方案书，所以还要容斥一下。

【SRM531 B】MonsterFarm 把数目不会增加的品种设为终止节点，显然如果答案有限，那么只有终止节点能在环中。我们把终止节点都缩起来，这样就得到了一个DAG，直接DP就好了。

【SRM531 C】BuildingReorganization 显然存在一个中介位置，它的左边全部都是从[tex]A[/tex]移过去的，它的右边全部都是从[tex]B[/tex]移过去的，它这儿两个都有。可以枚举这个位置，然后三分[tex]A[/tex]到这个位置的楼层个数，得到最优值后更新答案。求答案可以二分一下[tex]A[/tex]或者[tex]B[/tex]运出去的最高代价，这样就能得到终止状态了。

【SRM532 A】DengklekMakingChains 能整段取就整段取，否则求一下前缀值和后缀值，枚举取哪个的前缀，然后在剩下的串里取个最大的后缀更新答案就好了。要注意只有中间那个有值的时候也要更新答案。

【SRM532 B】DengklekBuildingRoads 装压一下前[tex]K[/tex]个点度数的奇偶性，随便转移就行了。

【SRM532 C】DengklekCountingFormations 容斥，枚举行的所有等价类，然后瞎记忆搜一波。要预处理大小为[tex]i[/tex]的等价类的方案数，

【SRM533 A】CasketOfStar 区间DP，每一次枚举区间里最后一个拿的是哪个，然后就递归到子状态了。

【SRM533 B】MagicBoard 对每一行每一列建一个点，然后每一个#都是一条边，原问题相当于判断这张图是否存在一条从行所在的点出发的欧拉路径，直接套结论就好了。

【SRM533 C】Pikachu 开始一直往哈弗曼树算法上想，结果怎么也想不出来。和普通的哈弗曼树算法不同，从根往叶子考虑，可以发现考虑到第[tex]i[/tex]层的时候，只有[tex]i+1,i+2[/tex]这两层可能有节点。状态就是这三层的节点数和当前从大到小填了几个数进去。可以发现在计算代价的时候和层数无关，所以层数就不用记了。转移就枚举填了几个数到第[tex]i[/tex]层，剩下节点的连边都可以贪心得到。

【SRM534 A】EllysCheckers 数据范围才20，随便记忆搜一下就好了。

【SRM534 B】EllysNumbers 分解质因数之后，显然对于每一个质因数，只能选取一个它的倍数的数。于是对每一个数记录下来它是哪些质因数的倍数，然后装压DP一波。

【SRM534 C】EllysString 因为修改和交换的代价都是1，两对交换的数对应的区间一定不会相交（不包括端点）。于是就可以直接DP了，令状态为考虑到第[tex]i[/tex]个位置，换过来的字符是[tex]j[/tex]，需要一个字符[tex]k[/tex]换进去，然后枚举一下是否继续交换就好了。

【SRM535 A】FoxAndGCDLCM 如果把两个数都除以[tex]G[/tex]，那它们的乘积就是[tex]P=\frac{L}{G}[/tex]，要最大小和，所以只要找到[tex]P[/tex]的一个尽可能大的约数[tex]k[/tex]满足[tex]k \leq \frac{P}{k}[/tex]，暴力就好了。

【SRM535 B】FoxAndBusiness 二分答案，然后就能推出来一个柿子，然后就可以贪心啦。

【SRM535 C】FoxAndGreed 每一次往下走，路径的权值和一定至少增加了1。所以路径一定会经过第[tex]S[/tex]行第[tex]m[/tex]列。这样就把DP的范围缩小到了[tex]S \times m[/tex]，剩下的部分用排列组合算就行了。

【SRM526.5 A】MagicCandy 轮数不会很多，直接模拟出每一轮少了多少个糖果，然后再从最后倒推回来就好了。

【SRM526.5 B】MagicBlizzard 相当于计算在同一个格子内的雪花个数，对每一朵雪花拆开来计算贡献就行了。

【SRM526.5 C】MagicMatchesGame 开始一直处于智障状态，居然没有看出来...相当于求一个最小乘积线性基。如果权值是一维的，就直接排序后贪心的加入。然后再套上最小乘积问题的通用方法，转化成一维搜下去就好了。

【SRM518 A】LargestSubsequence 直接贪心，从大到小能取就取。

【SRM518 B】ConvexSequence 好难啊..根本不会做。后来听说只要对于每一个位置，直接把它调整到小于等于相邻两个的平均数，重复若干轮直到稳定就行了。

【SRM518 C】Nim FWT经典题，但是因为我不会推FWT，所以就码了一波分治乘法。

【SRM519 A】BinaryCards 找到A和B不同的最高位，那么能达到最大值就是更高位数和A相同，后面都是1的二进制数。

【SRM519 B】RequiredSubstrings AC自动机经典题，建出来转移然后直接状压DP。

【SRM519 C】VerySmoothDecompositions 要考虑的质因子只有2,3,5,7，而5和7是无关的，可以考虑DP，状态是2使用的次数和3使用的次数，然后用各种奇怪的方式优化转移就行了。因为卡空间所以写起来很蛋疼。

【SRM520 A】SRMCodingPhase 枚举做哪几道题然后贪心。

【SRM520 B】SRMIntermissionPhase 背包出每一种做题状态得每一种分数的方案数，然后用DP合并求出答案，转移要用前缀和来优化。

【SRM520 C】SRMChallengePhase 把点分成叉人自己也被叉，叉人自己没被叉，没叉人自己被叉三类（剩下的人和答案无关）。可以发现叉人的关系是若干条链，其中第三类一定是链的结尾，所有链的开头一定是第一类。问题就转化成了把这些人分成第一类人数这么多条链的方案数，可以枚举当前情况下最先叉人的那个人，加入某一条链的末端进行DP，状态就是人数和链数，排列组合随便算算就好了。

【SRM521 A】MissingParentheses 经典题，在最左边加(，在最右边加)，从左到右扫一遍能不加就不加。

【SRM521 B】RangeSquaredSubsets 正方形肯定有两个相邻的边界的坐标与给出点的坐标相差不超过1，所以枚举这两条边的坐标，然后把所有点按照被纳入这个正方形时需要的最小边长排序，依次加入，用map去一下重统计一下答案就好了。

【SRM521 C】Chimney 只有最上面三层可能不满，先搜出所有可能的状态，建出转移矩阵，直接矩阵乘法就好了。

【SRM522 A】RowAndCoins 数据范围很小，直接记忆搜就好了。

【SRM522 B】CorrectMultiplication 显然[tex]a,b[/tex]中较小的数不超过[tex]10^5[/tex]，不妨设[tex]a<b[/tex]，枚举[tex]a[/tex]，然后[tex]b[/tex]一定在[tex]\frac{c}{a}[/tex]附近，稍微枚举一下然后计算贡献更新答案就好了。

【SRM522 C】PointErasing 最后剩下的一定是数值分别等于最左边的数，最右边的数，最大的数，最小的数的至多四段数，其中最大的数和最小的数一定不会变，而可能存在的最左边的数和最右边的数的[tex]x[/tex]坐标不会相交，直接预处理出所有可能的操作然后DP就好了。

【SRM523 A】CountingSeries 等比数列中的数字个数有限，直接计算等差数列中出现了多少个，然后再枚举等比数列中的每一个数计算贡献得到答案。

【SRM523 B】BricksN 预处理出摆连续的长度为[tex]i[/tex]的一段的方案数，然后直接DP就行了。

【SRM523 C】AlphabetPaths 长度为[tex]i[/tex]的路径最多只有[tex]nm3^i[/tex]条，直接把这些路径都搜出来然后meet in middle就得到答案辣。

【SRM524 A】MagicDiamonds 质数的答案是2，合数的答案是1，要特判一下1和3。

【SRM524 B】LongestSequence 如果答案有限，那么一定不超过2000，二分一下答案然后把差分约束系统建出来，因为所有边的边权都是负数所以可以直接DFS判负环。

【SRM524 C】AxonometricProjection 之前TC练习记的时候做过，瞎DP一通就好了。

【SRM536 A】MergersDivOne 最优方法一定是两个两个从小到大合并，排序一下就好了。

【SRM536 B】RollingDiceDivOne 从小到大把骰子加进去，每一时刻开头一段单调增，最后一段单调减，中间一段都是相同的最大值。记录一下最大的那一段的左端点和右端点，加入骰子后分类讨论可以得到之后的状况。最后的左端点就是答案了。

【SRM536 C】BinaryPolynomialDivOne 相当于从给定集合中选出[tex]m[/tex]个数拼出[tex]k[/tex]。可以把这[tex]m[/tex]个数两两配对，如果其中至少有一对的两个数不同，就可以把这两个数交换一下也是一个合法的答案，因此这个方案在模2意义下就消掉了。所以每一对的两个数都是相同的，这样就递归到了一个[tex]\frac{m}{2},\frac{k}{2}[/tex]的子问题。如果[tex]m[/tex]是奇数就枚举多出来的那个数是什么，加一个map进行记忆搜，这样复杂度也是对的。

【SRM537 A】KingXNewCurrency 如果[tex]X[/tex]能同时拼出[tex]A,B[/tex]，那么就有无穷多解，否则假设拼不出来[tex]A[/tex]，那么就在[tex][1,A][/tex]枚举[tex]Y[/tex]。在[tex][1,AB][/tex]范围内跑背包判断是否有解，更大的情况只要满足[tex]AB[/tex]的最大公约数是[tex]XY[/tex]的最大公约数的倍数就好了。

【SRM537 B】KingXMagicSpells 经典问题，分每一位考虑，DP之后累加贡献。

【SRM537 C】PrinceXDominoes 存在欧拉回路的条件是图联通且每一个点的入度等于出度。如果一个点的入度大于出度，就从它连到汇连流量为入度减出度，费用为0的边；入度小于出度就从源连过来。对于图中原有的边，如果有[tex]i[/tex]条，就在图中接上连接相同的两个点，流量为[tex]i-1[/tex]，费用为1的边。如果图不连通或者这个费用流无法满流，那么就无解，否则答案就是总边数减去最小费用最大流的费用。

【SRM538 A】EvenRoute 路径长度的奇偶性只和终止节点两维坐标之和的奇偶性有关，要注意坐标之和可能为负数。

【SRM538 B】TurtleSpy 一定存在一个最优方案是：先向前走，然后转一定的角度，再往后走，最后再转一定的角度。所以背包出当前这些操作能够转的角度数，然后枚举每一个能达到的角度计算答案取最大值就行啦。

【SRM538 C】SkewedPerspective 摆出一个状态用的列数越少越好。要考虑到不重不漏，最后可以设计出这样的状态：记录当前的高度，总体积，视野中有多少个黑色方块，使用的列数，必须要使用的黑色方块数，必须要使用的单个方块数，上一次放置的是否是没换列的黑色方块。然后七位数组DP一波就好了。

【SRM539 A】Over9000Rocks 枚举在哪些盒子里放，然后就得到了若干个区间，排序之后统计一下就好了。

【SRM539 B】SafeReturn 先跑出两点之间的最短路，然后直接二分图匹配一波就好了。

【SRM539 C】FoxBomb 最开始想简单了，漏了一些状态。先把树建出来。对于每一个子树，根记录它子树中和它连在同一行和同一列的所有点的状态。状态有三种：没有被覆盖满，被覆盖满但是没有在这一段上没有放炸弹，在这一段上放了炸弹。然后瞎DP一波就好饿啦。

【SRM540 A】ImportantSequence 每一个数都可以用第一个数来表示，因为所有数都是正整数，所以就相当于给第一个数的取值产生了很多约束。只要求出第一个数取值的上界和下界就好了。

【SRM540 B】RandomColoring 比较基础的DP优化，每一次给一个长方体范围内的所有位置进行加减。三维差分之后加加减减一波就行了。

【SRM540 C】ProductQuery 根据中国剩余定理把2和5拆开来分别计算。可以把以每一个位置为右端点的限制简化到一个（区间加加减减乘乘除除的乱搞搞），然后DP状态就是当前的位置和上一个值为0的位置，随便转移一下就好了。

【SRM678 A】ANewHope 没过一个礼拜每一件衣服的日期就可以往前移动[tex]N-D[/tex]，所以答案就是往前移动最多的距离除以[tex]N-D[/tex]上取整再加一。

【SRM678 B】TheEmpireStrikesBack 二分答案，然后对节点和所有可能的范围的右上角处理出一个阶梯状物体，贪过去就好了。

【SRM678 C】ReturnOfTheJedi 比赛的时候猜到了做法但是柿子没有推出来QAQ。一定存在一个[tex]k[/tex]使得在最小化答案的同时最小化了[tex]\sum x_i+k\sum \log p_i[/tex]。证明大概就是把图像画出来然后从最优解作图像的切线之类的，和CC那题很像。