A1. Dual (Easy Version)

https://codeforces.com/contest/1854/problem/A1

题意

给定一个长度为 \(n\) 的序列 \(a_1, a_2, \dots, a_n\)，你可以做以下操作：

• 选定两个下标 \(i, j(1 \leq i, j \leq n)\)，\(i, j\) 可以相同，然后 \(a_i \leftarrow a_{i} + a_j\)。

要求构造一种操作方案，使得 \(a_1 \leq a_2 \leq \dots \leq a_n\)，操作次数不得超过 \(\textbf{50}\) 次。

\(1 \leq n \leq 20, -20 \leq a_i \leq 20\)。

题解

其实 \(50\) 次的限制很松。

首先如果没有正数，那么直接做一遍后缀和即可，次数 \((n - 1=)19\)。

如果有正数，那么随便选一个正数，然后不断自己加自己，直到大于一个 \(20\) 的数（代码里选的是 \(45\)）。

然后让负数加上这个处理完的正数，做一遍前缀和即可，操作次数最多 \((6 + n - 1 + n - 1 = 2n + 4=)44\) 次。

https://codeforces.com/contest/1854/submission/216383173

A2. Dual (Hard Version)

https://codeforces.com/contest/1854/problem/A2

题意

给定一个长度为 \(n\) 的序列 \(a_1, a_2, \dots, a_n\)，你可以做以下操作：

• 选定两个下标 \(i, j(1 \leq i, j \leq n)\)，\(i, j\) 可以相同，然后 \(a_i \leftarrow a_{i} + a_j\)。

要求构造一种操作方案，使得 \(a_1 \leq a_2 \leq \dots \leq a_n\)，操作次数不得超过 \(\textbf{31}\) 次。

\(1 \leq n \leq 20, -20 \leq a_i \leq 20\)。

题解

\(31\) 次操作刚好卡满。

首先前缀/后缀和最少需要 \((n - 1=)19\) 次。

还剩下 \(31 - 19 = 12\) 次。

分三种情况讨论（赛时就是没想到，寄在这了）：

• 如果都是 \(\geq 0\) 的数，直接做前缀和；如果都是 \(\leq 0\) 的数，直接做后缀和。

• 如果正数的个数 \(\leq 7\)，那么先将绝对值最大的负数自加 \(5\) 次（至多为 \(-32\)），再加到这些正数上，就可保证所有的数都是非正数了；如果负数的个数 \(\leq 7\)，那么先将绝对值最大的正数自加 \(5\) 次（至少为 \(32\)），再加到这些负数上，就可保证所有的数都是非负数了。次数刚好是 \(7 + 5 + 19 = 31\) 次。

• 否则正数和负数的个数都至少为 \(8\)，所以正数和负数的个数最大值也只能取到 \(12\)，用绝对值最大的加即可。次数也是 \(12 + 19 = 31\) 次。

https://codeforces.com/contest/1854/submission/216386326

B. Earn or Unlock

https://codeforces.com/contest/1854/problem/B

题意

有一个长度为 \(n\) 的序列 \(a_1, a_2, \dots, a_n\)，一开始只有 \(a_1\) 是解锁的，其他的都是锁定的。你有一个动态的下标 \(x\)，初始为 \(1\)。

你要重复做以下操作：

• 如果 \(a_x\) 是锁定的，那么直接结束所有操作。

• 解锁接下来 \(a_x\) 个数或将得分加上 \(a_x\)。

• \(x \leftarrow x + 1\)。

求最大得分。

\(1 \leq n \leq 10^5, 0 \leq a_1, a_2, \dots, a_n \leq n\)。

题解

考虑暴力进行可行性 DP，设 \(f_{i, j}\) 表示现在考虑到 \(a_i\)，解锁了前 \(j\) 个数是否可以实现，转移方程 \(f_{i, j} = f_{i - 1, j} \text{ OR } f_{i - 1, j - a_i}\)。

初始状态 \(f_{0, 1} = 1\)，注意在转移完 \(f_i\) 的时候最后要将 \(f_{i, i}\) 赋值为 \(0\)！！！因为这样无法解锁 \(a_{i + 1}\)，赛时就寄在这了。

很显然可以使用 bitset 优化，如果 \(f_{i, j} = 1\) 那么得分至少为 \(a_{1} + a_{2} + \dots + a_{i} - j + 1\)，因为 \(f_{i, i + k}(k > 0)\) 会被后边的算到，所以不用在 \(i\) 考虑，只需要考虑 \(f_{i, i} = 1\) 的贡献即可。特别的，DP 到 \(n\) 的时候要考虑 \(f_{n, n \sim 2n}\)。

\(2n + 1\) 以上的就是无效的，因为这样一定可以减去几个数使得其 \(\leq 2n\)。

时间复杂度 \(O\left(\dfrac{n^2}{w}\right)\)。

https://codeforces.com/contest/1854/submission/216387677