IOI 2021 国家集训队作业：试题泛做记录

截至 \(\text{2020.12.7}\)，已完成 \(81/150\)（看题解的算不清楚就不写了）

\(\rule[0pt]{14.3cm}{0.1em}\)

给定正整数可重集 \(a_{1\ldots n}\)，一次操作定义为：选择 \(i\in [1,n]\)，令 \(a_i\) 乘上一个任意的正整数，对于所有 \(k\in [0,n]\)，求出 \(k\) 次操作后可重集中至少有多少种不同的数。

\(n\leq 3\times 10^5,\ \ a_i\leq 10^6\)。

如果一次操作后 \(a_i\) 没有变成原始集合中的某个数，那么显然我们可以令它变为原始集合中所有数的公倍数 \(S\)，这样以后其他数也可以变成这个公倍数，这一定不劣于变成其他数。

于是我们有两种选择：

将某些数变成 \(S\)，那么我们自然是选择出现次数最少的若干个数，将它们统一变成 \(S\)；

不将任何数变成 \(S\)，那么我们只能对那些存在一个真倍数在原始集合中的数进行操作，选择它们中出现次数最少的若干个数变成它们的某个倍数。

所以我们通过两个数组记录所有出现过的数的出现次数和作为其他数真因子出现的数的出现次数（直接利用倍数枚举可以找出这些数），当 \(k\) 从 \(0\) 变到 \(n\) 时对每个数组维护一个指针表示当前的 \(k\) 足以将多少个数全部操作一遍。

时间复杂度为 \(O(A\log A+n)\)，其中 \(A\) 为值域大小。

\(\rule[0pt]{14.3cm}{0.1em}\)

有 \(n\) 个外星人，第 \(i\) 个外星人有权值 \(d_i\)，需要在 \([a_i,b_i]\) 中某个时间被消灭，一次功率为 \(P\) 的攻击只能消灭权值不超过 \(P\) 的外星人，问消灭所有外星人的最小功率总和。

共询问 \(T\) 组数据。

\(T,n\leq 300,\ \ a_i,b_i,d_i\leq 10^4,\ \ \sum n^3\leq 2.5\times 10^8\)。

查这题的时候顺便看到了正解用到了区间 DP，之后就不难想了。

设 \(dp(i,j)\) 表示消灭所有包含于 \([i,j]\) 的外星人的最小功率，我们找到这些外星人中权值最大的，枚举消灭它的时间 \(t\)，那么与此同时所有包含 \(t\) 的外星人也会被同时消灭，只要分别递归计算 \(dp(i,t-1)\) 和 \(dp(t+1,j)\) 即可。

注意区间要先离散化。

时间复杂度为 \(O(\sum n^3)\)。

\(\rule[0pt]{14.3cm}{0.1em}\)

给定 \(1,\ldots,n\) 的排列 \(\pi_{1\ldots n}\)，定义区间 \([l,r]\) 为连续段当且仅当排列中 \([l,r]\) 当中所有数排序后是公差为 \(1\) 的等差数列，现有 \(m\) 组询问，每次询问包含 \([l,r]\) 的最短连续段，可以证明这是唯一的。

\(n,m\leq 10^5\)。

是原题，直接搬运我以前写的题解了。

结论 1：设 \(ans(l,r)\) 表示询问区间 \([l,r]\) 的答案，则 \(ans(l,r)=\bigcup\limits_{i=l}^{r-1}ans(i,i+1)\)。

注意要特判 \(l=r\)。

这个结论不证了，因为可以脑补，而且证起来又有点麻烦。

所以我们求出 \(ans(i,i+1)\) 即可。

结论 2：设 \(L_i,R_i\) 分别表示以 \(i\) 为右/左端点的连续区间的最远左/右端点，则 \(ans(i,i+1)=[\max(j|j\leq i,L_j\ge i+1),\min(j|j\ge i+1,R_j\leq i)]\)。

道理和结论 1 差不多，也不证了。

于是问题又转化为求 \(L_i,R_i\)，求完以后上面那个东西二分一下 \(j\)，用 ST 表判定即可。

这个东西就要上线段树了，从左到右扫一遍 \(r\)，对于每一个 \(r\)，计算最左边的 \(l\)，即为 \(L_r\)，再反着做一遍，可以类似得到 \(R_l\)，这里只讲前面一个了。

考虑 \([l,r]\) 是连续区间，等价于 \((\max(p_i|i\in [l,r])-\min(p_i|i\in [l,r]))-(r-l)=0\)，当 \(r\) 固定时它是关于 \(l\) 的函数，设为 \(f(l)\)，用线段树维护 \(f(l)\)，考虑从 \(r\) 变成 \(r+1\) 时 \(f(l)\) 的变化。

考虑每一项的变化即可，\(r\) 对于每个 \(f(l)\) 来说都增加了 \(1\)，所以先将整个左边区间加 \(1\)。

\(\max\) 和 \(\min\) 类似，这里以 \(\max\) 为例。

用一个单调栈维护递减当前 \(p_i\)，则如果 \(p_{r+1}>p_{top}\)，那么要弹栈，并且 \(p_{top}\) 到 \(p_{top}\) 前一个元素 \(+1\) 这一段的最大值变成了 \(p_{r+1}\)，原本这一段的最大值是 \(p_{top}\)，所以相当于整体加上一个 \(p_{r+1}-p_{top}\)。

有很多对称的东西，类似处理即可。

时间复杂度 \(O(n\log n+m)\)。

\(\rule[0pt]{14.3cm}{0.1em}\)

给定若干环上区间，选择最少的区间覆盖整个环，或报告无解。

环长为 \(n\)，区间数为 \(k\)。

\(n,k\leq 10^6\)。

国旗计划弱化版。

首先复制为两倍破环为链，然后直接倍增，令 \(f(i,j)\) 表示从 \(i\) 开始覆盖 \(2^j\) 个区间最右能到多少，其中 \(f(i,0)\) 可以从左到右扫一遍，求左端点在 \([1,i]\) 的区间右端点的最大值。

然后从每个左端点倍增跳一下就可以了。

时间复杂度为 \(O((n+k)\log n)\)。

\(\rule[0pt]{14.3cm}{0.1em}\)

你要依次制作 \(n\) 个烤肉串，第 \(i\) 个会花费 \(q_i\) 的时间，每个单位时间你可以走神或不走神，但两次相邻走神必须间隔大于 \(t\) 单位时间，烤第 \(i\) 个串的时候至少有 \(x_i\) 个单位时间没有走神，问走神的方案数，对 \(10^9+7\) 取模。

\(n\leq 1000,\ \ k\leq 100,\ \ q_i\leq 250\)。

令 \(dp(i,j)\) 表示烤完前 \(i\) 个串，最后一次走神是第 \(i\) 串烤完前的倒数第 \(j\) 单位时间的方案数，特别地，\(dp(i,t)\) 表示最后 \(t\) 单位时间内都没有走神的方案数。

那么枚举一个 \(k\)，从 \(dp(i-1,k)\) 转移到 \(dp(i,j)\)，转移系数应当是对于第 \(i\) 个串中间的某个区间，走神次数不超过 \(q_i-x_i-1\)（或一些类似的东西）的方案数。

所以我们再来一次 DP，设 \(f(i,j,k)\) 表示长为 \(i\) 的区间，走神 \(j\) 次，最后一次走神是倒数第 \(k\) 单位时间（对于 \(k=t\) 同样特殊定义），如果 \(01\) 的点，每个点的出边缩成从它出发不断走到 \(in_i=1\) 的点，这条链末尾的那个点的出边。

在新图上状压 DP，每个点记录前驱以输出方案。

时间复杂度为 \(O(n+2^k)\)。

\(\rule[0pt]{14.3cm}{0.1em}\)

给定 \(n\) 个点的根结点为 \(1\) 的有根树，接下来发生 \(q\) 个操作，每个操作形如有一个叶结点被敌人占领或有一个叶结点不再被敌人占领。

你需要选择一些树边切断，使得根结点到所有被敌人占领的点不连通，最小化割去的边数，同时在最小化割去边数的情况下最小化未被敌人占领但与根结点不连通的叶结点数量。

每次操作后你需要输出最小割去边数和最小的未被敌人占领但与根结点不连通的叶结点数量。

\(n,q\leq 10^5\)。

前一问的答案是显然的，根结点的每个子树中最多割一条边，只要看这个子树里有没有被敌人占领的点即可。

而为了使后一问的答案尽可能小，对于根结点每个存在被敌人占领的点的子树，被切断的一定是所有被占领点的 \(\text{LCA}\) 到父亲的边。

一些点的 \(\text{LCA}\) 等于其中 DFS 序最大和最小点的 \(\text{LCA}\)，我们用一个 set 维护每个子树中所有点的 DFS 序，即可实现插入，删除，查询 \(\text{LCA}\)。

时间复杂度为 \(O((n+q)\log n)\)。

\(\rule[0pt]{14.3cm}{0.1em}\)

给定 \(n\) 个红点 \((a_i,b_i)\) 和 \(m\) 个蓝点 \((c_i,d_i)\)，求 \((a_i-c_j)\times (b_i-d_j)\ \ (a_i\ge c_j,\ b_i\ge d_j)\) 的最大值。

\(n,m\leq 5\times 10^5\)。

第一个单调性：如果一个红点在另一个红点左下方，那么可以扔掉。

同样的单调性：如果一个蓝点在另一个蓝点右上方，那么可以扔掉。

所以红点集合和蓝点集合分别可以化简成一个 \(y\) 坐标随 \(x\) 坐标增加而单调减的点集，设红点对应的此集合从左到右为 \(c_1,\ldots,c_s\)，蓝点对应的此集合从左到右为 \(d_1,\ldots,d_t\)。

第二个单调性：对于每个红点 \(i\)，设 \(f_i\) 表示使得 \((a_i-c_j)\times (b_j-d_j)\) 最小的 \(j\)，那么 \(f_i\) 随 \(i\) 单调不下降。

为证明这个结论，我们可以先证明一个基本结论：如果 \(x (a_y-c_u)\times (b_y-d_u)\)。

这是因为前者等价于 \(b_x(c_u-c_v)+a_x(d_u-d_v)