六省联考2017 题解汇总

题面自己找找,loj 和洛谷上都有。

Day1

T1 期末考试

按照题意模拟。

T2 相逢是问候

首先模数不是质数,所以要用扩展欧拉定理来对幂取模。

扩展欧拉定理是需要讨论指数是小于 $\varphi (p)$ 还是大于等于的,需要比较麻烦的特判。

如果手玩的话会发现这么一件事情:对于 $c ^{c ^{c ^{c ^{\cdots}}}}$ 这个式子而言,嵌套到了一定的层数之后这个式子的值在模意义下不会再改变(因为每次都会让上层应用上欧拉定理,而 $\varphi (\varphi(\varphi(p)))$ 在嵌套多次后会变成 $1$)。

众所周知的是 $\varphi(n)$ 这个函数嵌套 $\log n$ 层就会变成 $1$。证明不展开了,分奇偶讨论即可。

这样的话整个序列的势能是一定的,考虑用并查集跳过那些已经到达界,修改不再变化的点,每次暴力修改即可。

由于层数 $\log n$ 层,每次修改需要 $O(\log n)$ 的快速幂,还有 $\log n$ 次修改,总复杂度 $O(n \log ^3 n)$。由于模数很少,且都是 $\varphi$ 嵌套的形式,考虑预处理好他们的根号次幂,光速幂即可做到 $O(n \log ^2 n)$。实际上直接将阈值设成 $6$ 就可以很快的跑过了。

T3 组合数问题

可能这就是菜鸡的水平吧……这题没做出来。

考虑要求的式子的组合意义,相当于是在 $nk$ 个数中选出个数模 $k$ 为 $r$ 的方案数。考虑组合数的原始式子,即 $f _{i, j} = f _{i - 1, j - 1} + f _{i - 1, j}$,发现这个式子放到模 $k$ 意义下就可以做出来了,直接矩幂 $O(k ^3 \log n)$。

也可以考虑倍增 DP,也即 $f _{2n, i + j} \gets f _{n, i} f _{n, j}$,可以理解成讨论前 $n$ 和后 $n$ 个的选取情况。暴力卷积复杂度 $O(k ^2 \log n)$。

当然这里也可以用生成函数的方式来解释这个倍增 DP。可以去看洛谷上的题解。

Day2

T1 摧毁树状图

坑分类讨论题。

首先连通块数等于点数减边数,也就相当于找到两条链使得边数减点数最大。

先踢掉两条链相交于一点的情况不考虑,考虑不相交的情况。可以发现对于一个子树而言答案有 4 种情况:

  1. 答案不经过根,展开得到两种。
  2. 答案经过根,展开得到两种,并且还要求出一个点到其子树内延伸一条链加上其子树内另一条链的最大值。这个也要讨论起来维护。

相交的就枚举交点,两条链要么出子树要么不出。如果出了就换根一下得到到子树外的链的最优答案,没出就相当于选四个最大的链拼起来。

注意一个很坑的地方。一开始自己推的式子是对于两条单独的链而言的,为 $\sum _{i = 1} ^m d _i - 2m + 1$。但是在两条链有公共边(指的是每个点连出去的边)的情况下,把这个式子加起来的时侯要减 $1$,三条链减 $2$,依此类推。要着重注意这种情况的判断。

可以做到 $O(n)$,偷懒用了 std::multiset 变成了 $O(n \log n)$。这种 shit 题考场上真的码的完吗

T2 分手是祝愿

首先要发现一个很重要的性质:如果将按下每个灯所带来的影响写成一个长度为 $n$ 的 $01$ 向量,可以发现这些向量是线性无关的,也就是按一个灯不能被其他灯的组合表示出来。

要证明倒是很简单。容易知道任意长度为 $n$ 的 $01$ 序列都可以被他们表示出来,考虑如下方式:

从后往前遍历,遇到 $0$ 不管,遇到 $1$ 将其约数位置异或上 $1$。

于是他们的张成大小为 $O(2 ^n)$,又因为只有 $n$ 个向量,所以这 $n$ 个向量一定线性无关。

由此也可以得到这个方式得出来的就是最小的操作次数。于是设 $f _i$ 表示一个要操作 $i$ 次的序列,期望要多少次才能到 $i - 1$ 次的序列。有转移:

$$
f _i = \frac i n + \frac {n - i} n (f _i + f _{i + 1} + 1)
$$

移项之后递推即可。$O(n \log n)$,因为要枚举约数算出一开始的序列的操作次数。

T3 寿司餐厅

好像是一道偏简单的网络流?本来因为 T1 的关系看这题的时间就很少,加上对网络流不熟练,打个暴力走人还算正常。

需要注意到题意里面一些特别诡异的地方:每个收益只会被获得一次,每个点的代价也只会被消耗一次,再加上这些权值正负不定,这些条件直接把 DP 限制死了。

看到数据范围,可以考虑用网络流来解决这个问题。

先考虑抽象出来一个模型。可以发现,如果选择了一个区间 $[i, j]$,那么其子区间内的收益和代价都会被选中,可以回忆起一个重要的模型:最大权闭合子图。

最大权闭合子图:给定一个 $n$ 点 $m$ 边的有向图,点有点权,选出一个点集,满足这个点集的所有出边所指向的点都在点集内(也就是「闭合」子图),最大化选的点权和。

最优的情况是将大于 $0$ 的点权全部选中,但是这种方案不一定合法。考虑用最小割来调整最优方案。

如果一个点点权小于 $0$,向汇点 $T$ 连流量为 $-a _i$ 的边;否则从源点向其连流量为 $a _i$ 的边。割掉了分别表示不选和选。其他的边建流量为 INF 的边,表示不准割。

用所有大于 $0$ 的点权减去最小割就是答案。

每一个区间都代表一个点,$[i, j]$ 向 $[i + 1, j], [i, j - 1]$ 连边表示强制选择,然后 $[i, i]$ 单独向 $a _i$ 这个类型连边,因为 $a _i$ 这个类型被选会单独带来 $a _i ^2$ 的代价。

然后跑最大权闭合子图即可。