Codeforces Round 889 (Div. 2)

T1

​ 思路：我们将 \(i \ne p_i\) 的数量记下来，再判断这个数的奇偶性，如果为偶，那么答案就为这个数 / 2，如果为奇，那么就是这个数 / 2 + 1。

T2

​ 思路：我们枚举 \(1 \sim n\) ，我们记录连续是 \(n\) 的因数的个数，如果不连续了就 \(break\) ，答案就是个数。还有一种做法是枚举 \(1 \sim 1000\) 然后按照上面的做法也能过。这题考场上用了好长时间才想出来。

T3

​ 思路：这道题目给的次数比较大，我们可以分类来进行处理，如果这里面的数字存在正整数，那么肯定可以把这些数字转化为正整数，那么我们只需要后面的数加前面的数就肯定能够符合条件，如果所有的数字都是负数，那我们只需要前面的数字加上后面的数字也肯定能够满足条件。还有一种情况全部都是0，那就直接输出0即可。这题考场上没时间看。

T4

​ 这题压根没看题目。思路：接下来是C2，首先31次很关键，为什么从50减少到31次？如果能把31次拆开来，就能大致理解出题人想要的做法。

其实刚做完C1的基础上，很快会把31拆成12+19，19是叠加的过程，而12就是留给我们把整个数组变为全正或全负的次数。

想了很久没个思路，后来用C1的程序跑了下题目给的第10个样例，突然找到一点突破口。

20
-15 -17 -13 8 14 -13 10 -4 11 -4 -16 -6 15 -4 -2 7 -9 5 -5 17

这个样例对我C1的操作来说，最大值17就能把所有负数变成大于等于0的数。所以我可以先记录绝对值最大的a[i]，然后对所有和这个值符号不同的都加上这个值，然后整个数组的符号就统一了。

但很明显这个思路不够，假如我有1个20，19个负值，那么这样做需要19+19=38次，还是不满足31次。

但是可以发现，如果与绝对值最大的a[i]符号不同的数小于等于12个，那么这样操作一定小于31次。

那大于12个怎么办？为方便讨论，这里先将绝对值最大默认为正数。

对大于12个的负数进行操作一定不行，因为想要减少叠加的19次，需要考虑更多情况，很明显无法通过简单的编程完成，于是我们只能对其余的正数进行操作。简单来说就是把数组变成20个负数，那么在大于12个的情况下，由于每个正数都至少得进行一次操作将其变为负数，那么也就是说，最不利的情况为，7个20，13个-1，此时除去每个正数所需的操作次数外，只剩余5次操作次数。

好巧不巧，这个5是不是很眼熟？1变成32需要5次！所以操作就是，-1通过5次操作变成-32，然后把7个20变为负数，最后19次叠加，总共5+7+19=31次。

所以思路就是，如果与绝对值最大值符号不同的数小于等于12个，每个操作一次把所有的变成符号相同的，然后叠加；如果大于12个，那么就取符号不同的数中的一个，将其扩大直至它成为绝对值最大的数后，将符号相同的变成与它符号相同的，然后叠加。

T5

​ 如果知道哪些前缀可以 恰好 被解锁，就可以用 \(\sum a_i - (i-1)\) 更新答案，因为需要花总和为 \(i-1\) 的卡解锁该前缀。从左往右递推。如果最长的可以被解锁的前缀 \(p\) 小于当前位置 \(i\) ，则 \(i\) 一定无法被解锁，退出。\(p\) 初始为 1。

​ 否则，对于所有解锁了 \(i\) 的方案，可以再解锁前 \(a_i\) 张卡。即若前缀 \(j \ge i\) 可以被恰好被解锁，则前缀 \(j+a_i\) 可以恰好被解锁。因为 \(p\ge i\)，所以令 \(p\gets p+a_i\) 。

​ 注意解锁的卡的数量可能大于 \(n\)，但显然不超过 \(2n\)。

​ 用 bitset 维护背包，时间复杂度 \(\Theta(\frac{n^2}{w})\)。

T6

​ 看了题解算法的大概是 概率期望dp，题解有点看不太懂。

T7

​ 题解还是看不懂