IOI2020国家集训队作业试题乱做 Part 3

难度标签：$\color{red}\texttt{[HARD]}$，$\color{blue}\texttt{[NORMAL]}$，$\color{green}\texttt{[EASY]}$。

CF573E Bear and Bowling

$\color{red}\texttt{[HARD]}$

首先有一个结论：首先选择 $\varnothing$，然后每次选择一个位置使得 $\Delta$ 最大，这样选出来的就是最优解。证明不会

那么考虑维护这个东西，直接每次找是 $\mathcal{O}(n^2)$ 的。发现修改一个位置从未选中到选中需要 $\mathcal{O}(n)$ 的时间，计算一个答案是 $\mathcal{O}(1)$，因此考虑分块。直接序列分块之后，位置 $i$ 的 $\Delta$ 大概是：$a_i\times k+b_i$，其中 $a_i$ 是定值，$k$ 是前面选择了多少个，$b_i$ 是后面选择了的数的 $a$ 的和。

实际上就是需要支持这些操作：

• 前缀 $b_i$ 加相同值。
• 后缀 $a_i+b_i$。
• 查询 $b_i$ 的全局最大值。
• 删除一个位置。

分块维护即可。块内维护一个上凸壳，整体加的时候不影响，零散块暴力重构。由于 $a_i$（斜率）不变所以可以最开始块内排序一次，之后就不用再排序了。然后就可以指针维护最优解位置了。

时间复杂度 $\mathcal{O}(n\sqrt{n})$。

CF576D Flights for Regular Customers

$\color{green}\texttt{[EASY]}$

$\text{sbt}$。但是俺是口胡的

考虑矩阵维护。把边按 $d$ 排序，然后依次加入，中间的移动用矩阵维护。这里的复杂度是 $\mathcal{O}(n^3m\log d))$，但是矩阵只有 $0/1$，所以可以 $\text{bitset}$ 优化。然后就可以得到最早在哪一条边加入之后可以到达 $n$。之后可以逐位确定，大概就是维护 $\log$ 个矩阵表示 $A^{2^i}$，然后拿 $1\times n$ 的矩阵去乘。

复杂度 $\mathcal{O}(\dfrac{n^3m\log d}{\omega})+n^2\log d)$。

CF576E Painting Edges

$\color{blue}\texttt{[NORMAL]}$

线段树分治。

考虑如何解决操作不一定执行，发现可以在递归到线段树叶子节点的时候，判断当前操作是否会执行。令其控制时间区间为 $[l,r]$。如果执行，则在线段树区间 $[l+1,r]$ 加入新颜色的边（因为 $l$ 已经考虑过了）；如果不执行，则在线段树 $[l+1,r]$ 区间加入当前颜色的边，表示延续当前边。

时间复杂度 $\mathcal{O}(n\log^2q)$。

CF578E Walking!

$\color{blue}\texttt{[NORMAL]}$

显然是选出一些 $\text{L,R}$ 交替，下标递增的子序列。每次加入一个位置的时候，考虑前面一些结尾，如果能加入则加入，否则新开一个子序列，显然最优。

考虑输出方案。观察到子序列只有开头结尾的字符有意义，所以可以分为 $\text{LR,RL,LL,RR}$ 四种。$\text{LR}$ 和 $\text{RL}$ 可以通过 $\text{LL}$ 或 $\text{RR}$ 拼接。如果没有 $\text{LL}$ 或者 $\text{RR}$，可以选择一个 $\text{LR}$ 和 $\text{RL}$，将末尾字符进行调整，转化为 $\text{LL}$ 和 $\text{RR}$，从而解决问题。

如果在这种情况下仍然无法构造，则无解，而题目已经申明保证有解。

时间复杂度 $\mathcal{O}(n)$。

CF578F Mirror Box

$\color{red}\texttt{[HARD]}$

又是不看题解压根不会做的题

考虑将网格变为 $(n+1)\times (m+1)$ 的图，按镜子连边。发现镜子只会在横纵坐标奇偶性相等的点之间连边，所以给点染色。就像这样：

考虑题目中需要的两个条件：

每一个格子都能被照射到。

则等价于图中没有环——有环则环内部必定无法被照射到。

从一个格子射入的光从相邻的格子射出。

这个俺就不会了。画画图发现，这等价于将相邻两个边界用一个封闭的图形框起来，容易证明不会从自己回去，所以只会从相邻的位置射出。

我们发现，这等价于同色点之间的一棵生成树！为什么？首先无环满足树的条件，将相邻两个边界用封闭图形框起来，这在树上实际上就是在树的某两个叶子上连一条边，显然会得到一个环，这就将光线框住了。

所以，只需要先根据给出的镜子给图缩点，然后跑两遍 $\text{Matrix-Tree}$ 然后答案相加即可。

复杂度 $\mathcal{O}(nm\log(nm)+k^3)$。

CF585E Present for Vitalik the Philatelist

$\color{blue}\texttt{[NORMAL]}$

设 $f_n$ 为 $\gcd$ 为 $n$ 的集合个数，$s_n$ 为与 $n$ 互质的数字个数，$c_n$ 为 $n$ 的出现次数，$w=\max\{a_i\}$。

$$ s_n=\sum_{i=1}^w [\gcd(i,n)=1]c_i $$

$$ =\sum_{d|n}\mu(d)\sum_{d|i} c_i $$

令 $g_i=\sum_{i|x} c_x$，即 $i$ 的倍数的出现次数，可以狄利克雷前缀和做到 $\mathcal{O}(w\log\log w)$。那么：

$$ s_n=\sum_{d|n} \mu(d)g_d $$

狄利克雷前缀和即可。考虑求 $f_n$，设 $f'_n$ 表示 $\gcd$ 是 $n$ 的倍数的集合个数，那么：

$$ f_n=\sum_{n|x} f'_x $$

相同的方法可求，且显然 $f'_x=2^{g_x}-1$。所以整道题可以在 $\mathcal{O}(n+w\log\log w)$ 时间复杂度内解决。

本题的做法感觉自己没有怎么见过，即先进行反演（尤其是莫比乌斯反演），然后根据其中自带的狄利克雷前缀和来进行优化，从而降低复杂度。

CF585F Digits of Number Pi

$\color{blue}\texttt{[NORMAL]}$

考虑在每一个串第一次出现长度 $\left\lfloor\dfrac{d}{2}\right\rfloor$ 的子串的位置计算。由于是匹配问题，所以考虑建立 $\text{AC}$ 自动机。显然的是，所有 $\text{trie}$ 上深度 $>\left\lfloor\dfrac{d}{2}\right\rfloor$ 的节点都没有意义，反正在走到他们之前就会统计答案。所以只需要把所有长度为 $\left\lfloor\dfrac{d}{2}\right\rfloor$ 的子串拿出来建即可。

然后跑 $\text{dp}$，设 $\text{dp}_{i,j,0/1}$ 表示当前在 $i$ 节点，已经填了 $j$ 位，顶/不顶上界的方案数，遇到终止节点就跳过，枚举这一位填啥即可。

时间复杂度 $\mathcal{O}(10nd)$。

CF587D Duff in Mafia

$\color{green}\texttt{[EASY]}$

考虑什么时候无解。发现如果一个点，有三条同色的边连向他，那么必然无解。

那么判掉之后，同一个颜色在一个点上就只会有至多两条边了。由“两条边”不难想到 $\text{2-SAT}$，他们两条中至多一条被选中。同时，选中一条边，这条边两个端点的所有其他边都不能选择了，这个可以前后缀优化建图。

至于使得最大边权最小，考虑二分答案。如果一条边边权大于二分的值，说明这条边一定不能选。那么把"选择这条边"连向"不选这条边"，这样的话若选择了这条边，就会导致相反的节点在同一强连通分量中，因此就可以保证不选择这条边了。

时间复杂度 $\mathcal{O}(m\log v)$。

CF590E Birthday

$\color{blue}\texttt{[NORMAL]}$

根据 $\text{Dilworth}$ 定理，最长反链就是最小链覆盖。子串关系是偏序关系，所以可以先建偏序关系的 $\text{DAG}$，然后跑最小链覆盖。

但是由于串总长太大，所以不能每次暴力连边。可以在 $\text{AC}$ 自动机上找到 $\text{fail}$ 树上最近的点，然后传递闭包。最后跑一遍匈牙利即可。

复杂度 $\mathcal{O}(n^3+\sum |s_i|)$。

CF605E Intergalaxy Trips

$\color{blue}\texttt{[NORMAL]}$

设 $E_i$ 表示从 $i$ 走到 $n$ 的期望天数。由于人足够聪明，所以他一定会选择所以出边中期望步数最小的，有：

$$ E_u=1+\sum_{v}E_v\times p_{u,v}\times\prod_{E_x<E_v} (1-p_{u,x}) $$

意思是枚举出边 $v$，那么期望比 $E_v$ 更小的边都不应该出现。转移有问题，把右边的 $E_u$ 提出来是：

$$ E_u=1+E_u\prod_{E_x<E_u} (1-p_{u,x})+\sum_{v\ne u}E_v\times p_{u,v}\times\prod_{E_x<E_v} (1-p_{u,x}) $$

化简一下变成：

$$ E_u=\dfrac{1+\sum_{v\ne u}E_v\times p_{u,v}\times\prod_{E_x<E_v} (1-p_{u,x})}{1-\prod_{E_x<E_u} (1-p_{u,x})} $$

发现一个点不会走向比自己的 $E$ 更大的点，所以可以类似 $\text{dijkstra}$ 的方式来按照 $E$ 从小到大转移。时间复杂度 $\mathcal{O}(n^2)$。