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

The 4th Universal Cup 做题记录

做题记录 1：Stage 0 - Stage 9

Stage 12: Shanghai：BIKLM

Stage 14: Hong Kong：AF

Stage 15: China：EL

Stage 17: St. Petersburg：FGIM

Stage 18: Hongō：ABCHK

The 4th Universal Cup. Stage 12: Grand Prix of Shanghai

单挑。场上过了 ABDGHIJK。主要是调不出题，调试傻逼错误至少被硬控了 2h。

B 是找一棵生成树直接做，做完就剩根不对，再找一个奇环调。注意次数。

I 是 $f_i=\min f_j+(i-j-1)C+(a_i\oplus a_j)$，高低位分治。

K 直接 $O(n\sqrt{n\log n})$ 容易。注意单侧递归套单侧递归可以 $O(n{\log }^{3}n)$ 做 $m{n}_i\times m{x}_i$。

L. Yet another permutation problem

判定一个序列能否变为另一个：从左到右能分段就分段，不能分段再考虑交换最大最小值并重新分段。

即，对 $[l,r]$，之前的操作会导致：没变化、原来最小值的位置是来自外面的最大值、最大值位置是最小值。还有一些位置被 ban 掉不能分段：全部不能、全部能、最小值右边不能、最大值右边不能。

直接枚举分段的位置转移即可。

submission

M. Yet another 01 problem

一个节点的两个叶子儿子必须不同。一个确定的树的权值为 $2$ 的（有两个非叶子儿子的节点数）次方，也即 $2$ 的（有两个叶子儿子的节点数 $-1$ ）次方。

钦定一些相邻且不交的对数，一对如果不等权值为 $-1$，剩下的乱选即 $Cat(n-k-1)$。

设 $f_{i,j,0/1}$ 为前 $i$ 个选 $j$ 个最后一个选/不选。分治 ntt，$f(l,r,0/1,0/1)$.

The 4th Universal Cup. Stage 14: Grand Prix of Hong Kong

场上过了 ABGHIJK。F 写粪了，没调出来。C 分讨不出来。

A. Bipartite Graph Matching Problem

一开场就被过穿了是吧，怎么还有用匈牙利的时候。

扫 $r$，维护合法的解，每次找一条增广路，踢掉最左边的匹配点。复杂度 $O(nm)$。

哦，关于这个证明，二分图最大匹配等于矩阵 $A_{i,j}=e_{i,j}{x}_{i,j}$ 的 rank，随机赋一组值进去算。扫 $r$ 的时候做一个线性基状物，可以把一行的代表元换成靠后的，这也等价于调整一条增广路。

F. Find the Circuit

大概就是，第一次给无向图定向的时候，断环，每个点的出边要么是序列上之前的点，要么是下一个点。

第二次就是每次找到一个 $d_u=1$ 的位置，确定其下一个点，缩起来。

The 4th Universal Cup. Stage 15: Grand Prix of China

被带飞。场上过了 ABDEHIJKL。

E. Efficient Express

枚举 $\min \max (x_i,y_i)$，容斥为 $\ge$ 减 $>$，然后随便 dp 一下。

L. Logical Resonance

$n$ 个点 $k$ 个叶子且下标集合为 $S$，与，$n$ 的排列 $k$ 个上升且下标集合为 $S$ 双射。

由排列中转，反转之后取反即可。

似乎被 maojun 一个简单很多的做法过去了，应该是等价的。

The 4th Universal Cup. Stage 17: Grand Prix of St. Petersburg

开这场的时候我还在高速上，除了过了一个多项式原以外完全负贡献。场上过了 BFGHIKL。

F. Pluses and Minuses

对每个 $n$ 求 ${\sum }_{x\in S}\left(\genfrac{}{}{0ex}{}{2n-x-1}{n-x}\right)$。

转化为 $(x,1)$ 有一些起点，求所有 $(i,i)$ 的格路数。以第一次去到某个 $(p,p+1)$ 为分界，前面的是 $y=x$ 的 阶梯型格路，后面是 $\left(\genfrac{}{}{0ex}{}{2(n-p)-1}{n-p}\right)$ 一个卷积。

G. Traffic Lights

维护每个方向的 min。子树内容易。

在另一个线段树维护每个节点除重儿子以外的最大值，修改和查询的时候只有切换重链时重新查一次子树。

复杂度 $O(n{\log }^{2}n)$。

I. Wooden Checker

合并 $u\to v$，等价于要求 $v$ 为根且 $u$ 到 $u$ 的根的 $p{r}_u$ 都等于 $p{l}_v-1$。

直接维护 $rt\to p{r}_{rt}$ 的路径，每次一直 pop 直到 $u$，然后再拼上 $v\to p{r}_v$ 的路径。链表维护。

M. Construction Company

不能同时对两个流。

只考虑 $a$，要求关键任务流量必须为 $1$，否则为 $[0,1]$；剩下的任务同一时刻 $\le b$ 个，至少流掉 $num-b$ 个，所以 $i\to i+1$ 的流量上界 $a+b-num$。

求上下界最小流。

The 4th Universal Cup. Stage 18: Grand Prix of Hongō

场上过了 CEFGJKN。A 被 corner 干爆了，你告诉我这个是蓝？两个多项式都不会。

C 结构是一条直线加两个点，或左边那个 $6$ 个点。枚举一个点，极角排序以下，枚举第二个点形成直线，另外两个点就是直线反向延长两侧最近的两个。

K 总之打表之后发现一个退出的阈值，然后枚举 $O(n)$ 个终点算组合数即可。

A. Apparently Make UTPC

一坨。

here

B. Binary Tree Counting

here

H. Heyawake-like Problem

服了，怎么想出来的。