SEERC 2020 题解

啥都想不到

A - Archeologists

考虑一个 naive dp:\(f_i(j)\) 表示第 \(i\) 个位置,深度为 \(j\) 的最大收益。那么:

\[f_{i}(j) = \max\{f_{i-1}(j-1),f_{i-1}(j),f_{i-1}(j+1)\} + j\times p_i \]

然后这没法直接优化,不过这个 \(f_i\) 其实是凸的。

证明可以用一个转化:对位置 \(\{1, 2, \cdots, n-1, n\}\) 这些位置做线段覆盖,线段左右端点必须为 \(1\sim n\) 的整点。一个点被覆盖的次数为 \(c_i\),则答案为 \(\sum_{i}c_ip_i\)。附加条件:每个点被作为起点或重点至多一次。

用流表示选中一段区间——这样使入边和出边容量为一即可控制这个附加条件。首先设 \(s_i=\sum_{j\le i} p_i\),考虑对于点 \(0, 1, 2, \cdots, n-1, n\),源汇点分别为 \(S,T\),如下建图:

  • \(i\to i+1\),容量无限,费用为 \(0\)。
  • \(S\to i\),容量为一,费用为 \(-s_i\)。
  • \(T\to i\),容量为一,费用为 \(s_i\)。

答案即为最大费用最大流,其凸性还是比较显然的,那么 \(f_i\) 也是凸函数了。

如何维护 \(f_i\)​?我们可以开一颗平衡树,支持全局查最值(的位置),等差数列加。具体实现还有不少细节,我也没写过。\(O(n\log n)\)​ 已经可以通过了。

有趣的是,我们建好了费用流模型,使用模拟费用流的思想就能解决问题。考虑从右往左,用一个堆维护一个后缀的出边。然后用当前位置的入边去匹配一条最大的。由于不是每条边都需要选择,我们不妨每个位置入堆两次,最后总共的贡献中会有一次抵消(一个方案中 \(a\to b\) 和 \(b\to c\) 的值相当于 \(a\to c\))。这个做法好写很多。

B - Reverse Game

只要想到逆序对这个关键切入点就胜利了。记逆序对数为 \(I\)。

考虑这些操作这么设置的本质,就是可以使 \(I\) 一次减少 \(1\) 或者 \(2\)(保证逆序对 \(\ge 0\))。如果要使 \(I\) 减一那么必然存在一个 \(\texttt{10}\) 子串,翻转即可减一。如果 \(I>1\) 时需要减二,那也必然存在剩下三种子串之一。具体可以用反证法简单证明。

\(O(n)\) 计算 \(I\),对于 \(I\in\{1, 2\}\) 是先手必胜,\(I=3\) 则后手必胜。根据必胜-必败态定理易得 \(I\in \{4,5\}\) 是先手胜,\(I=6\) 后手……因此 \(I\bmod 3 = 0\) 时输出 Bob,否则输出 Alice

D - Disk Sort

考虑一个思考方向:每次花费 \(\le 6\) 次操作排好一个颜色。

根据直觉,每次我们一定是选择“移除目标颜色圆盘上的圆盘数尽可能少”的颜色,这样我们清理上方比较方便。

对与一种颜色,设 \([a, b, c]\) 表示其三个位置的深度(由上到下深度依次为 \(0,1,2\))。注意到一个显然的结论,就是一定存在一个 \([a, b, c]\) 使得 \(a+b+c\le 3\)。而除 \([1,1,1]\) 外的所有这样的情况都可以通过不超过 \(6\) 次操作,得到一个新的排好序的柱子。

以上一共 \(5\) 中情况,都可以手模验证。然而我们发现除去 \([1,1,1]\) 并没有影响,因为总会存在一个颜色是满足至少一个圆盘在顶上。

如果每次都找一个这样的颜色,将其排序,一共需要 \(6(n-1)\) 次(最后一种颜色会在最后天然排好)。最后花费 \(3\) 次将最后一个柱子清空。

复杂度 \(O(n^2)\),实现非常有技巧性。如果不想写长,可以考虑 \([a, b, c]\) 应满足 \(a \le 0, b\le 1\)。这样可以快速方便地找到可操作的颜色。我们目标明确地将目标圆盘都移到空柱子上,然后记录一下除空柱子外的空位就能简单地移除上方的障碍了。这样还不用考虑两个目标圆盘在同一个柱子上的情况。

参考实现(参考 hellomath):https://codeforces.com/gym/103102/submission/128966492

E - Divisible by 3

设 \(s(l,r)=\sum_{i=l}^r a_i\)。

考虑有 \(w(l,r) = w(l,k) + w(k+1,r) + (s_{k}-s_{l-1})\times (s_{r}-s_{k})\),这个东西很好拆,差分统计。

将左端点集合按前缀和以及前缀的 \(w\) 值按 \(\bmod 3\) 分类。然后就 \(O(n)\) 了。

F - Fence Job

考虑从合法的结果入手而不是操作,因为不同的操可能得到相同的结果。对于一个 \(h_i\),它可以通过操作“扩展”,从而对区间 \([l,r]\) 赋值,其中 \([l,r]\) 是极长的包含 \(i\) 的,满足最小值为 \(h_i\) 的区间。

动态规划,定义 \(f(i,j)\)​​​ 为只使用 \(h_{1\sim i}\)​​​,构造一个长度为 \(j\)​ 的结果序列的方案数。考虑从 \(f(i, \cdot)\)​ 转移到 \(f(i+1, \cdot)\)​。设 \([l,r]\)​​​ 为其极大拓展区间,那么写出转移:

\[\forall j\in [l,r],\qquad f(i+1,j) = \sum_{k=l-1}^j f(i,k) \]

通过显然的前缀和优化,这个式子已经可以 \(O(n^2)\) 算出了。实现时可以将第一维滚掉。

I - Modulo Permutations

网上题解不清不楚,还是万老爷靠谱。

切入点:对于任意一个数 \(x\),将它放在 \(1\) 或 \(2\) 的左侧或右侧都是合法的。而对于其他相邻昂贵的两数 \(a,b\),则 \(a>b\) 是必要(不充分)条件。

问题转化为,将 \(3\sim n\) 分为两组数 \(A,B\),使得 \(A,B\) 降序排序后满足条件。一下以“1-段”和“2-段”简称。由于是降序,我们不妨从 \(n\) 考虑到 \(3\)。显然有 naive 的 dp:\(f(x,i,j)\) 表示放置数字 \(x\sim n\),1-段末尾为 \(i\),2-段末尾为 \(j\) 的方案数。一个显然的优化是,\(i,j\) 中必有一个 \(x\)。于是令 \(f(x,i)\) 为 \(x\sim n\) 中,\(x\) 在 1-段末尾,\(i\) 在 2-段末尾。那么有转移:

\[\begin{aligned} f(x,i) &\to f(x-1,i) & (x,x-1)\text{合法}\\ &\to f(x-1, x) & (i,x-1) \text{合法} \end{aligned} \]

第一个转移比较平凡,\((x,x-1)\) 必然合法,相当于将数组复制了一遍。索性忽略它,直接略去第一维。而第二种转移总数是调和级数级别的,直接枚举 \(x-1\) 的倍数 \(+0,1,2\) 即可。复杂度 \(O(n\log n)\)。

L - Neo-Robin Hood

考虑如果我们已经暂时选定了两个集合 \(A, B\)​,代表我们的策略是“偷 \(A\)​ 买 \(B\)​”(显然要保证 \(|A|=|B|,A\cap B=\varnothing\)​)。这并不决定最终策略,于是调整。对于一个 \(x\in A\) 以及一个 \(y\in B\),如果“偷 \(x\) 买 \(y\)”比“偷 \(y\) 买 \(x\)” 更劣,那必然会交换他们。我们把条件写出来:\(m_x-p_y<m_y-p_x\)。由于这个不等式的两边都涉及到了 \(x,y\),不好那么好操作。而经过移项,可得 \(m_x+p_x<m_y+p_y\)。我们设 \(val_x=m_x+p_x\) 作为排序的指标。

我们按 \(val\)​​ 降序排序。考虑一个最终的策略 \(A, B\)​​,必有 \(\max(A)<\min(B)\)。显然一旦违反这个性质就可以做一些交换,小的编号换到 \(A\),大的换到 \(B\),可以发现新的策略必然优。

上面的性质促使我们将这个数组分为两段,\([1: i]\) 以及 \([i+1:n]\),分别代表 \(A,B\) 的选取范围。维护 \(A\) 使用大根堆,维护 \(B\) 使用小根堆。顺序完成 \(1\sim n\) 中所有的 \(i\) 即可。不过似乎不太好同时控制两边的选取个数,当如果限定选 \(k\) 个却简单了。

二分答案。注意到答案 \(k\) 有单调性。如果选 \(f\) 个可行,那 \(f-1\) 必然可行。总复杂度 \(O(n\log^2 n)\)。​

M - Mistake

考虑一个有趣的贪心:对于当前的 \(x\),将它加入到编号尽量小的当中去。具体的,对每个 \(i\in[1, n]\) 维护一个集合 \(S_i=\{1, 2, \cdots, k-1,k\}\),每次找到 \(S_x\) 中的最小值输出并删除。也就是说,输入的图白给了。

给个非常感性的说明,按照这样的策略,越小的编号,其已经构造完的答案“越完善”。如果出锅了实际上就是无解了。复杂度可以做到 \(O(nk+m)\)。

上一篇:贪心——cf708b


下一篇:「YbtOJ」递推算法