The 4th Universal Cup 做题记录 (1)

The 4th Universal Cup 做题记录

不是我写的有一些就懒得补了。

是我写的有一些就懒得写做法了。

剩下一些没写但大概直到做法的就随便提一句。

The 4th Universal Cup. Stage 0: Trial Contest

场上过了 ABDEFGHIJKLM。

C. Entrapment

爆搜，记状态 $(s 1, s 2)$ 表示 $s 1$ 无障碍且不可能有人， $s 2$ 无障碍且可能有人。

转移枚举问 $t \subseteq s 2$ ，可以答 $0/1$ ，再决定 ban $i$ ，再将 $s 2$ 改为新的可能的位置。

复杂度 $O (4^{n} n)$ 。

D. Geometry Rush

求出上下界， ~~bitset~~，合法的位置是一个区间。

E. Humans vs AI

令 $c_{i} = a_{i} - b_{i}$ ，如果 $c_{i}$ 为正有 $1$ 的系数，否则 $k$ 的系数，每次还可以取最大的正的 $c_{i}$ 改为 $- k$ 的系数。求前缀和，要求有多少个区间 $[l, r]$ 满足 $s_{r} - s_{l - 1} - (k + 1) max_{i = l}^{r} c_{i} \geq 0$ 。

建笛卡尔树，枚举短的一边，主席树维护另一边。

F. Mob Grinder

充要条件是要有 $n - 1$ 个 U 和 $m - 1$ 个 R。

从右往左，每列从下往上放 L。贴着 L 的边界放 U，多的接着从右往左放。贴着地面和之前列的上边界填 R，多的接着从右往左放。剩下的 D。

G. Most Scenic Cycle

注意到：同胚与 $K 4$ 不合法。

广义串并联图方法。

J. Popping Balloons

过程中，每个出现的不合法的串对答案贡献其出现的概率。

即对每个长度数有多少种合法的串。记 $f_{i, j, 0/1/2}$ ，分治 $f_{l, r, 0/1/2, j}$ 卷即可。

M. This Is Sparta!

按 $2^{k}$ 分层，每次一层中至少一半会掉下去。可以快速缩小到 $lo g V$ 个数。

又因为想让他不发生相对顺序变化，大概要 $1, x, x^{2}, \dots$ 。这部分大概只用做 $n nV$ 次。可以快速缩小到 $3$ 个数。

对于 $[a, b, c]$ 做 $k$ 次后是 $[a, b - ka, c - (k + 1) b + \frac{k ( k + 1 )}{2} a]$ 。可以二分 $k$ 。一旦发生相对大小变化，就相当于辗转相除。

The 4th Universal Cup. Stage 1: Grand Prix of Korolyov

场上过了 ABCDEFHIKL。

A 是观察到可以模 $3$ ，合法矩阵每行每列模 $3$ 余 $0$ 。后面不会。

B. Domain Compression

拆贡献到树上每对距离为 $d$ 的点，能有边即中间 $d - 1$ 个点都被删了。

点分治求距离为 $d$ 的点对数。

E. Coffee Shops

上界是 $n + \frac{n - 1}{2}$ 。

G. Cyclic Topsort

如果先删 $u$ 能到达 $v$ ，则 $u$ 偏序 $v$ 。这种关系形成一颗树。

每次找一个 $u$ 开始暴力拓扑排序。将点打乱随机找 $u$ 开始，跳过不优的点，则每个点只会经过 $lo g n$ 次。

J. Yet Another Constructive Problem

~~杨表是什么？~~

固定 $k$ ，调整 $m$ 。

直接对反链流，原始对偶，复杂度 $O (n^{2} lo g^{2} n)$ 。

优化：最短路用桶 $O (m + d i s)$ 。建图用 cdq 分治，还要偏移一下 $mi d$ 效果最好（注意点/边数最小做 spfa 不一定优，要避免大度数点）。只有 sqfa 带两个 $lo g$ 。

The 4th Universal Cup. Stage 2: Grand Prix of Paris

场上过了 ABDFGHIJKL。E 能过的假解爆 inf 了。

D 一个比较有道理的做法是，注意到这数位和和数值应该没什么关系，随机调整就 $O (k)$ 。

E. Euclid in Manhattan

只能在相邻行/列转移。

假解是选前 $B$ 个转移，可以 hack。

决策点不交？

二分栈？

J. JamBrains

合法位置有单调性。

如果存在 $u$ 行总数量大于 $r$ ，后面的就无法跨过，否则都可以。

The 4th Universal Cup. Stage 3: Polar Grand Prix

场上过了 BCDEFGIJK。

B. Christmas Tree

P9111。

求一个点指向多少个点，设 $f_{u, j, k}$ 表示 $u$ 子树内连向 $j$ 个，钦定 $u$ 最后一个指向 $k$ 个，提前补上 $a_{u} \times (k - j)$ 。

$f_{u, j 1, k} + f_{v, j 2, j 2} + a_{u} \times j 2 \to f_{u, j 1 + j 2, k}^{'}$

$f_{u, j 1, k} + f_{v, j 2, j 2 + k} \to f_{u, j 1, k}^{'}$

E. Maximum Segment Sum

求 $\leq k$ 的答案再差分。

考虑后缀和，每次可以 $s + 1 \to s^{'}$ 或 $max (s - 1, 0) \to s^{'}$ 。要求 $s \leq k$ 。

构造双射路径：第奇数次 $s = 0$ 时 $- 1$ 向下走，并反转之后的路径，直到第偶数次 $s = 0$ 时 $- 1$ 向上走。这样双射从 $(0, 0)$ 到 $(n, i)$ ，一步右上或右下，不经过 $k + 1$ 和 $- k - 2$ 的路径。

反射容斥，预处理上指标为 $n$ 的前缀和。单次复杂度 $O (\frac{n}{k})$ 。

F. This Time I Will Be Lucky

倒着做，维护正着 dp 的 dp 值对终点的贡献，太小就扔掉。

G. Far Away

判掉 $u, v$ 所在连通块 $\leq 20000$ 。随机选几百个点求最短路，有极大概率选到最短路上的点，检查 $min f_{i, u} + f_{i, v}$ 即可。

I. Two Permutations

从 $n \dots 1$ ，每次往前跳跟目前最大值换。

J. One Permutation

ZR3343

凸！套一个 P10181，根号分治段数和 wqs 的 $c$ 。

把求区间贡献和加 wqs 分段的 $c$ 放在一个树状数组 dp 中。

复杂度 $O (n n lo g n)$ 。

The 4th Universal Cup. Stage 4: Grand Prix of Chengdu

场上过了 ABCDGJKLM。全是签到。

H. Heuristic Knapsack

贪心会不了一点。

按 $w$ 排序后 A 取一个前缀，枚举是哪个前缀，然后 check。

把 $w_{i}$ 确定的按 $w_{i}$ 排序，剩下的按 $v_{i}$ 排序。枚举 $w_{i}$ 确定的一个要选前缀，前缀的未确定 $v_{i} = in f$ ，后缀的未确定 $v_{i} = 1$ ，然后把 $w_{i}$ 确定按 $v_{i}$ 排序。

从前往后 $w_{i}$ 未确定的 $w_{i}$ 。考虑要不要选未确定的 $w_{i}$ 中 $v_{i}$ 最大的，考虑该位置 $w_{i}$ 的上界。首先不能超过当前背包剩的空间，也不能超过枚举过不选的最小 $w_{i}$ ，如果此时 $w_{i} > 0$ ，那就选上以尽快填满剩下的背包空间。

K. K-Coverage

按照新位置与原位置的关系分讨，拆贡献。

M. Meeting for Meals

对 $a_{i}$ 和 $a_{j}$ 要求所有满足 $d i s (1, p) + max (d i s (a_{i}, p), d i s (a_{j}, p)) \leq T$ 最小的 $T - \frac{d i s ( a _{i} , p ) + d i s ( a _{j} , p )}{2}$ 。