IOI2020国家集训队作业试题乱做 Part 5
难度标签：$\color{red}\texttt{[HARD]}$，$\color{blue}\texttt{[NORMAL]}$，$\color{green}\texttt{[EASY]}$。
CF627E Orchestra
$\color{blue}\texttt{[NORMAL]}$
首先有简单的 $\mathcal{O}(r^3)$ 做法：枚举上下边界然后 $\text{two-pointer}$。
发现完全没用到 $n$ 与 $r$ 同阶和 $k$ 很小的性质。考虑去掉一个枚举部分。发现在上边界固定，下边界变化很小的时候，中间的点实际上变化并不是很大，重新做一次有些浪费。
考虑一个点 $i$ 作为 $k$ 个点中最左边的一个的方案数，也就是有多少个右端点可以使得当前点 $i$ 是第 $k$ 个关键点，记为 $\text{sum}_i$。那么答案应该是 $\sum y_i\times \text{sum}_i$。因此只需要维护 $\text{sum}_i$ 即可。
考虑固定上边界，下边界从上到下进行枚举。不难发现，每遇到一个新点，实际上只有在该点前面的 $k-1$ 个点的 $\text{sum}_i$ 会发生变化，具体来说是平移一位。好像不太好维护，但是如果下边界从下往上枚举，加点就变成动态删点，找一个点的前驱。可以使用双向链表来维护。
时间复杂度 $\mathcal{O}(r^2+rnk)$。
CF704D Captain America
$\color{green}\texttt{[EASY]}$
考虑网络流。首先钦定所有的点都是代价较大的颜色，然后通过最大流找出最多可以改变多少点的颜色从而得到最小的代价和。
对于一个限制（以 $x$ 轴为例）$l$，上面的点的个数差 $\le d$。由于轴上点总数是一定的，所以实际上就是对某一种点的数量的，带有上下界的限制。把 $x$ 的限制向 $S$ 连边，$y$ 的限制向 $T$ 连边，流量是该轴上限制最紧的上下界，对于一个点 $(x,y)$，连接 $x\rightarrow y$，流量为 $1$，跑有源汇上下界最大流即可。
构造方案显然可以在残余网络上直接看。
CF639E Bear and Paradox
$\color{green}\texttt{[EASY]}$
考虑一组解是否可以变得更优。邻项交换，推推柿子就可以发现，最优解是按照 $\dfrac{p_i}{t_i}$ 降序排序的。
如果 $\dfrac{p_i}{t_i}$ 互不相同，则只有一种最优解。但是如果存在相同的 $\dfrac{p_i}{t_i}$，则他们之间的位置是可以相互交换的。这样的位置构成一些区间，这些区间中的点都可以任意互换位置，则某一个点放在这个区间的第一个时，单点权值最大；放在区间最后一个时，单点权值最小。
再将序列按照 $p_i$ 排序，然后二分一个 $c$，从前往后看前面是否存在一个点的权值的最大值 $>$ 当前位置权值的最小值即可。时间复杂度 $\mathcal{O}(n\log n)$。
CF639F Bear and Chemistry
$\color{blue}\texttt{[NORMAL]}$
$\text{solution 1:}$
考虑缩边双，缩出一个森林。加边的时候，把所有涉及的点抓出来建虚树森林，然后再跑缩边双即可。
时间复杂度 $\mathcal{O}(n\log n)$。
$\text{solution 2:}$
缩出森林之后，加入一条边有两种情况：
- 原本两个点在一棵树中。
- 不在一棵树中。
若在一棵树中，那么就相当于两点之间的点都不用管了，把他们的边权设为 $0$；如果不在，则把两棵树连起来。
用 $\text{LCT}$ 即可做到 $\mathcal{O}(n\log n)$。
CF666E Forensic Examination
$\color{blue}\texttt{[NORMAL]}$
子串出现次数，考虑 $\text{SAM}$。建立 $T$ 串的广义 $\text{SAM}$，拿 $S$ 在上面匹配，记录出 $S$ 每个前缀在 $\text{SAM}$ 上的位置，然后向上倍增到 $S$ 某个子串出现的位置即可。查询可以用线段树合并来维护 $\text{endpos}$ 的个数，注意这里的线段树合并需要新建节点。
CF671D Roads in Yusland
$\color{red}\texttt{[HARD]}$
首先有比较好想的，类似 [NOI2020] 命运 的做法，但是比较难写。
事实上这就是一个线性规划的模型，每条边上的覆盖次数 $\ge 1$，最小化权值和。考虑其对偶问题，推出来等价于：
每条边可以赋一个非负权值，每条给出的路劲上权值和 $\ge w$，求最大权值和。
线性规划相关结论可以证明。考虑这个问题，显然从深到浅，能选就选是最优的（因为不会对更上面的有影响），于是拿一个可并堆来维护当前点上所有的限制，取出最小的限制即这条边的最大权值。左偏树全局减法可以打 $\text{tag}$。
时间复杂度 $\mathcal{O}(n\log n)$。
CF643F Bears and Juice
$\color{red}\texttt{[HARD]}$
本题十分有意思，从一个很巧妙的角度给出了计数的新思路——从“信息”的角度来思考问题。
例如，如果需要对长度为 $n$ 的序列进行排序，每次可以比较两个下标 $i,j$ 的大小，需要多少次比较？
首先，对 $n$ 个数的排列共 $n!$ 种，每次比较两个下标，相当于确定了答案排列中这两个位置的相对关系。这就是我们能得到的“信息”，发现一个“信息”可以排除 $\dfrac{1}{2}$ 的排列（根据比较的两个位置的先后）。排序结束后，剩下的可行解只有 $1$ 个。
设需要 $k$ 次比较，那么有：$\dfrac{n!}{2^k}\le 1$，这样就可以根据“信息”来排除到只剩一种排列，那么需要 $k=\mathcal{O}(\log n!)=\mathcal{O}(n\log n)$ 次比较。这就可以证明基于比较的排序算法复杂度下界是 $\mathcal{O}(n\log n)$。
再用这个思路来看本题。不去考虑他的策略，整个事件结束之后，我们可以得到什么呢？
- 有哪些熊去睡觉了。
- 每只去睡觉了的熊是哪一天去睡觉的。
这就是我们可以得到的所有“信息”了。这样的“信息”最多有多少种呢？设 $t$ 天所能得到的“信息”量是 $\text{F}_t$，那么：
$$ \text{F}_t=\sum_{i=0}^{\min(p,n-1)}\binom{n}{i}\times t^i $$
也就是枚举多少熊去睡觉了，选择睡觉的熊，再确定每只睡了的熊是哪一天睡的。可以发现，$\text{F}_t$ 就是我们能区分的方案数上界。这应该很好理解，如果有更多种方案，但是我们能得到的不同“信息”只有这么多，自然无法区分出每一种。
因此，现在我们只需要判断是否能够达到这个上界即可。本题恰好可以，即 $t$ 天可以区分的方案数$_{\max}=\text{F}_t$！考虑构造一种策略来证明这一点。
设一共 $k$ 种方案，那么同样有 $k$ 种“信息”，令第 $i$ 种方案为：酒在第 $i$ 个桶中。若在某一个“信息”中，这天某些熊去睡觉了，那么就让他们在这天去喝第 $k$ 桶酒；若一头熊没有睡觉，就永远不喝第 $k$ 桶。由于每桶酒都是独立的，所以这样恰好可以把 $k$ 种“信息”对应到 $k$ 种方案，便顶到了上界。
然后就是算：
$$ \text{F}_t=\sum_{i=0}^{\min(p,n-1)}\binom{n}{i}\times t^i $$
的问题了。由于 $\bmod\ 2^{64}$ 所以没有逆元。但是 $p$ 很小，所以组合数可以暴力枚举分数线上下的数字，暴力取 $\gcd$，最后分母必定是 $1$，再对剩下的分子的乘积取模即可。复杂度 $\mathcal{O}(pq+p^3\log p)$。
CF643G Choosing Ads
$\color{blue}\texttt{[NORMAL]}$
考虑 $p>50$，也就是求严格众数的时候要怎么做。发现由于众数比任意其他数字出现次数的和还要大，所以可以设计这样一个东西来计算区间众数：每次选择区间内两个不相同的数字，将他们都删去，最后剩下的数字就是众数。应该很好理解。
换成 $p\%$，事实上，用差不多的方式，每次选取 $\left\lfloor\dfrac{100}{p}\right\rfloor+1$ 个互不相同的数字，全部删去，可以得到所有出现频率 $>p\%$ 的都会留下来，而 $p\ge 20$，所以至多保留 $k=5$ 种元素。线段树维护即可。
时间复杂度 $\mathcal{O}(nk^2\log n)$。
CF700E Cool Slogans
$\color{blue}\texttt{[NORMAL]}$
看到子串问题，想后缀自动机
建立后缀自动机，用线段树合并维护出 $\text{endpos}$ 集合（注意新建节点）。接着在 $\text{parent tree}$ 上进行 $\text{dp}$，设 $\text{dp}_x$ 表示以 $x$ 节点的某串结尾的序列最长是多少，可以说明，选择同一个节点中最长的串是最优的。因为越长就越可能包含更多的串，答案单调不降，所以如果最长的串不能匹配，答案就直接从父亲继承，反正一个节点贡献至多为 $1$。
那么可以从父亲转移过来，只需要记录上一个选中的节点在哪个祖先上，就可以在这个祖先的线段树上查询某个区间，以判断这个祖先是否在当前节点的最长串中出现至少两次。时间复杂度 $\mathcal{O}(n\log n)$。
CF603E Pastoral Oddities
$\color{red}\texttt{[HARD]}$
首先，原题的限制 $\iff$ 每一个联通块大小都为偶数。若存在一个联通块大小为奇数，则取出某边集之后，节点总度数和为奇数，但度数和显然为偶数，所以不合法。对于偶数大小联通块，可以构造一组解，主要是通过拉出一棵生成树，从底向上判断是否可以连接当前点与父亲。
则现在只需要维护联通块大小即可，可以 $\text{LCT}$，也可以离线下来分治。
分治的具体做法是，设第 $l$ 次加边到第 $r$ 次加边之后，最小的最大边权在 $[L,R]$ 中。首先将第 $l$ 次前，且边权 $\le L$ 的边加入并查集，考察 $\text{mid}$ 位置的答案，显然 $\text{mid}$ 左边的答案较大，右侧较小。可回退并查集维护即可。
复杂度 $\mathcal{O}(n\log^2 n)$。