啥都想不到
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)\)。