TC SRM661~670

SRM661

Easy

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

Medium

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

Hard

没看

SRM662

Easy

大概是排成先上升后下降的圈。

Medium

设$f[i][j]$为$i$个节点，全距离和模$m$为$j$的有根树的最小全距离和。因为是有根树，转移则是在某个节点上再连一棵有根树，如果之前那棵有根树大小为$x$，则新的边会被走$x(n-x)$次。

时间复杂度为$O(n^2m^2)$

SRM663

Easy

按照目标串与初始串的B数量之差可确定做了多少次B操作，以及决定最后的串是不是反着的，然后在找到能匹配的位置看两边B的数量以及串的模式是否满足要求。

Medium

对于每个询问，如果不包含$num$个大小为$size$的物品的方案数组为$f$，则：

$$ways[i] = \sum_{k=0}{f[i - size \cdot k]C_{num}^{k}}$$

所以

$$f[i] = \sum_{k=0}{(-1)^kways[i - size \cdot k]C_{num+k-1}^{k}}$$

单次询问复杂度为$O(D)$。

SRM664

Easy

设$n=A+B$，则每一轮如果$x$是较小的数，就会变成$2x$，如果是较大的数，就会变成$2x-n$。每过一轮可以看做在模$n$剩余系下乘$2$。故答案为$min{A \cdot 2^K \mod n , n - (A \cdot 2^K \mod n)}$。

Medium

考虑期望的线性性，联通块大小的平方的期望可看作每对点之间是否联通的概率之和，所以问题就变成了点上有权，求$n^2$条路径权值乘积的和。这个拿dfs在每对点的LCA处统计统计就好了。

SRM665

Easy

因为位数很小，可以直接从低到高枚举每一位放什么，搜索参数同时有现在有多少个数活着(0,1,2)和进位。

Medium

如果value之和为total，那么很明显题目给出的前缀后缀都是没用的，可以统一变成$min(sum-value , total- sum)$，代表这个帽子在某个方向上顺过去的帽子value和小的值。

那么一开始必然要存在一个值为0的点，表示这个点一定要放在边界上，给这些值排个序，类比维护一个两边的和，如果当前这个和两个都满足，就意味着两边都可以放，方案就乘上了$2$。注意如果有解最后一个位置一定是两边都满足的，这个$2$就不能乘了。

SRM666

Easy

如果$L \geq 2(n-1)$，那肯定可以遍历整棵树。走过尽可能多的点意味着往回走的步数尽可能少，所以如果最大深度是$d$，则这$d$个点可以以1的代价走到，其他点的代价都为2。

Medium

设$f[i][0/1][0/1]$为长度为$i$的排列，左右两侧是否有数被选了的答案，则转移就是枚举第一步选哪个数，就能知道这个数对答案的贡献，两头拼起来再乘个组合数就好了。

SRM667

Easy

状压DP，直接设$f[mask]$表示某个集合已经缓存过的最小代价，转移就是枚举一行按下去。最后只要把出现过的位记录上即可。

Medium

要让第$K$个位置最后一个被访问，那么只有两种情况，一个是先访问$K-1$再回头访问$K+1$，另一个是先访问$K+1$再访问$K-1$。两个的概率当然是可以累加的。现在就要算先访问$K-1$再回头访问$K+1$的概率。

所以就从$K$个位置断开，从$0$号位置出发要比$K+1$的位置先到$K-1$，这里就有一个转移方程。解这个方程就能得到这个概率。然后到了$K-1$后还要比第$K$个位置先到$K+1$，这里也是一个一样的方程，解出来乘起来就好了。

SRM668

Easy

$K=1$肯定有解，不然当$n \times m$为偶数时肯定有解。

Medium

首先0和1必须强联通，然后如果0和1所在强联通分量内部所有的环gcd为1则有解。

所以可以BFS出$f[i][j]$从0点出发走$j$步到达$i$号点是否可能，$j \leq n + n$。

用所有$f[0][j]=true$的$j$的gcd判断答案。

SRM669

Easy

如果确定了最后切成什么样，那么切的顺序并没有影响，所以可以看出切的尽可能平均得分最高。所以只需要枚举切了多少次来看得分是否达标即可。

Medium

枚举最后MST的权值分布，可以看出非树边的权值是要不小于对应树上的边权的，所以可以DP设$f[i][j]$为有$j$个点的链，并且树边的权值不超过$i$的方案数，则有： $f[i][j] = f[i - 1][j] + \sum\_{k=1}^{i-1}{f[i][k] \cdot f[i - 1][j-k] \cdot (L-i+1)^{k(j-k)-1}}$ 最后把链镶嵌回去有$\frac{n!}{2}$种方法。

SRM670

Easy

观察到LCS应该是n-1，所以只需枚举所有和原串LCS为n-1的$O(n^2)$个串然后check一下是否是括号匹配串即可。

Medium

B的决策应该是往A的某一个点靠近。所以可以二分答案然后判断所有B的点是否是否可以覆盖住某个A点的所有可能在的位置。

Written with StackEdit.