2020 省选题目乱做.
OJ 上有的就不写题面了.
BJOI
1v1 大战.
封印
对 $t$ 建出后缀自动机,将 $s$ 放上去匹配,对于 $s$ 的每个前缀能处理出它最长的是 $t$ 的子串的后缀.
这些后缀可以表示成 $n$ 个区间 $[l_i,r_i]$ ,对于每次询问 $[L,R]$ ,显然只需要考虑这 $n$ 个区间的贡献.
考虑所有 $l_i\le L$ 的区间,它们对答案的贡献是 $\min(\max(r_i,L-1),R)-L+1$ ,预处理前缀最大的 $r_i$ 即可.
记 $p=\max_{l_i\le L}\lbrace\min(\max(r_i,L-1),R)\rbrace$ ,考虑 $p<r_i\le R$ 的区间,贡献是 $r_i-l_1+1$ ,预处理 ST 表即可.对于 $r_i>R$ 的区间,它们的贡献会在 $r_i=R$ 处算上,对于 $l_i>L,r_i\le p$ 的区间,都没有从 $L$ 到 $p$ 长,就不用考虑.
code
联合省选 A 卷
冰火战士
首先可以将权值全部离散化,考虑有两个函数 $f(x),g(x)$ 表示当温度为 $x$ 时,冰,火能参战的人的总能量.
那么当温度为 $x$ 时,显然消耗总能量为 $2\times\min(f(x),g(x))$ .
而 $f$ 是不降的, $g$ 是不增的,只需要找到 $f$ 第一次比 $g$ 大的位置和 $f$ 最后一个比 $g$ 小的位置,二者中必有最优解.
考虑如何找出这些位置,用线段树维护这两个函数在每个位置的值,在线段树上二分,每次看一下往哪边走即可.
由于要输出最高的最优温度,所以最后还需要在线段树上向右拓展一下,找到最高的最优温度.
时间复杂度 $O(n\log n)$ .
code
组合数问题
给的多项式 $f(k)$ 可以直接拆成 $m+1$ 个单项式做,每个单项式只需要算下面这个东西:
$$
\sum_{k=0}^n x^k\binom n k\cdot k^m
$$
直接用第二类斯特林数将自然数幂展开成组合数.
$$
\begin{aligned}
ans&=\sum_{k=0}^nx^k\binom n k\sum_{i=0}^m {m\brace i}i!\binom k i \\
&=\sum_{i=0}^m{m\brace i}i!\sum_{k=0}^n x^k\binom n k\binom k i\\
&=\sum_{i=0}^m{m\brace i}i!\binom n i\sum_{k=0}^n x^k\binom{n-i}{k-i} \\
&=\sum_{i=0}^m{m\brace i}n^{\underline i} x^i\sum_{k=i}^{n-i}x^{k-i}\binom{n-i}{k-i}\\
&=\sum_{i=0}^m{m\brace i}n^{\underline i} x^i(x+1)^{n-i}
\end{aligned}
$$
对于每个单项式可以 $O(m)$ 求其贡献,时间复杂度 $O(m^2)$ .
code (代码偷懒写的 $O(m^2\log P)$)
魔法商店
2018 年集训队论文 - 浅谈保序回归问题.
首先可以注意到求出权值最大/最小的合法集合是一个带权拟阵求最大/最小权值极大独立组的问题.
若集合 $A$ 外的元素 $x$ 能替换 $A$ 内的元素 $y$ ,则必须满足调整后的权值 $v_x\ge v_y$ .
若集合 $B$ 外的元素 $x$ 能替换 $B$ 内的元素 $y$ ,则必须满足调整后的权值 $v_x\le v_y$ .
于是就形成了若干个偏序关系,转化成了保序回归 $L_2$ 问题,具体解法可以参考相关论文.代码先鸽着.
信号传递
考虑状压 dp ,从小到大依次确定每个信号站在 $S$ 序列中的编号,记录哪些编号已经被确定.
两个相邻的数会产生贡献,这个贡献可以拆到每个位置上分别计算,预处理一下贡献的系数即可.
自己不会与自己产生贡献,贡献系数只会有 $m\times 2^{m-1}$ 种,空间就能开下了,时间复杂度 $O(m2^m)$ .
code
树
AGC044C 再放送.
用 01 Trie 树维护子树 $x$ 内所有的 $v_i+d(i,x)$ .
需要实现插入一个数,合并两棵 Trie ,给插入的数整体 $+1$ , 询问插入的数异或和这些操作.
整体 $+1$ 有一个 trick, 将 Trie 树反着建,即先走低位,再走高位,修改时先对 $1$ 的方向递归修改,然后交换左右儿子.
合并就直接像线段树那样合并就行了,全局异或和可以在修改和合并的时候顺便维护一下,时间复杂度 $O(n\log n)$ .
注意因为有 $+1$ 操作, Trie 树中实际可能出现的最大值是 $v+n-1$ ,而不是 $v$ .
code
作业题
先枚举一个因子,只保留权值是它倍数的边计算贡献,最后把答案反演出来.于是瓶颈在于算所有生成树边权之和.
考虑每条边被计算了多少次,这可以用矩阵树定理转换为求一个余子式的值.
要求每条边的贡献,做一次矩阵求逆搞出伴随矩阵就行了.
具体一点的描述可以看 这里 ,把图当成有向图,强制让 $n$ 作为根,求生成内向树数目,也就是原图的生成树数目.
也可以将每条边的权值看作 $1+wx$ ,在 $\bmod x^2$ 意义下求行列式,最后一次项的系数就是所有生成树边权之和.
复杂度是 $O(n^4\max \sigma_0(w_i)$ ,可以剪下枝,如果保留某些边后图不连通,就不用计算了.
code
联合省选 B 卷
和 A 卷相同的题就不再写了.
卡牌游戏
显然从第二个位置开始,选取那些前缀和 $>0$ 的位置,将它们的前缀和加入答案即可.
code
信息传递
把询问离线下来挂在每个点上,做一次点分治即可统计出答案.
如果强制在线,则可以考虑在每个分治中心把信息存下来, 询问时在点分树上跳即可,空间复杂度会多一个 $\log$ .
code
幸运数字
显然每种优惠都可以拆到不超过 $2$ 个区间上进行贡献,端点离散化后打上差分标记,最后扫一遍统计答案即可.
由于还要输出要求的最优位置,还要额外处理一些细节.
code
丁香之路
枚举 $t$ ,考虑第 $t$ 个人的答案.
假定已经确定了每条边要走多少次,那么这个方案合法当且仅当它们能构成 $s\to t$ 的欧拉路.
问题可以归纳为,已经加了 $m$ 条给定边,此时 $s,t$ 以及其他有度数的点形成集合 $S$ ,还要加若干条边(每条边可以被加多次),使得每个点度数满足各自的奇偶性要求,且 $S$ 内所有点连通,最小化加入的所有边权值总和.
不难发现,我们新加的边中只会用到 $(x,x+1)$ 的边,其他边可以被组合出来,于是只用再考虑这 $n-1$ 条边.
此时还需要连奇数条边的点显然有偶数个,我们将它们按顺序两两串起来,就满足了度数的限制.
此时 $S$ 集合中的点仍可能不连通,需要将各个连通块用边连起来,并且为了满足度数限制,选到的边都要走两次.
由于可能会用到 $S$ 外的点来使 $S$ 连通,直接做是斯坦纳树问题,不是 MST 问题,需要进一步观察图的性质.
若 $x$ 不在集合 $S$ 中,则 $(x-1,x),(x,x+1)$ 这两条边一定是同时被选或同时不被选,可以缩在一起,缩完之后的边一定都是连接 $S$ 连通块之间的边,用这些边做一次 MST 即可,由于权值不会达到 $n$ ,对它们的排序可以用计数排序.
时间复杂度 $O(n^2\alpha(n))$ .
code
SCOI
游戏
给定二维平面上的两个点 $S,T$ ,以及其他 $n$ 个点 $p_1,p_2,\dots,p_n$ ,询问有多少组 $i<j$ 满足 $T$ 在三角形 $SP_iP_j$ 的外接圆内部(不包含边界).
$n\le 10^5$ ,保证没有点重合,没有三点共线的情况,点的坐标可以认为是在 $[-10^9,10^9]$ 内随机的.
记圆心为 $O$ ,需要满足 $|OS|>|OT|$ ,连接 $ST$ ,做其中垂线,划分出两个半平面,圆心必须在靠近 $T$ 的那个半平面内.
外心是两条边的中垂线交点,记线段 $SP_i$ 的中垂线为 $L_i$ ,变为询问这 $n$ 条直线之间有多少个交点在给定的半平面内.
因为坐标随机,所以可以有精度很垃圾的做法,先通过平移,旋转,把 $S$ 搞到原点, $T$ 搞到 $x$ 轴正半轴上某个位置.于是只需要求 $x>k$ 的交点 $(x,y)$ 个数,假定两条直线分别是 $y=ax+b,y=cx+d$ ,则要求 $x=\frac{d-b}{a-c}>t$ .
把所有直线拿来按照斜率从小到大排序,枚举 $y=ax+b$ ,考虑 $c<a$ 的所有直线 $y=cx+d$ ,此时 $a-c>0$ ,要求变为 $d-b>ta-tc$ ,即 $tc+d>ta+b$ ,不难发现就是个关于 $a,ta+b$ 的二维数点,随便搞一搞即可.
行走
在三维空间中随机游走.
初始在 $(0,0,0)$ ,每一步会从 $ (x,y,z)$ 等概率走到
$$
(x+1,y+1,z+1),(x+1,y,z),(x,y+1,z),(x,y,z+1),\\
(x-1,y,z),(x,y-1,z),(x,y,z-1),(x-1,y-1,z-1)
$$
这八个点中的一个.
有 $m$ 次询问,每次询问走了 $t$ 步后,在 $(a,b,c)$ 的概率.
$a,b,c$ 可能是通配符, 表示并不关心这一维的坐标,保证 $a,b,c$ 不会同时是通配符 .
答案对 $998244353$ 取模, $1\le m\le 2\times 10^5,0\le t,|a|,|b|,|c|\le 2\times 10^5$ ,恰好有一个通配符的询问不超过 $50$ 个.
Case 1: 恰好有 2 个通配符
可以先将通配符换到 $b,c$ 上,答案为
$$
\begin{aligned}
ans&=2^{-t}[x^a] (x+2+x^{-1})^t \\
&=2^{-t}[x^{a+t}] (x^2+2x+1)^t \\
&=2^{-t}[x^{a+t}] (x+1)^{2t} \\
&=2^{-t}\binom{2t}{a+t}
\end{aligned}
$$
单次询问时间复杂度 $O(1)$ .
Case 2: 恰好有 1 个通配符
可以先将通配符换到 $c$ 上,答案为
$$
\begin{aligned}
ans&=8^{-t}[x^ay^b] (xy+x+y+1+x^{-1}+y^{-1}+1+x^{-1}y^{-1})^t\\
&=8^{-t}[x^ay^b] ((x+1)(y+1)+(x^{-1}+1)(y^{-1}+1))^t\\
&=8^{-t}[x^ay^b]\sum_{i=0}^t \binom t i(x+1)^i(x^{-1}+1)^{t-i}(y+1)^i(y^{-1}+i)^{t-i}\\
&=8^{-t}\sum_{i=0}^t\binom t i[x^{a+t-i}] (x+1)^t\cdot[y^{b+t-i}] (y+1)^t\\
&=8^{-t}\sum_{i=0}^t\binom t i\binom{t}{a+t-i}\binom{t}{b+t-i}
\end{aligned}
$$
单次询问时间复杂度 $O(t)$ .
Case 3: 没有通配符
答案为
$$
\begin{aligned}
ans&=8^{-t}[x^ay^bz^c] (xyz+x+y+z+x^{-1}+y^{-1}+z^{-1}+x^{-1}y^{-1}z^{-1})^t\\
&=8^{-t}[x^{a+t}y^{b+t}z^{c+t}] (x^2y^2z^2+x^2yz+xy^2z+xyz^2+yz+xz+xy+1)^t \\
&=8^{-t}[x^{a+t}y^{b+t}z^{c+t}] (xy+1)^t(xz+1)^t(yz+1)^t
\end{aligned}
$$
若 $xy,xz,yz$ 分别选了 $k_1,k_2,k_3$ 个,则有 $k_1+k_2=a+t,k_1+k_3=b+t,k_2+k_3=c+t$ ,可以直接解出 $k_1,k_2,k_3$ 的值,根据二项式定理,答案即为 $8^{-t}\binom t {k_1}\binom t {k_2}\binom t {k_3}$ .
单次询问时间复杂度 $O(1)$ .
FG
有 $n$ 个数,初始都是 $0$ ,有 $m$ 种操作,每个操作有 4 个参数 $l,r,v,c$ ,表示这个操作可以给 $[l,r]$ 内所有数异或上 $[1,v]$ 内的一个任意一个数,代价为 $c$ .
每个操作可以执行多次,一个操作序列的代价是使用过的操作代价最大值,每个操作序列会得到若干种终止状态,每种终止状态的贡献是能得到它的操作序列中代价的最小值,询问所有可能被得到的终止状态的贡献总和.
答案对 $10^9+7$ 取模, $1\le n,m\le 10^5,1\le l\le r\le n, 1\le c\le 10^9,1\le v\le 2^{16\times 2^{16}}$ , $v$ 会通过给定的随机数生成器来读入.
首先容易发现可以直接把 $v$ 换成最大的满足 $2^k\le v$ 的 $2^k$ ,因为每次都只修改一个二进制位,就能凑出 $\le 2^k$ 的数.
若用 $c\le x$ 的操作能得到 $f(x)$ 种终止状态,则答案为 $\sum_x x\cdot (f(x)-f(x-1))$ .
将所有操作按照 $c$ 从小到大排序,依次加入每个操作,并维护当前的 $f(x)$ .可以对每个二进制位分开考虑, $f(x)$ 是每个二进制位终止状态数量的乘积.对这 $n$ 个数做异或意义下的差分,则每个操作相当于可以给两个数异或上 $1$ ,对每个二进制位维护一个线性基, $f(x)$ 即为 $2^t$ ,其中 $t$ 表示所有二进制位的线性基大小之和.
由于加入的数都是只有两个位置上是 $1$ ,可以看成是在 $l,r+1$ 之间连了一条边,不难发现,若加入一条边时两端点未连通,则线性基大小会增加一,于是可以用并查集来维护每个线性基,就得到了一个 $O(n\cdot \alpha(n)\cdot \log v)$ 的做法.
注意到若加入边时,端点已连通,那么可以用新加的边去替换环上的某条边,显然将 $v$ 更小的替换掉,就能保证不变劣.用 LCT 对 $n+1$ 个点维护一个关于边权 $v_i$ 的最大生成树即可,时间复杂度 $O(n\log n)$ .