The 3rd Universal Cup. Stage 15: Chengdu

本题解由无敌坦克手贝塔撰写。

A

By misaka_sama。

给一个长度为 $n$ 的由 '-' 和 '>' 构成的字符串 $s$，一开始你有一个空的串 $t$，每次你可以选出 $t$ 的一个长度为 $x \space (x\ge 5)$ 的子串，并将这个子串的内容覆盖成一个 '>' ，$x-4$个 '-' 和 $3$ 个 '>' 拼接而成的串。至多进行 $n$ 次操作，构造一种方案使得 $s$ 和 $t$ 相等。

将 $s$ 分成 '>' 和 '-' 构成的若干连续段，如果第一段或最后一段是 '-' 则无解，同时最后一段 '>' 的长度 $\le 2$ 也无解。

先把最后一段填成 '>' ，记最后一次填的位置为 $p$，然后依次从 $1$ 到 $p-1$ 遍历串 $s$，如果遇到一个 '>' 就覆盖 $[i,p]$。

B

By AbsMatt。

设 $dp_{i,j,k,0/1/2}$ 表示前 $i$ 个中花钱购买了 $j$ 个 a，$k$ 个 b，$s_i-j-k$ 个 c，上一个位置是 $0/1/2$ 的方案数，$s_i$ 表示前 $i$ 个字符中 ? 的个数。 不难写出 $O(n^3)$ 的 DP 转移。

最后给 dp 数组写一个三维前缀和（$O(n^3+q)$）或二维前缀和（$O(n^3+nq)$）预处理答案。

E

By misaka_sama , AbsMatt。

给一棵树，$q$ 次询问有多少连通块包含 $u$ 到 $v$ 路径的点。

考虑 $u$ 到 $v$ 路径上除 lca 之外的点，它们的贡献可以通过钦定它们为所在连通块中深度最小的点计算。设 $f_u$ 表示 $u$ 子树内以 $u$ 为根的连通块数量，有转移 $f_u \gets \prod (f_v+1)$。

然后是 lca 的贡献，其实就是包含 lca 的连通块数量，可以换根解决。

有可能出现 $f_u+1$ 取模后为 $0$ 的情况，所以不能求逆。设 $g_u$ 表示去掉 $u$ 的子树后包含 $u$ 的父亲的连通块数量，通过维护每个点儿子的 $f_v+1$ 的前缀积和后缀积做类似 $f$ 的转移就能求出 $g$ 。然后包含 $u$ 的连通块数量也能同理求出。

G

By misaka_sama，AbsMatt。

给一个序列 $a$，每次可以在 $a_i$ 和 $a_{i+1}$之间插入 $a_i \oplus a_j$，其中 $\oplus$ 可以是与，或，异或。问最多能有多少不同的数。

首先每两个相邻的数是独立的，然后不断在 $a_i$ 和 $a_{i+1}$ 之间插入$a_i \operatorname {xor} a_{i+1}$ 可以得到很多个相邻的 $a_i$ 和 $a_{i+1}$，这样一看就很优。

然后你可以不断用三种位运算组合出一堆数，这最多有 $O(1)$ 种，手算一下只有 $a \operatorname{or} b$， $a \operatorname{and} b$， $a \operatorname{xor} b$， $a \operatorname{xor} (a \operatorname{or} b)$，$a \operatorname{xor} (a \operatorname{and} b)$和 $0$。

I

By misaka_sama，AbsMatt。

维护一个序列，单点修改，查询有多少个 $k \le n$ 使得将原序列按照 $k$ 的长度分块后（最后一块的长度可能不足 $k$）每一块内元素单调不减。

设 $x$ 是满足 $[1,x]$ 单调不减的最大的 $x$，那么 $k$ 一定能整除 $x$。同理可以得到 $k$ 必须整除每一个连续段的长度（除最后一段）。那么答案就是除了最后一段的所有段的长度 $\gcd$ 的因数个数。

对于每个位置维护它所在的上升段的左右端点，修改分讨加线段树打标记就行。

J

By cyz2010。

签到题。按照题意模拟即可。

注意下一场比赛开始后当前比赛立刻结束。

K

By cyz2010。（赛后过的）

将 $a_i$ 向 $a_i$ 所有因数连边，形成一个 DAG，初始时每个 $a_i$ 上有一颗棋子。

每轮操作形如把一颗棋子移动一条路径，棋子不能重叠。

引理 1：存在一种最有操作使得每个棋子只会被操作一轮。

证明：如果操作了两轮，合并显然不劣。

引理 2：如果当前棋子所在点 $u$ 有没被占用的出点 $v$，留在原地一定不优。

证明：结合引理 1，留在原地只会挡住其他棋子。

由引理 1,2，整个过程可以看作 $a_i$ 到其因数 $d_i$ 的一个匹配。匹配的权值为 $val(a_i,d_i)$，即 $a_i \rarr d_i$ 的最多操作次数。

建模二分图。左部点 $a_i$ 向右部点 $a_i$ 的所有因数 $d$ 连边，边权为 $val(a_i,d)$。

由于因数个数是 $\sqrt{V}$ 级别，所以只取前 $300$ 小因数连边。

跑二分图完美最大权匹配，边数点数 $n^2$，费用流 $O((n^2)^3)$，实测跑飞快。

L

By AbsMatt。

签到中的签到。直接输出 $50$ 个 a，$45$ 个 b，$4$ 个 c，和 $1$ 个 inf。