TC SRM651~660

SRM651

Easy

如果机器人在某一方向有墙挡着，返回-1，因为往那个方向再怎么走都不会死。然后现在考虑某一个方向，如果走x步就会死，那显然步数序列中就不能有x个这个方向。四个方向的x-1加起来答案为n+m-2。

Medium

首先只有6只狐狸……6个格子所形成的联通块样式的数量是非常有限的，可以先把这些样式暴搜出来，然后就差移动了。固定一个格子的坐标后可以发现横纵坐标是独立的，而每个坐标实际上还是一个求绝对值之和最小的问题，取中位数即可。

SRM652

Easy

考虑1所在置换群子群的大小，答案为$[1,n]$的LCM。

Medium

设$f[i][j]$表示Alice在i点并且Bob还有j次机会Alice走到终点的最小花费，初值$f[n-1][j]=0$。则如果i能走到x，$f[i][j]$要么从$f[x][j] + cost$转移，表示不用机会，或者从$\max(f[x][j-1] + cost)$转移，从中选最大值。转移带环，用Dijkstra即可。

SRM653

Easy

直接DP，看方案是否存在且唯一。

Medium

大于high以及小于low的配属已经确定了，关键在于low到high之间怎么分配给谁，变量选择有代价，之间也有代价，可以看出这是一个最小割问题。

SRM654

Easy

利用期望线性性，枚举一段字符串考虑它们全是某种字符的概率。

Medium

第一个数必加，第二个数必减，然后在剩下数中找至多两个不相交的连续子序列符号变正，方法很多。

SRM655

Easy

增添一种新的标记’?’表示之前既可能是黑的也可能是白的，这样如果存在一个不同时有黑色和白色格子的KxK的矩形，就把它们全部染成’?’。最后如果是Possible意味着所有格子都被染成了’?’。

Medium

直接一位一位DP复杂度是$O(9^nnm)$的，肯定不行，考虑到位最多只有$2^n$种，可以把相同的放在一块考虑，先DP出$g[i][j]$表示i位数字加起来得到j的有多少种，再dp就是$O(9^nn2^n)$了。

SRM656

Easy

$f[i][j]$表示取了i张饼并且最上边的饼宽度为j的期望，转移显然。

Medium

考虑容斥，容斥的每一项都是一堆组合数相乘，然后再加加减减。观察式子可以从左边提出不同的项，提出来之后就可以发现$O(n^2)$的递推/DP。

SRM657

Easy

二分，check优先用E和H填补简单和困难，然后再用EM和MH，最后用剩下的EM，M，MH填补中等难度。

Medium

对答案可以每个质数单独计算，对于每一个质数$p$都要找一个最大的$k$使得对于$x$的任意取值都可以使得$p^k|P(x)$。至于这个$k$该如何去找，可以考虑从$[0,p)$枚举$x$每一位上的取值，这样取所有$x \equiv i \mod p$的位置，将指数的和加入答案，再找下一位。最后的结果仅需取一个最小值。

SRM658

Easy

先$O(n^3)$判断是否合法，再去枚举一个根，链接上奇点，再链接上偶点。

Medium

直接$f[i][j][k]$表示打败前i只怪物用了j次9，k次3时最少用了多少次1是不行的，因为无法表示每轮9,3,1攻击的怪物不同。考虑到可以二分答案，只需要check是否在m轮内能全灭怪物。所以只要保证每次怪物被攻击不超过m次这样DP即可。

Hard

做一次最大匹配，如果一个被匹配到的左端点与一个未被匹配到的右端点相连，那这个点必然不能被加入答案中。每次将这样的左端点删去，做匹配，直到不存在这样点为止，此时所有被匹配到的左端点集合的size和与被匹配到的左端点相连的右端点集合size相等。题意要求了每个左端点必须和一个右端点相连，似乎不存在无解的情况。

SRM659

Easy

贪心，从前往后能放就放，拿树状数组维护。

Medium

状压DP，逐格转移$O(nm2^m)$。

SRM660

Easy

枚举第一个的位置，用set维护第二个的最大值。

Medium

单独考虑每个人对答案的贡献，显然他的贡献只与他dislike构成的链长有关。具体的值用DP求出，或者找规律。

SRM661

Easy

求出1~n的LCM，拿每个质数次幂的大于n的最小倍数更新答案。

Medium

单独考虑每个点，如果一个点前面有i个点，啥都不连方案为K，如果连因为不能同色方案为i*(K-1)，所以答案为$\Pi_{i=0}^{N-1}(K + (K-1)i)$。

Written with StackEdit.