怎么做题速度单调递减了。
464. THUPC2024Pre
省流：我是演员。
M
我过的题。
K
我过的题。
暴力打表就行了，我在本地打了三分钟就出答案了！很快。
J
我过的题。
考虑 \(v\) 什么时候对 \(len = k\) 没有贡献。那就是 \(v\) 把序列分成了若干区间 \([l,r]\)，\(ban\) 掉的区间就是 \([包含[0,v-1] 的最短长度,r-l+1]\)。
I
我最演的一个题。
想了 5min 想到了四毛子+哈夫曼树，算了一下感觉不对（？？？？wtf），就扔了。
又想了 10min 想到了 \(U = A \& B,V = A -U,W = B - U\) 的做法，算了一下感觉不对（？？？？wtf），就扔了。
把谭哥拉过来了 20min，谭哥看了看说我一开始的做法就是对的。这 20min 导致谭哥没冲出 f，我谢罪 /ll。
C
谭哥过的题。
队友过的题我是不是可以不用补。
E
谭哥过的题。
有点神秘的分讨题。
H
谭哥过的题。
史。
B
lcw 过的题。
有人怂恿 lcw 直接按重心贪心，wa 了一发，我不说是我。
lcw 开场就会了一个闵可夫斯基和的做法，暴力是两个 log 的，不过他不太敢写。
然后发现这玩意有个经典技巧，可以做到一个 log，就过了。
D
lcw 过的题。
看起来是大力区间 dp，然后预处理一下合法的转移，好像就过了。
F
谭哥差点过的题。 /ll。
似乎不难，好像要注意维护一下每个人的普通指令数，不然一直 activate 一个空人，会被卡飞。
G
人类显然在连通块里可以乱动，所以权值就是连通块中最大的人数个点。
显然一个状态可以用 \((时间，机器人位置，ls 人数，rs 人数)\) 表示，一共只有 \(O(T n^2)\) 个状态，每次转移容易随便做到 \(O(1)\)。
A
不知道为啥能想出连接 $p_i + 1 $ 和 \(p_{i+1}\)。然后就是简单的分类讨论，加上一种简单的构造。
L
没防住 dls。出题人汗流浃背了吧！
465. loj3965 「APIO2023」序列
他妈的，感觉我现场打的时候智商真低，这都没过。
二分答案，枚举区间内最前和最后的中位数。考虑一个区间合法的条件：中非空，左+中 >= 右，右+中 >= 左。如果把左和中看成 -1，第一个条件相当于区间和 <=0。如果把左看成 -1，第二个条件相当于区间和 >=0。简单线段树判断即可。这是两个 log 的。
交上去发现 T 了，发现内层线段树只做一次然后存下来就行， 就变成一个 log 的了。
466. loj3957 「联合省选 2023」人员调度
假设所有人都已经确定，考虑如何计算答案。大概是从底向上 dfs，每个节点维护一个 size 不超过子树大小的堆。每个节点的堆是把它上面的员工和所有儿子的堆拼起来，然后 pop 到 size 不超过子树大小为止。那么根节点的堆就是答案。
考虑只有加入，假设在 \(x\) 点加入一个人。动态维护根节点的堆。如果 \(x\) 到根的路径上没有满堆，那就直接加进去。否则找到最近的满堆，把最小的人踢掉即可。
套个线段树分治就过了。
他妈的 uoj hack 数据怎么素质这么低啊，估计是对着线段树的区间划分硬卡的。他妈的，我线段树划分区间加随机扰动都过不去，傻逼。
467. xsy5303 新居规划（zayinxxxx）
首先特判掉一整个环都塞满的情况，这样就变成了若干条链。然后长度 \(>2\) 的链至多只有一条，因为可以把其他链的中间塞到一起。然后长度 \(\geq 2\) 的链至多只有一条，因为 \(merge(2,>2)\) 总能成功。
可以直接模拟费用流求答案。
468. xsy5304 黑鸭的序列（dseq）
可以看作有 \(n+q\) 个点，然后把二操作踢了。
可以看作是求树上虚树路径，那只需要 \(\sum dep\) 和 \(lca\)。注意到 1 操作带来的 \(dep\) 变化次数至多只有 \(O(n \log \log V)\) 次，所以可以暴力修改。因为树比较特殊，可以被化为若干层，每层只需要取最大和最小的点计算 lca 即可。
469. xsy5305 黑鸭的字符串（dstr）
假装没有问号。在序列前加一个 0，序列后加一个 1，这样就有 \(n+1\) 个间隔。钦点只能删连续段中最后的 0 和最前的 1，每次删的时候把删的间隔记录一下，可以获得一个长为 \(n+1\) 的排列，所以一个合法的 \(T\) 对应唯一一个排列。观察这个排列的性质：对于串中的 \(0\)，\(p_i > p_{i+1}\)，对于串中的 \(1\)，\(p_{i} < p_{i+1}\)。我们声称满足这样的条件的 \(p\) 也能获得唯一一个串 \(T\)。具体地从前往后构造，删 \(p_i\) 的时候可以根据 \(p_l\) 和 \(p_r\) 的大小关系判断删的是 0 还是 1。
所以 0 是 \(<\)，1 是 \(>\)，? 是没有限制，问题就变成了 「LibreOJ NOI Round #2」不等关系 ，简单 cdq 一下就行了。
470. loj3958 「联合省选 2023」过河卒
搜索出所有的状态，一个状态是必胜态当且仅当它有必败态儿子，一个状态是必败态当且仅当它全是必胜态儿子，否则就是平局。类似拓扑排序，能被排序到的就是有胜负的，否则就是平局。
471. loj3959 「联合省选 2023」填数游戏
把 \(T_{i,0}\) 和 \(T_{i,1}\) 连边，搞出的连通块要么是树，要么是基环树，否则就寄了。
那么相当于每条边有四种情况：两端都不能加/只能加其中一端/两端都能加，第一个人要给每条边确定加哪边，第二个人要选一个代价最小的子集。
如果是基环树，就很简单：树上的边已经确定方向，环上的边就是 \(\min(a+c,b+c,{a+b+c \over 2})\)。
如果是树，先把所有边外向，找到值最小的儿子，把它到根的路径拉出来，把其中一个前缀反向。可以用线段树暴力维护。
472. loj3847 「NOI2022」众数
暴力题。我使用的是求出中位数和查询中位数出现次数。用了链表维护若干序列。
傻逼 uoj 机子太慢了，卡我常，加了 IO 才过。
473. loj3848 「NOI2022」移除石子
感觉完全会不了这种题啊 /ll。
首先操作 2 的长度只能是 3,4,5，并且不会有操作区间相等的操作 2。
大概可以设一个 \(dp\) 判定 \(K=0\) 是否合法：\(f_{i,j,k}\) 表示 \([1,i]\) 内所有操作都已经做完，\([i,i+1]\) 区间内一共有 \(k\) 个区间覆盖，其中从 \(i\) 开始的有 \(j\) 个。经过一些奇异的分析，可以搞出 \(j \leq k,j \in [0,2],k \in [0,3]\)，并且 \(j = 0,k = 3\) 这个状态完全没用。
然后有厉害的观察：
- 恰好为 $K $ 和至多为 \(K\) 的差距不大！
- \(a_i \leftarrow \min(a_i,4)\)，状态不变。
爆搜出所有状态转移即可。
474. xsy5006 逆序对 (inversion)
暴力数位 \(dp\) 即可。
475. xsy5009 括号串 (bracket)
考虑括号折线的最小值，若最小值 \(< -1\)，显然会一直用操作一抬高最小值。否则若最小值 $ = -1$，若只有一处最小值，即使用操作二，否则继续使用操作一。
476. xsy5010 构造字符串 (string)
考虑 SA 告诉了我们什么，写出 \(sa\) 数组，显然 \(c_{sa_i} \leq c_{sa_{i+1}}\)。当 \(rk_{sa_i + 1} > rk_{sa_{i+1} + 1}\) 时，有 \(c_{sa_i} < c_{sa_{i+1}}\)。马拉车告诉了我们一堆相等和不等关系，贪心构造即可。
477. loj3850 「NOI2022」挑战 NPC Ⅱ
大概记 \(match(u,v)\) 表示 \(G_u\) 和 \(H_v\) 能否匹配。发现合法的情况里，需要递归的儿子不会太多，暴力做即可。
478. loj3851 「NOI2022」冒泡排序
很厉害的题！题解先咕了。
479. loj3852 「NOI2022」二次整数规划问题
很厉害很厉害的题！题解先咕了。