The 2nd Universal Cup 做题记录
le0n
·
·
个人记录
Stage 1
C. Halting Problem
搜索。
F. Chaleur
不需要脑子的做法。考虑求出任意一组合法划分，那么最大团要么是比划分出的团大 1，要么是一样大（去掉一个点加入一个点），最大独立集同理，这个都是好统计的。合法划分可以直接 2-sat，优化建图即可。
I. Kuririn MIRACLE
盲猜策略只有两种，要么跟着第二个圆，要么绕过第二个圆。第一种好算。第二种考虑分解速度为切向和向心，解出来切向速度 \frac{\sqrt{sin^2+3}+sin}{3}。辛普森积分可以算出绕到的位置，然后套个二分判断一下到终点连线和切向速度取到最大时的方向就行了。
Stage 2
I. Password
奇偶讨论。
K. Poor Students
贪心模拟费用流。维护两个右部点之间经过一个左部点的最短长度，可以开 k^2 个 set，然后跑一遍 spfa 求最短路。取反带来的代价相当于删 O(k^2) 个数再加 O(k^2) 个数，总复杂度 O(nk^2(k+\log n))。
M. Hardcore String Counting
典，但是卡常？？？？设 f_m 是 m 的答案，考虑 S 的所有 border，有一个长为 n 的转移（加一个前缀和）。直接常系数齐次线性递推，但是要卡常。
C. Many Many Cycles
先求一颗生成树。定义恰包含一条非树边的环为基本环。有个经典结论是所有环都能通过基本环异或得出。随机化，每次可以 O(n+m) 算出长度，可以随很多次，然后就过了。
Stage 3
L. Partially Free Meal
决策单调性。我写的是二分栈套主席树。
D. Discrete Fourier Transform
出题人好良心，不让你写 O(n\log n) fft。求完 F 数组然后旋转一下就转化成求 x 轴上离一个点集的最远点最近的整点，我写的是二分加线段求交。
I. Monster Generator
这题为啥过的人这么少？m=0 是一个可以做到 O(n\log n) 的经典问题。我们发现可以处理出所有 a,b 之间大小关系改变的位置，有 O(n^2) 个。两个相邻位置之间所有怪的顺序是固定的，因此相当于求 n 个一次函数在一段区间上的最大值之和，转化为凸包求最大截距。求完凸包之后一个点做贡献的位置是个区间，然后就做完了，复杂度 O(n^3 \log n)。