ucup 做题记录
https://www.cnblogs.com/yhddd/p/18415768
The 3rd Universal Cup. Stage 1: St. Petersburg
A
bitset 维护 \(f_{i,j}=a_i<a_j\)。每 \(m\) 个点划一个段，统计跨过段的答案，维护一段的后缀 or。
C
从大往小加，线段树维护区间前缀后缀和最大连续 \(1\)。
D
在 \(0\) 先每个问一次，然后每隔 \(49,48,\dotsb ,1\) 问一次，问到状态翻转就挂到 \(12\) 小时后连续的问。
G
随机一个点开始找，当前找到 \(a_1,\dotsb,a_k\)，如果找不到新的出边，那么 \(a_k\) 连向 \(a_p\)，将路径改为 \(a_1\to\dotsb\to a_{p-1}\to a_p\to a_k\to a_{k-1}\dotsb\to a_{p+1}\)。据题解说是 \(O(n)\) 的，删掉一条路径之和图仍随机。
J
对 \(a_i\bmod B\) 做 bitset 背包，还原方案时如果既可以选也可以不选，就随一个。取 \(B=2.5\times 10^6\)。
N
\(\log n\) 个点维护每个点的编号，把 \(\log n\) 个点连成一条链。剩下 \(3\) 个点。取 \(a\) 为度数最大的点，\(b\) 标记所有的 \(n\) 个点，\(c\) 是唯一不连 \(a\) 的点，标记 \(b\) 和 \(\log n\) 个点的链头。
The 3rd Universal Cup. Stage 7: Warsaw
A
代价 \(2\to 1,6\to 3\)。dp 套 dp。内层 dp，设 \(dp_{i,j}\) 为前 \(i\) 个点，代价为 \(j\) 最长向后多远。只有 \(mn,mn+1,mn+2\) 的 dp 值有用。外层 dp 设 \(f_{i,x,y,z}\) 为前 \(i\) 个点，\(mn,mn+1,mn+2\) 的 dp 值分别在 \(x,y,z\)。当 mn 增加时增加答案。除了最开始只有 \(a+20\le b,b+20\le c\) 的三元组有用。
B
有不确定的端点先当成单点。按左端点排序，记录最多最少能放多少 \((-1,-1)\)。
E
将横纵坐标都小于等于 \(2\) 的障碍连边，等价于不存在左下边界到右上边界的路径。最小割。
K
设 \(f_u\) 为 \(u\) 为根的和，\(sum_u=\sum_{v\in subtree(u)} 2^{dep_v}\)，\(dep_u\) 为最大深度。换根 dp。
L
\(a_i\) 期望为 \(\frac{n}{2}\)。所以检查长度为 \([1,B]\) 和 \([\frac{n}{2}-B,\frac{n}{2}+B]\) 的区间。
The 3rd Universal Cup. Stage 8: Cangqian
C
构造二分图，\(1,4\) 为左，\(2,3\) 为右，\(1\to 2,4\to 3\)。然后奇数为左向之前的右连边，偶数为右向除了 \(2\times i-1\) 之前的左连边。
D
一个格子如果有两个方向的要求则为空。队列维护矛盾格子向后推。
E
注意到划分数不多，搜出来后贪心检查。
H
二分，时刻维护当前区间次大值位置。如果次大值和最大值在同一边则用一次，否则两次。每次将 \(len\) 变为 \(d\times len\) 用 \(1\) 次，\((1-d)\times len\) 用 \(2\) 次，取 \(d=0.6\)。
I
按位置之和排序，可以知道每张照片的先后顺序。\(m>n\) 所以必然有一只猪出现在相邻照片的同一位置。枚举这个位置，检查是否存在这样一条直线经过 \(m\) 个点。每只猪只可能出现在一条直线上。
J
找到最小生成树，只替换一条边，维护奇偶边权的路径最大值。
The 3rd Universal Cup. Stage 9: Xi'an
A
差分，哈希 \(a_i\) 和反过来的 \(k-a_i\)。线段树维护哈希值。二分答案。
E
出度最大的点 \(u\) 为支配点。设 \(u\) 连向 \(S\)，\(T\) 连向 \(u\)。如果存在 \(x\) 使得 \(dis(u,x)>2\)，那么 \(x\) 连向所有 \(S\) 和 \(u\)，\(d_x>d_u\)，矛盾。如果 \(T\) 为空，无解。否则 \(T\) 组成的子图的支配点 \(uu\) 也符合条件。如果 \(uu\) 不是指向 \(T\) 所有点，递归下去得到 \(uuu\)。否则指向 \(uu\) 且属于 \(S\) 的部分的支配点符合条件。
F
lucas 定理，等价于拆成 \(p\) 进制数下每一位的组合数之积。设 \(dp_{i,j}\) 为填到前 \(i\) 位，组合数之积为 \(j\)，\(cnt_k\) 为一位时的答案。\(dp_{i,j}=\sum_{kl\mod p=j} dp_{i,k}\times cnt_l\)。满足结合律，快速幂优化。\(p\) 为质数有原根，下标 \(i\) 改为 \(g^x\bmod=i\) 的 \(x\)，加法卷积。
H
从小到大加入，每次更新 \(n\) 个点。
I
质因数分解，枚举答案。可能贡献的 \((i,j,k)\) 满足 \(i,j\) 是相邻的 \(v\) 的倍数，双指针最近的 \(k\)。共 \(O(n\sqrt n)\) 组。把 \((k,v)\) 挂在 \(i\) 上，二位数点，做 \(O(1)\) 插入 \(O(\sqrt n)\) 查询的分治。
J
\(>3\) 一次后无解，分讨 \(n\) 和 \(t\)。
标签：个点,3rd,记录,连向,mn,times,ucup,dp From： https://www.cnblogs.com/yhddd/p/18415768