3rd ucup 记录
Arghariza
·
·
个人记录
ucup 记录。其实好像也没打几场，场切了的就更少了。
The 3rd Universal Cup. Stage 17: Jinan
I
一如既往的只会做 I。
相当于用若干条边数 \ge 2 的路径覆盖所有边，于是就是用若干条边数为 2 或者 3 的路径覆盖所有边。
只用边数 2 的路径覆盖是简单的，有解当且仅当 n 为奇数，直接从底向上贪心将每个点的每个儿子两两配对，剩下一个再和父亲配对即可。
**The 3rd Universal Cup. Stage 16: Nanjing**
B
诈骗题。
考虑只有 $01$ 怎么做。由于每次删相邻两个数之后，其余数下标的奇偶性不变，所以我们把奇数位翻转，也就是 $a_i\gets 1-a_i,\forall2\nmid i$，相当于消掉相邻的 $01$ 或者 $10$。于是在末尾插入一个数时能消就消，答案就是 $0$ 的个数和 $1$ 的个数的差。
于是相当于把任意的 $2$ 替换成 $0/1$，使得 $0,1$ 个数的差最少。贪心即可。
G
考虑点分治。设当前确定 $s$ 在 $S$ 连通块内。
如果 $|S|=1$，即 $S$ 中只有一个点，则输出连通块内的唯一点即可。
如果 $|S|=2$，即 $S$ 中有 $(u,v)$ 一条边，那么询问 $(u,v)$ 就可以得到答案。
否则我们拿出 $S$ 的重心 $u$，考虑 $u$ 的出边 $v_1,v_2,\cdots,v_m$。其中 $2\le m\le 3$。
如果 $m=2$，那么询问 $(v_1,v_2)$。$t=0$ 则递归到 $v_1$ 子树中，$t=1$ 则答案为 $u$，否则递归到 $v_2$ 子树中。
如果 $m=3$，那么将 $v_1,v_2,v_3$ 子树大小从大到小排序，询问 $(v_1,v_2)$。$t=0$ 则递归到 $v_1$ 子树中，$t=1$ 则递归到 $S\setminus sub(v_1)\setminus sub(v_2)$，否则递归到 $v_2$ 子树中。
询问次数至多 $\lfloor\log n\rfloor$。
I
为啥做这题做了这么久，还是在 qwqwf 的指导下过的。我是做 I 大师（确信）。
显然就是算 $\le k$ 的方案数，容斥一下变成 $(nm)!-(nm-s)!s!\cdot f(s)$，其中 $s$ 表示 $>k$ 的数的个数，$f(s)$ 为将 $s$ 个 X 填入 $n\times m$ 的矩阵中，使得每行每列至少有一个 X 的方案数。
然后再容斥一些行、列没有 X，其余随便填：
$$
f(s)=\sum\limits_{i=0}^n\sum\limits_{j=0}^m(-1)^{n+m-i-j}\dbinom{n}{i}\dbinom{m}{j}\dbinom{ij}{s}
$$
列出 $s$ 的生成函数 $F(x)=\sum_{i}f(i)x^i$：
$$
\begin{aligned}
F(x)
&=\sum\limits_{s=0}^{nm}\sum\limits_{i=0}^n\sum\limits_{j=0}^m(-1)^{n+m-i-j}\dbinom{n}{i}\dbinom{m}{j}\dbinom{ij}{s}x^s\\
&=\sum\limits_{i=0}^n\sum\limits_{j=0}^m(-1)^{n+m-i-j}\dbinom{n}{i}\dbinom{m}{j}(1+x)^{ij}\\
&=f(0)+\sum\limits_{d=1}^{nm}(1+x)^d\sum\limits_{i\mid d}(-1)^{n+m-i-d/i}\dbinom{n}{i}\dbinom{m}{d/i}
\end{aligned}
$$
于是枚举 $d,i$ 就能求出 $F(x-1)$ 是啥了，求 $F(x)$ 就多项式平移一下，卷积即可。
复杂度 $O(nm(\ln nm+\log nm))$。
**The 3rd Universal Cup. Stage 15: Chengdu**
F
感觉是前期题啊？
将 $s_i$ 从小到大排序，这样一定是取连续一段为一组最优。记 $sum_i$ 为 $s_i$ 从小到大排序后的前缀和，由某些基本不等式可知 $i\to j$ 的转移贡献函数 $w(i,j)$ 大概形如 $\sqrt{(j-i)(sum_j-sum_i)}$ 状物。
这个东西显然又有凸性又有决策单调性，wqs 二分 + 任意决策单调性优化算法即可。
**The 3rd Universal Cup. Stage 13: Sendai**
D
打表找规律，结束前 2 分钟启动过题！
不会证明，先固定一个 $N$，打个表出来大概长这样：
$$
F_i=
\begin{cases}
1 &i=1\\
K\cdot F_{\frac{i}{2}} &2\mid i\\
F_{\frac{i-1}{2}}+F_{\frac{i+1}{2}} &2\nmid i,i\neq 1
\end{cases}
$$
这里的 $K$ 是一个只和 $N$ 有关的东西。先不管这个 $K$，我们要求的就是 $F_M$。直接按照这个式子递归 + 记忆化复杂度就是对的。然后再对 $K$ 观察一下，发现一个递推式：
$$
K_i=
\begin{cases}
3 & i=0\\
0 & i=1\\
2 & i=2\\
K_{i-2}+K_{i-3} & i\ge 3
\end{cases}
$$
矩阵快速幂就可以求出 $K_N$，于是就做完了。
H
首先有一个显然的 dp，设 $f_i$ 为 $i$ 开头的最大后缀串。那么有 $f_i=\max(A_i+f_{i+1},f_{i+k})$。这里的 $+$ 指的是字符串拼接。
然后有人直接线段树这个 dp 值的哈希过了。然而我们只需要维护 $f_i$ 的首字母，当 $A_i<f_{i+k}$ 的首字母时直接删掉 $i\sim i+k-1$，否则贪心地选择不删即可。
求答案就标记一下 dp 过程中删掉的位置的开头，从开头向后跳就行了。复杂度 $O(n)$。
I
先随便拿出一个点 $u$，问其余所有点 $v$ 连向 $u$ 的颜色。$(u,v)$ 为红色的点记为 $r_1,r_2,\cdots,r_x$，蓝色记为 $b_1,b_2,\cdots,b_y$，则 $x+y=n-1$。
然后我们维护两个队列 $R,B$，$R$ 初始为 $r_1\sim r_x$，$B$ 初始为 $b_1\sim b_y$。每次拿出两个队列的队头询问，如果是红色就弹出 $B$ 的队头，否则弹出 $R$ 的队头，直到有一个队列为空。此时我们就找到了和空队列对应的颜色相反的那个颜色的生成树。共 $2n-2$ 次询问。
O
手玩一下，两个区间 $[L_i,R_i],[L_j,R_j]$ 如果满足：
- $L_i\not\equiv L_j \pmod 2$。
- $[L_i,R_i]$ 和 $[L_j,R_j]$ 有交。
那么这两个区间就不能同时满足条件，否则一定可以同时满足。
于是就变成了二分图最大独立集，网络流即可。