CF 2000 题目选做

2249C

法1

点边容斥

很好的一题。

点边容斥：考虑一个链或一个树的一部分，其连通块个数 = 点数 - 边数

所以我们只需要动态维护当前的每个前缀的点数 - 边数即可。

破环成链，然后我们直接滑动窗口，用线段树维护点数和边数的变化。

法2

纯分类讨论

我们把这个数列连成一个环，我们假设从顺时针方向走。首先，全局有两个特殊点，分别是1号和n号点，它们会把整个数轴区分为两部分，我们现在考虑 $n\to 1$ 这条路径上的点有多少能作为开头。

我们考虑 $n$ 后面第一段连续变化的区间：

显然有 $x+k$ 到 $x+1$ 是否可行等价， $x$ 自己单独。因此 $x+k$ 和 $x$ 本身这两个点是必须判定的。而这个 $y$ 我们不妨再手动判断一下。

接下来考虑我们遇到的是这种情况：

也就是有两段连续变化值，且两段连续变化值可以拼接在一起。那么只有 $x-1$ 后面那个位置是有机会可行的（因为它大抵是涵盖了 $x-b-1$ ，使其能够接上）。而再往后，连续变化段就会超过3个，必然不可行。

$1$ 和 $n$ 可以特判一下，然后两边各自判断4次，总共10次。

2247D2

显然 $k$ 一定是 $2^x$ 的形式。

证明：

考虑从高往低确定。

假设有一个数所在的位置和最终位置的是否有最高位1不同，那么这个最高位的1是必要的。

而只要有了最高位的1，那么所有最高位相同的数可以随意调换，不会超过。因此是充分的。

现在考虑带修，我们可以直接按每位是否有1来分治处理，每层拿一个ds来维护。因此每次修改只需要修改 $\log n$ 层。复杂度是 $O(q\log ^2n)$

为了简便，我们可以进行一个小小的条件转化。我们不必看最后的位置在哪。我们只需要看每层的左右区间的值域是否有交叉，因此我们数据结构方便插入删除查询最大最小值即可，直接set。

2245D2

我们发现题目的两个条件就是：

$a_i\ge -a_j$
$a_i<-a_j$

直接差分约束即可。

2238E

法1

先直接拆贡献。

假设T数量的前缀值为 $s$ ，全局有 $S$ 个T，且对方选的区间为 $[l,r]$ ，那么对方的答案为：

$s_r-s_{l-1}+(n-(r-l+1)-(S-(s_r-s_{l-1})))$

移项得：

$n+(2s_r-r)-(2s_{l-1}-(l-1))-S$

显然，对方面对一个局面，会选最小的 $2s_r-r$ 和最大的 $2s_{l-1}-(l-1)$

我们直接设 $f[i][s][k]$ 表示前 $i$ 个数，T的前缀和为 $s$ ，最大的 $2s_{l-1}+l$ 为 $k$ 下，对方 $(2s_r-r)-(2s_{l-1}-(l-1))$ 是多少。

转移显然。复杂度 $O(n^3)$

法2

令 $a_i=2s_i-i$ ，对 $a_i$ 进行差分，即我们要在 $S$ 最大下最小化最大子段和。

我们枚举最大字段和 $D$ ，现在尝试最小化 $S$

考虑反悔贪心，维护当前后缀最大值，如果超过 $D$ 了就把最前面可以改的T变成F。

时间复杂度 $O(n^2)$

2237E

我们考虑这样连边 $i\to a_i$

那样子我们就有很多个环。

我们可以断言只要一个 $b_i$ 知道了，那么这个环的所有元素都可以知道了。

证明：

考虑 $x\to y$ ，我们又有 $a_{b_i}=b_{a_i}$ ，等价代换可得： $b_y=a_{b_x}$ 。

若 $b_x$ 已知，则 $b_y$ 已知

现在考虑一个都不知道的环。从贪心的角度来说，我们肯定从编号最小的点开始确定。

手模一下可以发现，一个环上面的数字，必然也是令一个环（即两个环的定义域形成映射），因此两个环的大小要一样才可以。

2232D

首先若 $a_i\ge i$ ，显然不行。

考虑我们知道前 $i$ 块移过去的方案，并设步数为 $f_i$ 。

那么现在考虑我们要把第 $n$ 块移过去。由于有 $a_n$ 的限制，所以我们需要移走 $n-1-a_n$ 块。

我们可以直接移走最上面的 $n-1-a_n$ 块，然后把第 $n$ 块移过去。

接下来我们考虑如何移剩下 $n-1$ 块，先把这 $n-1-a_n$ 块移回去，然后再把这 $n-1$ 块统一移到第三格。

因此所需步数为：

$f_n=2f_{n-1-a_n}+f_{n-1}+1$

在极限情况下显然会炸。但我们考虑如果 $a_n=0$ 的话，那样子我们就没有必要移回去，直接统一移到第三格就行了。方案为：

$f_n=2f_{n-1}+1$

综上，我们在两种情况下即可完成。边界条件为 $f_1=0$

2227G

我们观察一下一个合法区间有什么性质：

性质一：长度必然是奇数
性质二：手玩可以发现，如果最后构造一个数，那么每个位置的贡献必然是 +-+-+-+-+ 。因此 $x$ 是唯一确定的。
性质三： $x>0$ 是必要的。

我们可以大胆猜测性质三也是充分的。

写了一下，发现过了，果然是充分的。

2222E

由于题目特地加粗 $a$ 非负，所以我们直接令 $a=0$ .

我们发现次数刚好是 $n+3$ ，因此我们可以猜测是用 $n$ 次来确定 $c$ ，3次来确定 $k$

我们尝试来先确定 $k$ 。现在显然只能先用 I 操作，而且显然我们考虑用一次 0000000 和 111111111 是最优的。

如果我们统计 $x_1,x_2$ ，发现不能完全区分（因为在 $c=111111$ 时会有截然不同的结果）。我们可以考虑直接在第一次插入后询问一次 $y=1111111$ ，最终我们可以得到如下结果：

我们发现只有当 $c=11111$ 时 | 和 & 是区分不了的，其他都可以确定 $k$ 了。而这两个情况由于 $c$ 全1，我们可以直接用一次 I 1 看看大小是否改变即可。

好，剩下的情况是确定 $c$ 了。这个东西逐位二分（用 Q 操作）确定即可，刚好 $n$ 次。

但如果是 ^ 我们可能有两个数，无法确定。所以我们可以直接在第二次插入前先二分就可以了。

2219B2

法1

我们考虑采用二分的思想。题目里我们可以询问的是子序列，我们可以先简化为可以询问的是子区间。

我们可以考虑随便沿一刀切开，然后分别询问两边的答案。

对于每个个正常数，如果它全部出现在一边，对答案的贡献是0。如果它在两边都出现，对两边的贡献都是1。因此正常数对两边贡献的差值永远无影响。

考虑我们求的特别数。假设它在其中一边出现3次，那么这边返回答案的奇偶性就会和正常数构成答案的奇偶性不同，因此我们就可以递归下去。

假设它在一边出现1次，另一边出现2次。那么我们就可以求出出现1次的位置了。因此我们就可以利用这种方法而二分其中一个1的位置。

当我们确定其中一个1之后，因为我们询问的可以是子序列，我们可以通过简单的调整来确定剩下两个1的位置。

可以通过easy version

法2

我们发现，刚刚我们其实已经发现了，我们可以直接通过一次询问来判断3个1是否同时在我们询问的区间里。

因此我们可以用这种方法直接二分出最后一个1的位置。

然后用子序列的操作，把这个1调整到最前，再二分剩余1的位置。

可以通过hard version。

2217E

我们考虑从后往前构造，维护 $q$ 的相对顺序。

首先 $j>i$ 的限制显然满足，然后我们抽出所有满足 $p_j>p_i$ 的 $j$ ，按照它们之前已经得到的 $q$ 的相对顺序来排（从大往小），当前这个数的排位就在第 $d_i$ 个之后即可。

2215B

若 $p\ge 3$ ，则 $n\ge b^2+b+1$ ，所以 $b\le \sqrt n$ 。直接暴力枚举即可
若 $p=2$ ，不妨记我们的数是 $\overline{kk}_b$ 。则 $n=k(b+1)$ ，对 $n$ 因式分解即可。

2201C

显然一个合法的括号序列满足其前缀和处处大于0。

我们考虑一次移动会对前缀和造成什么影响。对于这个前缀区间，会加入我们第 $k$ 个括号，并弹走这个前缀区间最后一个选中的括号。

显然，只有在第 $k$ 个括号为 ) 且这个前缀最后一个括号为 ( 才可能不合法。

我们可以设 $dp_i$ 代表 $i$ 作为最后一个选中的位置有多少种合法的方案。显然 $dp_j$ 可以转移给 $dp_i$ 当且仅当：

$s_j$ 是 (
或 $[j,i-1]$ 的前缀和均大于等于2

统计答案时，如果当前这个为左括号，那么答案即为 $2^{i-1}$ 。如果为右括号，则为 $dp_i$