知识回顾：

• 巩固：二分，倍增，优化DP，莫队，分数规划，网络流，二分图，贪心，set/map，KMP

• 深入研究：分治（线段树分治），后缀数组，费用流

• 简单了解/没学明白：线性基，边分治，数位DP，博弈论

练题：

[SCOI2015]国旗计划

直接模拟复杂度 \(O(n^2)\)，显然会超时，于是考虑倍增。

定义 \(st_{i,j}\) 表示从 i 这条线段走 \(2^j\) 次所能到达的最远的线段编号。

转移显然，\(st_{i,j}=st_{st{i,j-1},j-1}\)。

为了方便，可以断环为链。

复杂度 \(O(n \log n)\)。

Yet Another Minimization Problem

神仙题。

第一眼看上去就是 DP。

定义 \(f_{i,j}\) 表示当前点 i，分 j 段的最小费用。

\(f_{i,j}= min(f_{i,j},f_{k,j-1}+val_{k+1,i})\)

然后发现复杂度 \(O(n^2k)\)，直接 T 飞，需要优化。

我们发现 j 那一维可以滚掉，也就是只考虑第一维，然后做 j 次就行了，下面称 \(f_{i,j}\) 为 \(f_i\)。

对于 \(val_{i,j}\)，我们发现当 j 固定时，i 越小，值越大 (废话。

接下来最关键的一步就是证明转移的最优决策点是单调不降的。

我们考虑反证法。

定义 u 为当前点 i 的最优决策点，v 为 i+1 的最优决策点。

那么 \(f_u+val(u+1,i) \le f_v+val(v+1,i)\)

若 v < u，则对于 i+1 应当满足：\(f_v+val(v+1,i+1) \le f_u+val(u+1,i+1)\)

即：\(f_v+val(v+1,i)+ \Delta v \le f_u+val(u+1,i)+ \Delta u\)

根据之前发现的单调性，显然可以得出 \(\Delta v \ge \Delta u\)，即 \(\Delta v-\Delta u \ge 0\)。

所以移项可得 \(f_u+val(u+1,i) \ge f_v+val(v+1,i)+(\Delta v-\Delta u)\)，与前者矛盾，证毕。

接下来就可以用分治来优化了。

定义 \(cal(l,r,L,R)\) 为当前处理的区间 \([l,r]\) 和可能的最优决策点所在区间 \([L,R]\)。

对于一个这样的函数，我们可以暴力找到 \(mid=\left\lfloor l+r \right\rfloor\) 的最优决策点 p, 然后递归下去。

那么问题来了，怎么快速求出 \(val(l,r)\) 呢？直接莫队就行了！

复杂度 \(O(kn \log n+n \sqrt n)\) 。

P4322 [JSOI2016]最佳团体

分数规划+树形背包。

可以根据推荐关系建出一颗树，然后如果选了一点，则该点到根上的所有点都必须选。

二分 mid，定义每个结点的权值，然后判断选 k+1 个节点的最大值是否大于 0。

设 \(f_{i,j}\) 为当前节点 i，在其子树内选了 j 个节点，最大点权和为多少。

转移方程为 \(f_{u,j}=max(f_{u,j},f_{u,j-t}+f_{v,t})\)。

初始化为 \(f_{u,0}=0\)，\(f_{u,1}=val_u\)，其余皆为 -inf。

然后我们发现这个 DP 的复杂度貌似是 \(O(n^3)\)。

但将各种限制条件加上后就变成了 \(O(n^2)\)。本人很菜，没法证明。

所以最终复杂度为 \(O(n^2 \log n)\)。

P3705 [SDOI2017]新生舞会

求比值，分数规划。

对于每一个男生向所有女生连一条容量为 1，费用为 \(a_{i,j}-c \cdot b_{i,j}\) 的边，原点 s 向所有男生连一条容量为 1，费用为 0 的边，所有女生向汇点 t 也连一条容量为 1，费用为 0 的边。

然后跑一边 KM 或者最大费用最小流就行了。

复杂度 \(O(玄学)\)。

A Museum Robbery

线段树分治。

我么发现添加物品容易，而删除物品难。

考虑把物品出现和删除的时间点表现在数轴上，那么一个物品的贡献就在这个区间内。

假设一共有 cnt 个查询操作，则我们建一棵大小为 cnt 的线段树。

然后对于每一个物品，将其区间拍在线段树上。

为了方便操作，可以在每个线段树结点上开一个 vector 存储被哪些物品覆盖。由于一个物品只会体现在 log 个结点上，所以 vector 的总空间为 \(O(q \log q)\)，不用担心 MLE。

最后遍历整棵线段树，对当前结点 vector 内的元素背包，然后再将 DP 数组下传给左右儿子。

最后每个叶子节点都对应一个询问，直接输出就行了。

复杂度 \(O(nk+q \log q)\)。

P5787 二分图 /【模板】线段树分治

模板题。

线段树分治还是该咋写咋写，二分图的判断需要注意一下。

常见的方法是黑白染色，但这里不行，要用拓展域并查集。

也就是把一个点 u 拆成 u 和 u+n 两个点，每次连边只连两个不同域内的点，如果发现 u 和 u+n 在一个集合里，则说明有奇环，不是二分图。

线段树分治返回的时候，并查集显然也要返回初始状态，所以不能进行路径压缩，为了使复杂度有保证，改用安秩合并。

撤回时可以借助栈。

复杂度 \(O(n \log n \log n)\)。

Painting Edges

可以说是模板题的进阶吧。

首先并查集要变成 k 个，对于每一种颜色都维护一下。

考虑一条边被染成某种颜色所处的时间段为 \([x,y]\)，那么会有两种情况。

1.染上去了，更新颜色。

2.没染上去，还是之前的颜色。

最后跑一边 dfs 就行了。

复杂度 \(O(m \log n \log q)\)

Painting Edges

还是线段树分治。

每次给一条边，如果没有就添加，如果存在就删除。

于是可以转化成一段存在的区间，可借助 map 记录是否存在。

剩下的就是板子了。

复杂度 \(O(n \log n \log n)\)。

[ABC281E] Least Elements

考场代码写得就是一坨屎，最后弃了。

我们可以定义一个 multiset 来存当前 m 个数。

添加元素：如果插入后在前 k 小，则减去第 k 个，加上这个数，否则不进行任何操作。

删除元素：如果要删除的元素在前 k 小，则减去这个数，加上第 k+1 个数，否则不进行任何操作。

复杂度 \(O(n \log n)\)。

[ABC281F] Xor Minimization

题目要求我们求这个式子：

可以从高到低考虑每一位。

如果当前这些数的第 k 位都相同，则可以忽略这一位。

否则的话可以将这些数分成两类，一类为 0，一类为 1，然后递归处理。

复杂度 \(O(n \log n)\)。

CF1442D Sum

背包+分治。

最朴素的做法是分组背包，对于每一个数组，考虑其每一个前缀，复杂度 \(O(nk^2)\)。

然后我们发现这些数组有着很好的性质，那就是不降。

于是就可以推出最佳的选法一定是全选若干个再加上一个选一些的，证明如下。

假设有两个数组都选了一部分数，其最后一个数分别为 a 和 b，且 a > b。

则显然在 a 后面继续选会更优。

接下来考虑分治。

对于当前区间 \([l,r]\) 计算出 mid，将 \([mid+1,r]\) 做一遍 01 背包，然后递归 \([l,mid]\)。

同理 \([mid+1,r]\) 也需要递归一遍。

如果 \(l==r\)，那么枚举一下数组 l 选的长度，更新一下就好了。

最后输出最大值。

复杂度 \(O(nk \log n)\)。

Compress Words

KMP简单题。

对于两个字符串a、b，我们要求出最大的 i 使得 \([lena-i,lena-1]\) 与 \([0,i-1]\) 相等。

然后可以把 b 接在 a 前面，中间隔上一个 \(#\)，跑一边 KMP 求出 border，然后去掉公共部分把 b 拼上就行了。

复杂度 \(O(n)\)。

【模板】后缀排序

很久以前就学过，但没太学懂，经过董老师的一番讲解，我豁（geng）然（jia）开（meng）朗（bi）。

定义 \(sa_i\) 为 s 的所有后缀中字典序第 i 小的编号。

\(rk_i\) 为后缀 i 的排名。

两者间关系为：\(rk[sa[i]]=sa[rk[i]]=i\)

可以用倍增求解。

任何长 \(2^k\) 的子串都可以表示成两个长为 \(2^{k-1}\) 的子串的拼接。

若知道所有长 \(2^{k-1}\) 的子串的排名，则长 \(2^k\) 的子串可以用一个二元组表示。

假如我们用 sort 进行排序，复杂度为 \(O(n \log n \log n)\)，不太 nice。

所以考虑用基数排序优化掉一个 log，即先对第二个排序，再对第一个排序。

P2408 不同子串个数

求出 height 数组，然后用总方案数减去所有 height 数组之和，即：

P2045 方格取数加强版

费用流题。

先拆点，分成入点和出点。

对于每一个点 \((i,j)\)，从入点向出点连一条容量为 1，费用为 \(c_{i,j}\) 的边，和一条容量为 k-1，费用为 0 的边。

然后 \((i,j)\) 和 \((i,j+1)\) 连一条容量为 k，费用为 0 的边，\((i,j)\) 和 \((i+1,j)\) 也连一条容量为 k，费用为 0 的边。

最后跑一边最大费用最大流就行了。

P4452 [国家集训队]航班安排

很麻烦的费用流。

我们可以给订单拆点，容量为 inf，费用为该订单的收益。

然后给起点 1 也拆一下，容量为 k，费用为 0。

如果起点到某个订单的起点的时间符合要求，则连一条容量为 inf，费用为 \(-f_{s, x[i].a}\)。

如果某个订单能按时回到起点 1，则连一条容量为 inf，费用为 \(-f_{x[i].b,t}\)

接着两两枚举订单，如果订单 i 能按时到达订单 j，则连一条容量为 inf，费用为 \(-f_{x[i].b, x[j].a}\)。

最后跑一边费用流。

模拟赛：

USACO

AK了铜组，银组差十秒AK（可恶。

一周过后终于出结果了，没晋级......

铜组：

[USACO22DEC] Cow College B

排序，对于每个值算一下就好了，比较简单。

复杂度 \(O(n \log n)\)。

[USACO22DEC] Feeding the Cows B

神奇的贪心。

首先我们可以把一块草的贡献理解为一个 \([i-k,i+k]\) 的区间，然后可以从左到右枚举每一头牛。

如果当前牛被区间覆盖，忽略。

否则的话以这头牛为左端点安排一个区间。

需要注意的是如果 \(i+k>n\)，那么可以先忽略这头牛，都处理完后从后往前找到第一个空位安排一下就行了（直观感受是对的，但我不会证明......

复杂度 \(O(n)\)。

P8899 [USACO22DEC] Reverse Engineering B

有意思的题。

判断有没有说谎其实就是看能否构造出可行解。

可以发现，if/else if/else 的组合的实际意义是每次根据某位的特性删去一部分字符串，而能够删除的条件是：当前拥有这个特性的所有字符串所返回的值相同。

接下来就好办了，我们采用贪心的策略。

如果当前位能够排除一波，那就执行一下。

为什么要立刻执行呢？因为如果一位能排除，那么不管怎么删除字符串都不会对其造成影响，反之的话就有可能使其成立。

所以这样的贪心是正确的。

复杂度 \((n^3)\)。

银组：

P8900 [USACO22DEC] Barn Tree S

第一眼看上去没什么思路。

考虑以 1 为根，计算其所有子树内干草的数量，然后可以判断出从节点 u 和它的父亲之间需要运多少草。假如需要从 u 向 \(fa_u\) 运 w 捆草，那么连一条 \((u,fa_u,w)\)。

可以发现这是一个 DAG，于是跑一边拓扑排序就行了。

复杂度 \(O(n)\)。

P8901 [USACO22DEC] Circular Barn S

考场上因为一些小细节没调出来！！！

定义 \(f_i\) 表示有 i 头牛，先手能否赢。

定义 \(g_i\) 表示有 i 头牛，如果双方都采取最优策略，需要多少次结束。

先用埃氏筛找出所有质数，然后对于递推求出 f 和 g。

如果存在 j，使得 \(j==i-prime\) 且 \(f_j==0\)，则 \(f_i=1\)，否则 \(f_i=0\)。

如果 \(f_i==0\)，则 \(g_i=\max\limits_{k=1}^{num}g_{i-prime_k}+1\)

否则 \(g_i=\min\limits_{k=1}^{num}g_{i-prime_k}+1\)

然后发现 T 飞了。

但是我们通过打表发现，如果 \(4 \ |\ i\)，则 \(f_i=0\)，否则 \(f_i=1\)。对于所有偶数，\(f_i=\frac{i}{2}\)。

于是只需要考虑 i 为奇数的情况。

因为所有奇数的 i 都有 \(f_i=1\)，而满足 \(f_j=0\) 的 j 必为 4 的倍数且 \(g_j\) 具有单调性，所以我们可以从大到小枚举质数，找到第一个满足 \(4 \ | \ i-prime_k\) 的 k，令 \(g_i=g_{i-prime_k}\)。

最后判断输赢的时候只需要对于每一个数找到 \(\frac{g_{val_i}}{2}\) 最小且最靠前的 i，并判断 \(f_{val_i}\) 即可。

复杂度很玄学，但是能过。

P8902 [USACO22DEC] Range Reconstruction S

别看题面很唬人，其实是个诈骗题。

我们知道相邻点的差的绝对值 r。如果 \(2^n\) 枚举显然不行。

假如我们有三个数，后两个的值不同且已经确定了（如果相同的话就可以合并成 1 个点），可以发现第一个数的值是唯一确定的。

于是我们就可以从后往前构造。

令 \(a_n=0\)，然后对于每一位的两种情况都分别试一下，取满足的一种就行了。

复杂度 \(O(n^2)\)。

A计划

太难了，打完部分分跑路了。

最终得分 20+20+40=80 rk15

贴一下官方题解。

T300672 A

对于每一个\(i\)，考虑给每条边一个定向，如果\(u\to v\)，那么另\(p_u=p_v+w\)，否则\(p_v=p_u+w\)。

那么如果一条路径上边的方向都是从\(u \to v\)或者\(v \to u\)，\(|p_u-p_v|=dis(u,v)\)，否则\(dis(u,v)\leq |p_u-p_v|\)。

考虑边分治，每次左边的所有边指向根节点，右边的所有边从根指向儿子即可。

或者点分治，每一层套一个二进制分组。二进制位为\(1\)的从下往上指，否则从上往下指。

ps：由于点分治不熟，不订正了。

T300674 B

显然，可以把两个数都填满前导零，答案也不会变。

最好的方法就是把\(x\)按位排序，\(y\)按位排序，依次相减。

也就是计算\(f_{i,j}\)表示\(l\)到\(r\)的所有数中，数位第\(i\)大的数大小为\(j\)的方案数。

考虑枚举\(j\)，数位dp。区间的数可以转化为前缀的数。

计算\(dp_{i,x,y}\)表示考虑了前\(i\)位，比\(j\)小的有\(x\)个，和\(j\)一样的有\(y\)个。

为了比较和\(r\)的大小，还要记录一位\(flag\)表示前\(i\)位是否和\(r\)一样。

T300680 C

最简单的一道题，但博弈论并不是我擅长的板块，所以考场弃了......

显然，如果初始时找不到\(k\times k\)的没有任何一个棋子的矩阵，那么先手必败。

如果能找到一个点，使得在这个点上放一枚棋子，导致找不到\(k\times k\)的没有任何一个棋子的矩阵，那么先手必胜。

除去这两种情况，初始局面至少会存在两个不相交的没有棋子的\(k\times k\)的矩阵。以及必败条件可以改成操作后使得找不到两个\(k\times k\)的矩阵，使得这两个矩阵全空且没有交。

那么考虑最后一步，肯定是只剩下了两个没有交的\(k\times k\)的矩阵。及一共有\(2\times k\times k\)个位置没有棋子，其他位置都有棋子。

根据初始空位的奇偶性，很容易得出最后一步是谁，从而得出谁必胜。

复杂度 \(O(n^2)\)。