联合省选2021 完整题解

详略程度和难度无关。

A卷 Day1T1 卡牌游戏

考虑枚举最小值$minv$（$minv$一定是某个$a$或$b$,排序之后枚举即可）.此时只需令最大值最小即可（当然要满足$m$的限制）。

为了满足最小值的限制，我们要翻一个前缀$[1,Lt]$.显然$Lt$关于$minv$非严格增。注意特判翻出的$b<minv$的情况。

为了令最大值最小，我们要翻一个后缀$[Rt,n]$.注意$Rt$要满足$m$和$minv$的限制。

考虑比较$[Rt,n]$和$[Rt+1,n]$.前者导致的最大值是$max(Sufmax_{Rt},a_{Rt-1})$，后者导致的最大值是$max(Sufmax_{Rt+1},a_{Rt})$.如果后者更小则增加$Rt$即可（注意同样优时也要增加$Rt$, 因为可能这个函数有一段平的，之后的某个位置才变小）

此外，当$minv$增大时$Rt$的下界会增大，其余不变，因此最优的$Rt$也是非严格增的，在上一个的基础上继续往右走即可。

瓶颈在于排序，为$O(n\log n)$或$O(n)$

My code

A卷 Day1T2 矩阵游戏

首先构造一个符合和的限制但不符合值域限制的矩阵$M$.这是很容易的，钦定第一行与第一列均为0 ，其余便可唯一推出。

考虑能怎样修改使其合法。为了使和的限制不被破坏，一定是若干次（可能为负）以下两种操作：

• 对某一行，奇数列+1，偶数列-1
• 对某一列，奇数行+1，偶数行-1

这样就简单了，设第$i$行操作$x_i$次，第$j$列操作$y_j$次，每个位置$(i,j)$的限制形如：
$$ \begin{align} M_{i,j}+x_i+y_j\in[0,10^6]\quad (1,1)\\\\ M_{i,j}-x_i+y_j\in[0,10^6]\quad (1,0)\\\\ M_{i,j}+x_i-y_j\in[0,10^6]\quad (0,1)\\\\ M_{i,j}-x_i-y_j\in[0,10^6]\quad (0,0)\\\\ \end{align} $$
$(1,1)$表示$i,j$都为奇数，其余同理。
恭喜，这样是没法做的

接下来是难以想到的操作：将$x_i,y_j$略作修改，具体的，对$i\mod 2=1,x_i:=-x_i$,对$j\mod 2=0,y_j:=-y_j$.这样操作之后，限制形如：
$$ \begin{align} M_{i,j}-x_i+y_j\in[0,10^6]\quad (1,1)\\\\ M_{i,j}+x_i-y_j\in[0,10^6]\quad (1,0)\\\\ M_{i,j}+x_i-y_j\in[0,10^6]\quad (0,1)\\\\ M_{i,j}-x_i+y_j\in[0,10^6]\quad (0,0)\\\\ \end{align} $$
都是两个变量的差的不等式，可以转化为差分约束模型求解，以$M_{i,j}-x_i+y_j\ge 0$为例：$\Rightarrow y_j+M_{i,j}\ge x_i$,令第$j$列代表的点向第$i$行代表的点连边权为$M_{i,j}$的边。

或者你也可以先猜到是用差分约束，然后把初始形式转化为差分约束的形式。

复杂度即$O(Check_Negative_Ring(n+m,nm))$ 。用spfa/Floyd 实现即可。

My code

A卷D1T3 图函数

考虑有序对$(u,v)$在$G$中产生贡献的条件：存在一个环$R$经过$u,v$且$u$为$R$上编号最小的。

进一步，若求出$T(u,v)$表示所有$R$中边的编号最小值最大的，那么$(u,v)$会对所有$i\le T(u,v)$的$G_i$产生贡献。

考虑如何求$T(u,v)$.

我的做法是，考虑Floyd的过程是加入中转点$k$,且加入$S$中所有点作为中转点后，我们求出的最短距离$dis(u,v)$表示$u$到$v$只经过$S\cup\{u,v\}$中的点的所有路径中边的编号最小值的最大值。

那么，若从大到小加入$k$，此时$(u,v)$的路径上所有点编号都$\ge k$.枚举$v\ge k,T(k,v)=\min(dis(k,v),dis(v,k))$.

时间复杂度$O(n^3)$,但循环展开之后能过！

也有$O(nm)$的做法，大致思路类似。

My code(Floyd)

A卷 Day2T1 宝石

关注$P_i$互不相同 的性质。这个性质指出，如果起点在$u$的子树内且匹配到了$u$且终点为根,那么下一个匹配点是唯一确定的（上一个也是）。因此，下$x$个匹配点也是唯一确定的。预处理每个点往上第一个匹配$P_1$的点$u$,然后可以倍增找出最多能匹配的数量，这样就$O(n\log c)$预处理,$O(\log c)$每次查询的复杂度解决了链上的问题。

对于一般情况，$s\rightarrow LCA$的部分同样可以这样处理，记匹配到$p$。对于$LCA\rightarrow t$的部分，考虑二分答案。设当前要判断能否匹配$[p+1,k]$ .先离线求解$t$往上第一个匹配$P_k$的点，然后同样倍增（这个倍增是倍增前驱）找出最多能匹配的位置$q$,若$q\le p+1$即可。

预处理$O(n\log c)$,$O(\log^2 c)$每次查询。

My code

A卷 Day2T2 滚榜

先考虑暴力枚举所有排列。我们可以考虑贪心，最小化封榜后过题数$t$：若$t(t\le m)$可行，那么一定可以让最后一队再过$m-t$题，这样仍可行。这样是$O(n!n)$的

优化也很显然，考虑状压DP。

暴力是，$f(S,i,w,sum)$表示用了集合$S$,最后一个是$i$,$i$额外过了$w$题，$S$额外过题数和为$sum$.

这样是$O(2^nn^2m^2)$,不太行。

按照套路，$w$是没用的，我们直接费用提前计算，就是说加入一个$j$,若$j$至少要过$x$题，那么之后共有$(n-|S|)$个人要因为$j$再过$x$题。

这样就是$O(2^nn^2m)$了，空间$O(2^nnm)$.

实际上，$\sum_i\binom{n}{i}i(n-i)=2^{n-2}n(n-1)$，计算量至多159744000，是合理的
My code

A卷Day2T3 支配

先求支配树$DT$。

当然可以用polylog的方法，但没必要，枚举删掉点$u$再从1开始bfs，走不到的就受$u$支配，这样就能$O(n(n+m))$求出每个点的支配集;又由于$fa_u$的受支配集大小恰为$u$的受支配集大小减1，就可以$O(n(n+m))$求出$DT$。

考虑一个点$u$，$DT$上父亲为$fa$,受支配集$D_u$变化仅当$D_{fa}$改变或$fa$不再支配$u$.这个等价于若$fa$不再支配$u$,则$u$子树中所有点受支配集都改变。

所以只需判断$fa$是否仍然支配$u$.

记新加入的边为$(x,y)$,那么$fa$不再支配当且$u$仅当原图存在$1\rightarrow x$和$y\rightarrow u$的路径且均不经过$fa$（注意$x,y\ne fa$）。

存在$1\rightarrow x$不经过$fa$显然仅当$fa$不支配$x$.考虑预处理$f(i,j)$表示在不经过$fa_i$的情况下$j$能否到达$i$.那么存在$y\rightarrow u$仅当$f(u,y)=1$.直接在反图上从$i$开始bfs即可预处理好。

询问时候枚举所有$u$判断即可。

总复杂度$O(n(n+m+Q))$

可能轻微卡常，但这些技巧显然省选选手都能掌握。

My code

B卷 数对

枚举$i$的所有倍数的复杂度是$O(A/i)$,去重之后复杂度是$O(\sum_i A/i)=O(A\log A)$.

B卷 取模

我居然这种题都不会了。。。

考虑暴力枚举$k$. 令$b_i=a_i\mod a_k$,就是找一对$b_i+b_j$最大,贡献$(b_i+b_j)\mod a_k$，或找一对$b_i+b_j<a_k$,贡献$b_i+b_j$.将$b$排序后双指针即可。复杂度$O(n^2\log n)$.

然而只要加上两个优化，当$a_k$小于当前答案时直接结束，则不同的有效$a_k$至多$O(\log A)$个。

证明也很容易：记最终答案为$ans$.$a_k$之后两个不同的数为$a_{k+1},a_{k+2}$
$$ (a_{k+1}+a_{k+2})\mod a_k\le ans\\\\ \Rightarrow a_{k+1}+a_{k+2}-a_k\le ans\\\\ \Rightarrow (a_{k+1}-ans)+(a_{k+2}-ans)\le a_k-ans $$
所以数列$f_i=a_i-ans$是至少是斐波那契级别增长，因此不同的有效$k$至多$O(\log A)$个。

总时间复杂度$O(n\log n\log A)$

My code