2017年六省联考题解

2017 年六省联考简要题解

# Day 1

# T1 期末考试

​ 有 $n$ 个同学，$m$ 个科目。每个科目计划在 $b_i$ 天公布成绩，第 $i$ 位同学希望在第 $t_i$ 天及以前知道所有科目的成绩，假如最晚的一个科目公布时间为 $t$ ，则其不满意度为 $max(0,t-t_i)\times C$。现有两种操作，一是将科目 $X$ 的公布时间推迟一天同时将 $Y$ 的公布时间提前一天，一次操作不满意度为 $A$ ；二是使科目 $X$ 的公布时间提前一天，一次操作不满意度为 $B$ 。（其中 $X,Y$ 为任意科目）。求最小的不满意度之和。

​ $1\le n,m,t_i,b_i\le 10^5 \; \; A,B,C$ 均为非负整数 。

考虑如果我们知道了最晚的一个科目的公布时间，我们就可以很容易求出不满意度。所以我们枚举最晚的一个科目的公布时间，然后将所有晚于它的科目的时间全部调整为它。然后我们可以根据 $A,B$ 的大小关系分类讨论一下。若 $A<B$ ，就不断用第一种，不够了再用第二种，否则就直接不断用第二种。这个用前缀和维护一下就行，时间复杂度为 $O(\max \lbrace b_i \rbrace)$ 。

# T2 相逢是问候

​ 给定 $n,m,p,c$ 。有一个长度为 $n$ 的序列，有 $m$ 个操作，$0 \;l\;r$ 表示将 $a_i(l\le i\le r)$ 都替换成 $c^{a_i}$ ，$1\; l\; r$ 表示查询 $[l,r]$ 内所有数的和 $mod\; p$ 的结果。

​ $1\le n,m\le 5\times 10^4$ ，$1\le p\le 10^8$ ，$0<c,a_i<p$ 。

考虑操作一，形如 $c^{c^{c\cdots}}$ 很容易想到扩展欧拉定理。

$$a^b \equiv \begin{cases} a^{b\bmod\varphi(m)},&\text{$\gcd(a,m)=1$}\\ a^b,&\text{$\gcd(a,m)\ne1,b\le \varphi(m)$}\\ a^{b\bmod\varphi(m)+\varphi(m)},&\text{$\gcd(a,m)\ne1,b\ge\varphi(m)$} \end{cases} \pmod{m}$$

所以我们反复使用扩展欧拉定理，每次都会把 $m$ 变为 $\varphi(m)$ ，当 $\varphi(m)=1$ 时，原式变为定值。所以我们不断将 $p$ 变为 $\varphi(p)$ 直到为 $1$ 后停止，而一个数最多经过 $\log$ 次就可以变成 $1$ ，因为偶数的欧拉函数值必定小于它的一半，而奇数的欧拉函数值必定为偶数，所以我们只需要维护 $\log p$ 个幂即可。同时，发现此题涉及到区间操作，考虑用线段树直接维护区间和以及区间最小变换次数即可。这题预处理比较麻烦，我们需要预处理出 $a_{i,j}$ 表示 $c^{c^{\cdots ^{a_i}}}$ （其中下方 $c$ 的个数为 $j$ ），这个直接套用扩展欧拉定理即可，若直接套用快速幂计算，预处理复杂度为 $O(n\log^3p)$ ，所以我们替换为光速幂。设定阈值 $b$ ，预处理所有的 $p_x=c^x$ 和 $q_x=c^{b^x}$ ，则 $c^x=p_{x \, mod\, b }\cdot q_{\lfloor\frac{x}{b}\rfloor }$ ，这样省去了快速幂的复杂度。最终总时间复杂度为 $O(n\log^2p+n\log n\log p)$ 。

# T3 组合数问题

​ 给定正整数 $n,p,k,r$ ，求 $\sum_{i=0}^{\infty} {\binom{nk}{ik+r}} \bmod p$ 的值。

​ $1\le n\le 10^9$ ，$0\le r<k\le 50$ ，$2\le p\le 2^{30}-1$ 。

可以转变题意，即求在 $nk$ 个物品中选出 $x$ 个，且满足 $x \; mod \;k =r$ 的方案数。那我们有一个比较显然的 $dp$ ，设 $f_{i,j}$ 表示当前考虑第 $i$ 个物品，选出的数量 $mod \; k=j$ 的方案数，转移也比较简单。分别考虑是否选这个物品，就有 $f_{i,j}=f_{i-1,j}+f_{i-1,(j-1+k)\,mod\,k}$ ，时间复杂度为 $O(nk^2)$ 。我们发现 $n$ 非常大，而且 $f_i$ 的转移只和 $f_{i-1}$ 有关系，我们可以考虑用矩阵乘法优化转移。

$$\left[ \begin{matrix} f_0&f_1&f_2&\cdots &f_{k-1} \end{matrix} \right] \times \left[ \begin{matrix} 1&0&0&\cdots&0&1\\ 1&1&0&\cdots&0&0\\ 0&1&1&\cdots&0&0\\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\ 0&0&0&\cdots&1&0\\ 0&0&0&\cdots&1&1 \end{matrix} \right]$$

可以构造出形如这样的转移矩阵，初始值 $f_0=1$ ，跑矩阵快速幂即可。时间复杂度$O(k^3\log(nk))$ 。

# Day 2

# T1 摧毁 “树状图”

​ 给定一棵 $n$ 个点的树，找到树上的两条边不相交的路径，使得删去路径上的所有点和边后剩下的连通块数量最多，输出最大个数。

​ $n\le5\times10^5$ 。

大力树形 $dp$ ，我们设 $f_{u,0/1/2/3}$ 表示以 $u$ 为根的子树（包括$u$ ）的四种情况。具体地，$f_{u,0}$ 表示链的一个端点为 $u$ ，另一个端点在 $u$ 的子树内，$f_{u,1}$ 表示路径的两个端点在 $u$ 的子树内且路径不经过 $u$ ，$f_{u,2}$ 表示路径的两个端点在 $u$ 的子树内且路径经过 $u$ ，$f_{u,3}$ 表示一条链以 $u$ 为端点，另一个端点在子树内，以及一条路径两端在 $u$ 的子树内且允许经过 $u$ 。

考虑如何转移，以下设 $v$ 为 $u$ 的直接儿子，$son_u$ 表示 $u$ 的儿子数量。

$f_{u,0}=\max(f_{u,0},f_{v,0}+son_u-1)$ ，即连接 $u$ 到 $v$ 的边。

$f_{u,1}=\max(f_{u,1},f_{v,1},f_{v,2}+1)$ ，直接继承 $v$ 的两种情况。

$f_{u,2}=\max(f_{u,2},f_{u,0}+f_{v,0}-1)$ ，将两条链直接拼起来，注意 $f_{u,0}$ 多算上了 $v$ 为根的连通块，而连接上 $v$ 后就没了，所以要减一。

以下 $f_{u,3}$ 的转移省略 $max$ 符号。

$f_{u,3}=f_{u,0}+f_{v,2}-1$ 直接作为两条路径，$f_{u,0}$ 多统计了 $v$ 的连通块，所以减一。

$f_{u,3}=f_{u,0}+f_{v,1}-1$ 和上面的类似。

$f_{u,3}=f_{u,2}+f_{v,0}-1$ 将 $v$ 到 $u$ 的路径连接起来，减掉 $v$ 的那一个连通块。

$f_{u,3}=f_{v,3}+son_u-1$ 将 $v$ 到 $u$ 的路径连接起来，多了 $son_u-1$ 个连通块。

设 $tmp$ 为之前的儿子中 $f_{v,1}$ 和 $f_{v,2}$ 的最大值，$f_{u,3}=f_{v,0}+son[u]-1+tmp-1$ 。直接根据 $f_{u,3}$ 的意义转移，将 $u$ 和 $v$ 连接，减去 $tmp$ 和 $v$ 的那两个连通块。

由于路径可以退化成链，所以 $f_{u,2}=max(f_{u,2},f_{u,0})$ ，$f_{u,3}=max(f_{u,3},f_{u,2})$。

然后考虑答案的更新。

$ans=f_{u,3}+f_{v,0}-[u=1]$ $ans=f_{u,0}+f_{v,3}-[u=1]$ $ans=f_{u,2}+f_{v,1}-[u=1]$ ，其中如果 $u$ 为 $1$ 表示 $u$ 为根，就没有上面产生的那个连通块了。

$ans=f_{u,1}+f_{v,2}$ $ans=f_{u,1}+f_{v,1}-1$

对于初始化操作，$f_{u,0}=f_{u,2}=f_{u,3}=son[u]$ 表示只选了 $u$ 这个节点，$f_{u,1}=1$ 表示只选了一个儿子，剩下了一个连通块。

时间复杂度 $O(n)$ 。

# T2 分手是祝愿

​ 给定一个长度为 $n$ 的 01 序列，每次可以操作一个位置 $pos$ ，然后 $pos$ 的所有约数上的位置会取反。当该局面的最小操作步数小于等于 $k$ 时，直接按照最小操作步数的方案操作，否则它会等概率随机一个位置操作。求使最终序列全部变为 0 的操作次数的期望乘上 $n!$ 对 $100003$ 取模之后的结果。

​ $1\le n\le 100000$ ，$0\le k\le n$ 。

​ 先考虑一个局面的最小操作步数，容易发现 $pos$ 位置只能被大于等于它的位置取反。所以我们就有乐一个贪心，从大到小操作序列中状态为 $1$ 的位置，即可得到最小操作数 $x$。所以当 $k\le x$ 时期望步数为 $x$ 。然后我们考虑 $k>x$ 的情况。我们又可以发现最小操作方案是和操作顺序无关的，所以我们从操作数上下手。我们定义最小操作数中操作的位置为需要操作的位置，设 $f_i$ 表示从需要 $i$ 次操作变为需要 $i-1$ 次操作的期望步数，当随机到的位置为需要的那 $i$ 次操作之一，期望为 $\frac{i}{n}$ ；若没有随机到，那么就会变成需要 $i+1$ 次操作的局面，那就需要 $f_{i+1}+f_i+1$ 次操作才能变成需要 $i-1$ 次操作的局面（加一表示加上随机的那一个操作）。整理一下可以得到，$f_i=\frac{i}{n}+(1-\frac{i}{n})\cdot(f_{i+1}+f_i+1)$ ，解方程可得 $f_i=\frac{(n-i)\cdot f_{i+1}+n}{i}$ ，初始化为 $f_n=1$ ，直接递推即可。最终答案为 $k+\sum_{i=k+1}^{x} f_i$ 。处理约数可以通过枚举倍数解决，时间复杂度为 $O(n\log n)$ 。

# T3 寿司餐厅

​ 有 $n$ 种寿司，第 $i$ 种寿司的类型为 $a_i$ 。如果你吃到了第 $i$ 到第 $j$ 种 $(i\le j)$ 寿司，你的收益为 $d_{i,j}$ 。如果你吃了 $y$ 种类型为 $x$ 的寿司，你会付出 $mx^2+yx$ 的代价（其中 $m$ 是一个常数）。 最大化价值和。

​ $n \le 100$ ，$a_i\le 1000$ ，$m \in \lbrace 0,1\rbrace$ ，$-500\le d_{i,j} \le 500$ 。

这是经典的最大权闭合子图问题，考虑用最小割来求解。将每个 $d_{i,j}$ 看成一种物品，$d_{i,j}>0$ 的从 $S$ 向其连一条容量为 $d_{i,j}$ 的边，否则向 $T$ 连边，容量为其相反数。当 $i\ne j$ 时，若选择了 $d_{i,j}$ ，则 $d_{i+1,j}$ 和 $d_{i,j-1}$ 也要被选择，所以连一条容量为 $INF$ 的边；当 $i = j$ 时，表明就选择了这一种寿司，就向其对应的类型 $a_i$ 连边，容量为 $INF$ 。这样我们就刻画了所有的依赖关系，接着我们考虑其余边的容量。我们发现现在只剩下 $mx^2+yx$ 的代价没有刻画。$mx^2$ 比较简单，我们直接让每种类型的寿司向 $T$ 连一条容量为 $mx^2$ 的边。对于 $yx$ ，其和数量有关，我们假设 $a_i=x$ ，我们可以让 $d_{i,i}$ 减掉 $x$ ，这样 $yx$ 的代价就自动减掉了。最终答案就是所有 $d_{i,j}>0$ 的 $d_{i,j}$ 之和减去最小割。