CSP-S 2022复赛认证

这里是热爱OI的予惜捏（冒头）本次专栏打算讲一讲CSP-S复赛的真题。

首先来看T1：

可以发现这道题n ≤ 2500，我们可以枚举起点使用广搜求出任意两个点之间的最短路，如果两点之间最短路≤k+1，那么它们就可以连续出现在行程中。

40分做法：由于n≤20，直接使用4层循环枚举A、B、C、D的下标，再验证是否满足要求；

70分做法：考虑只枚举A、B、C，其实D的值可以使用贪心法求解，D到C的距离≤k+1，并且D到1号点的距离≤k+1，那么D一定是满足条件的点中权值最大的那个。

这里需要注意的是：权值最大的点也可能是A或B中的一个，由于景点不能重复，所以我们需要选权值第二大的点，但是权值第二大的点也有可能是A或B中的一个，这种情况我们需要选择权值第三大的点。

因此我们需要预处理，对于每个点i，需要求出到i点和1号点的距离都≤k+1的点里面，权值的第一大、第二大、第三大，然后再三重循环枚举A、B、C点，D点就是C点的前三大点中的一个；

100分做法：预处理的部分还是不变，我们可以发现A点的性质和D点是非常类似的，A到B点和A到1号点的距离都≤k+1。我们可以只枚举B点和C点，可以发现A点必须是B点前三大点中的一个，D点必须是C点前三大点中的一个（需要考虑到B点前三大点和C点前三大点之间考虑会重合）。

时间复杂度为O(n2)；

T2：

首先使用贪心法思考问题，如果第一个人选的数字已经确定了，那么第二个人肯定会遍历整个区间，选出其中乘积最小的对应数字。对于第一个人来说，他选数的时候其实可以预见第二个人选的数字。

40分做法：直接枚举第一个人选的数字，然后遍历区间求出第二个人选的数字，实质是选每行最小值中的最大值，时间复杂度为O(nmq)。当数据满足特殊性质2时，时间复杂度为O(nq)；

65分做法：再考虑到特殊条件1：Ai,Bi>0，不管第一个人选的数字是什么，第二个人选的数字一定是区间中最小的数字。所以第一个人一定会选区间中最大的数字。我们可以使用ST表或者线段树维护A数组的区间最大值和B数组的区间最小值，然后对于满足特殊条件1的点，答案一定是A数组指定区间的最大值×B数组指定区间的最小值；

100分做法：按照上述讨论，如果Ai和Bi都大于0，那么取的数字一定是区间最值。拓展上述结论会发现：如果第一个人取的是正数，第二个人一定会取区间的最小值；如果第一个人取的是负数，第二个人一定会取区间最大值。在此基础上考虑第一个人的取值

1.如果他取正数：当第二个人取的区间最小值是正数时，第一个人应该取最大的正数；如果第二个人取的区间最小值是负数时，第一个人应该取最小的正数（或者有0取0）;

2.如果他取负数：当第二个人取的区间最大值是正数时，第一个人应该取最小的负数；如果第二个人取的区间最小值是负数时，第一个人应该取最小的负数。

综上，第一个人只会取区间中四种数中的一个：最小的负数、最大的负数、最小的非负数、最大的非负数；而第二个人只会根据第一个数字的符号取区间的最大值或最小值。使用ST表，维护A数组的区间最大负数、区间最小负数、区间最大正数、区间最小非负数，再维护B数组的区间最大和区间最小，然后每轮游戏只有四种方案，求出其中最大值就能得出这一轮的答案了。

时间复杂度为O(nlogn)；

T3：

首先要把描写得很复杂的反攻解释出来：需要从每个点出发，都能进行无限次虫洞穿梭，其实是要求从任意点出发能走到环上。每个点只能有一个从该点出发的虫洞，其实是图上每个点的出度为1。根据图论知识，有向图中每个点的出度为1，一定会形成环，并且所有点都能走到环上，因此反攻当且仅当所有点的出度为1。

40分做法：先存下每个点的初始邻居，每次修改时直接修改邻接矩阵，然后在修改过程中维护每个点的出度，如果n个点的出度都是1，输出YES，否则输出NO；时间复杂度O(nq)；

60分做法：如果没有4号操作，那么我们可以使用set对每个点维护两个集合，分别存储完好的入边的起点和被摧毁的入边的起点。每次1、2号操作时，可以在v对应集合中删除u，并且把u加入另一个集合，同时修改u的出度。在3号操作中，直接枚举u点的所有完好的入边，执行摧毁操作，并维护对应起点的出度。如果一条边被摧毁两次，说明它至少被修复了一次，由于最多能修复不超过q条边，所以整个程序最多摧毁m+q条边，再加上set的复杂度，时间复杂度为O((m+q)logn)；

100分做法：既然考虑使用set对每个点i分别维护好的虫洞的起点集合S[i]和坏的虫洞的起点集合T[i]，但是在4号操作时，需要枚举set中的所有点，把它们从坏集合移动到好集合，因此超时（虽然set合并可以做到O(logn)，但是修改起点的入度必须枚举）。

可以考虑使用Hash法存储集合，合并和修改时时候都是O(1)的。

设定一个足够大的质数P，令pi = p的i次方，假设有一个集合为{1,3,4,5}，那么可以对应Hash值为p1+p3+p4+p5（还需要按照指定模数进行模运算，为了便于描述以下均省略），这个值是唯一对应的。如果我们删除3到i的边，只需要让Hash值减去p3；如果我们修复7到i的边，只需要让Hash值加上p7，非常方便。

对于3、4号操作，如果点i的好的虫洞的起点集合对应Hash值为s[i]，坏的虫洞的起点集合对应Hash值为t[i]。3号操作执行后，好集合的所有边都要移入坏集合，此时点i的新的Hash值s'[i]=0,t'[i]=s[i]+t[i]；4号操作执行后，坏集合的所有边都要移入好集合，此时点i的新的Hash值s'[i]=s[i]+t[i],t'[i]=0。引入Hash值的最终目的其实是避免记录出度的工作，我们可以存储所有虫洞的起点集合（可重复集合），这个集合是一个大小为n的不重复集合，此时答案就是YES。求出初始状态下，所有虫洞的起点集合对应的Hash值Q，比如如果初始集合{1,1,2,3,5,5,5}，那么Q= 2p1+p2+p3+3p5。如果Q=p1+p2+⋯+pn，此时答案就是YES，否则答案是NO。

对于1号操作，Q-=pu；对于2号操作，Q-=s[u]；对于3号操作，Q+=pu；对于4号操作，Q+=t[u]。每次操作对Q的维护都是O(1)的。

时间复杂度为O(n+m+q)；

最后来看T4：

观察数据可以发现1≤k≤3，由于k的值很少，肯定对做法有影响，可以分别考虑不同的情况。当k=1时，路径中不能跳过任何一个点，所有只能直接从起点走到终点。当k=2时，不难想到我们停留过的点都是在起点到终点的简单路径上的。因为如果想规避掉路径上下一个点u时，我拐到这个点的某个儿子v上，继续走还是只能走到u的下一个点w，而从当前点可以直接走到w，不需要走到v。当k=3时，类似于上述情况，走到下一个点的儿子或者孙子都是没有意义的，我们停留过的点只能是起点到终点的简单路径中的点或者这些点的邻接点。

8分做法：使用深搜，每次直接枚举下一个点，最好先预处理存储距离小于等于k的点；

24分做法：当k=1时，从起点到终点的所有点都要停留，所以答案就是树上路径权值和，直接求出lca，然后使用差分法求出路径权值和即可；

44分做法：当k=2，并且n比较小的时候，我们可以把树上路径取出来，然后对取出来的路径使用线性DP。设f[i]为从起点出发停留在路径第i个点的最小时间，那么f[i] = min(f[i-1],f[i-1])+t[i]，其中t[i]等于第i个点的点权。最终答案为最后一个点的f值；

76分做法：当n比较小的时候并且k=3的时候，对于路径上的点的所有邻接点i，我们令g[i]为从起点出发停留在路径第i个点的邻接点的最小时间，如下图所示；

我们设c[i]表示i点邻居的最小处理时间。对于路径上第i个点x_i ，如果它是路径上的点，有

这种方法每次询问需要访问路径的所有点及其邻接点，时间复杂度为O(nq)；

100分做法：上述方法需要遍历路径上的所有点，我们可以尝试使用倍增法把DP的一些转移提前处理。这样子合并DP转移的时间复杂度可以变成O(logn)。重定义矩阵乘法A=B·C为

很明显这样也符合结合律；

当k=2时，DP转移可以表示成：

当k=3时，可以把之前的DP表示成一个5×5的转移矩阵，但是这样子每次矩阵乘法需要5的3次方个操作，时间上无法接受，需要简化一下DP方程。

简化完毕后，该题即可满分。