20220926 ICPC 网络赛

队长生病了没来，和 wwj 两个人打了一把，过了 8 题，勉勉强强。

A Yet Another Remainder

当 \(n\ge p-1\) 时，根据费马小定理，只需要对前 \(p-1\) 个位置询问每次跳 \(p-1\) 步得到的和是多少，单次询问时间复杂度 \(O(p)\) 。当 \(n<p-1\) 时，从后往前暴力确定每个数，单次询问时间复杂度 \(O(n\log n)\) 。

B Non-decreasing Array

对于第一步操作，显然是能删就删收益最大，而对于第二步操作，显然是把 \(a_i\) 改成 \(a_{i-1}\) 或者 \(a_{i+1}\) 收益最大，这也等价于将 \(a_i\) 删掉。于是问题转化为每次操作可以删掉两个数，问最后的最大收益。设 \(dp(i,j)\) 表示只考虑 \(1\sim i\) 这 \(i\) 个数，删掉其中 \(j\) 个数（不能删 \(1\) 和 \(i\) ）时的最大收益即可，时间复杂度 \(O(n^3)\) 。

G Good Permutation

先考虑没有区间相互包含的情况，即给出的区间都是两两相离的。记给出 \(m\) 个区间，第 \(i\) 个区间的长度为 \(x_i\) ，这些区间的总长为 \(s\) 。

考虑如何计算给这些区间分配数的方案数，发现只需要在值域 \(1,2,3,\dots n\) 这个序列上确定第一个区间的位置以及相邻两个区间间隔的距离，再将这些区间确定一个顺序依次放上去即可，方案数为 \(m!\times \binom{n-s+m}{m}\) ，再乘上这些区间外的方案数 \((n-s)!\) 与每个区间内部的方案数 \(\prod x_i!\) 。

现在考虑每个区间内部可能还有其他区间的限制，不难发现其他部分方案数是一样的，只需要把 \(\prod x_i!\) 换成每个区间内部的方案数，而这是一个子问题。对每个区间预处理出包含它的最小区间，于是区间加上 \([1,n]\) 形成了一个树形结构，在树上进行一次 dfs 即可算出答案。

H Communication Station

考虑点对 \((u,v)\) 之间的贡献，记它们之间的距离为 \(d\) ，除掉 \(u\) 到 \(v\) 这条链还有 \(m=n-d-1\) 个点，则贡献为 \(d\times (m+4)\times 2^{m-1}\) ，可以写成 \(\frac{1}{4}\times P(d)\times 2^{n-d}\) 的形式，其中 \(P(d)\) 是一个关于 \(d\) 的二次多项式。

考虑 dfs 遍历每个点作为 \(u\) ，换根的过程中某个子树内的 \(d\) 全部减 1，其余点的 \(d\) 全部加 1，用一棵线段树维护每个点作为 \(v\) 的贡献即可。

J A Game about Increasing Sequences

满足严格上升的取数序列数目不会很多，dfs 爆搜即可。

K Black and White Painting

由于圆和正方形的中心都在整点处，于是两个图形之间有交的情况是有限的，枚举一个图形 \(i\) ，如果是正方形，将它的边分成 8 份，如果是圆，将它的圆周分成 12 份，再枚举一个其他图形 \(j\) ，讨论所有情况，检查 \(i\) 的哪些边/圆周会被 \(j\) 覆盖掉，最后考虑了所有图形后仍未被覆盖的部分就是 \(i\) 对答案的贡献。

注意两个正方形可能会出现共用一部分边贡献到答案的情况，可以规定编号小的覆盖掉编号大的，避免重算漏算。

L Quadruple

如果确定了字符 I 的位置与字符 P 的位置，那么它们的贡献只和 C 的个数前缀和有关，将式子拆开后全部用前缀和进行处理即可。具体可以参考 autoint 的博客 。