CF *2600 思维题 2
A CF1819D Misha and Apples
\(\text{Link}\)
- 之前做过的原题，现在还能想起来。
考虑我们最后取得一定是一段后缀，那么我们想让这个后缀尽可能的长。我们从左往右遍历 \(i\)，并维护指针 \(p\) 表示当前位置之前最晚一次删除最早是多少。假如我们从 \(i-1\) 转移到 \(i\)，设 \(mx\) 表示集合 \(i\) 中的数字在前面最晚一次出现在哪里，则有如下转移：
- 若 \(p<mx\)，则令 \(p=mx\)，否则的话不会更优。
- 然后不断向右挪动 \(p\)，直到在 \(p\) 处可以被清空停止。
然后我们要维护的就是到某个点 \(i\) 处能否被清除，设为 \(f_i\)。这个数组也是比较好求的，有如下转移：
- 若 \(p<mx\)，则必然会被清空，\(f_i=1\)。
- 否则若 \((p,i]\) 中有空集，那么我们一定可以通过调整空集使得在 \(i\) 处被清空，\(f_i=1\)。
- 否则 \(f_i=0\)。
注意在这里我们是先求出 \(f\)，然后再转移 \(p\)。复杂度显然是 \(O(n)\) 的，可以通过。
B CF79D Password
\(\text{Link}\)
- 常见套路汇总了一下，数据范围很小所以不用图匹配。
首先这个区间翻转操作显然不好做，考虑差分处理。设 \(b_i=a_i\oplus a_{i-1}\)，则翻转区间 \([l,r]\) 相当于翻转 \(b_l,b_{r+1}\)。而这两个下标的差正好要属于 \(a\) 数组。
然后根据给出的 \(x\) 我们可以构造出最后的差分数组，显然里面只有 \(O(k)\) 个 \(1\)，考虑状压 dp，设 \(dp_S\) 表示走到状态 \(S\) 的最少步数，则有转移：
其中 \(w(u,v)\) 表示将 \(u,v\) 同时取反的最少步数。这个东西也是好求的。我们可以将上述取反的过程看成在序列上跳 \(a_i\)，然后将跳跃的起点和终点取反。那么我们对于每一个 \(1\)，跑一边 SPFA 预处理出到别的点的最短路即可。
总复杂度 \(O(knl+k^22^k)\)，可以通过。
C CF1891E Brukhovich and Exams
\(\text{Link}\)
- 咋又是原题。
考虑我们贪心的去做。首先我们有一些位置改成 \(0\) 之后可以让答案 \(-2\)，显然这是最大的贡献，我们能删就删；然后我们发现此时数列中会剩下很多段 \(1\)，把中间的 \(1\) 删掉可以拿到长度 \(+1\) 的贡献，这个均摊下来是比 \(1\) 大的，所以我们也贪心的选这些段。
最后剩下的贡献最多只有 \(1\) 了，先将所有能判断出来的全部删掉。然后此时可能还会剩下两边的 \(1\)，显然从内往外删每次可以 \(-1\) 的贡献，逐个删除即可。复杂度 \(O(n\log V)\)。
D CF1886E I Wanna be the Team Leader
\(\text{Link}\)
- 怎么还是原题。
首先很显然的一个结论是将 \(a_i\) 从大到小排序，然后每一个项目对应的程序员一定是一个连续的区间。但是我们发现他不一定是按照 \(b_i\) 从大到小的顺序依次给区间，所以直接 dp 不太可行。
考虑到 \(m\) 较小，所以使用状压 dp。设 \(dp(i,S)\) 表示当前分配到 \(i\)，已经满足的项目集合为 \(S\) 是否可行。枚举下一个要分配的项目 \(p\)，然后找出最小的一个合法区间转移即可。复杂度 \(O(nm2^m)\)，显然爆炸。
发现这个 dp 很蠢，值域甚至只有 \(0/1\)。考虑交换值域定义域，设 \(f_S\) 表示当前已经分配的集合为 \(S\)，满足要求的最小的 \(i\) 是多少。枚举下一个要分配的项目，求出最小的一个区间转移即可。可以 \(O(nm)\) 预处理出这个部分的答案，复杂度就是 \(O(nm+m2^m)\)，可以通过。
E CF1799F Halve or Subtract
\(\text{Link}\)
- 平方的贪心做法还是比较显然的。后面学习了一下严谨的 wqs 二分方法，高妙。
先说平方做法。考虑从大到小排序 \(a_i\)，显然我们一定先操作大的数，并且一定先除再减。容易发现只有一段前缀会两个操作都做，然后会有一段区间只做一个操作，最后一个区间不做操作。
枚举一二区间的划分点，然后只有第二个区间的取值是不知道的。考虑贪心，先假设全部取除法，然后将减量小的换成减法即可。复杂度 \(O(n^2\log n)\)，可以通过。
当然这道题也有比较显然的 wqs 二分做法，因为我们要求恰使用 \(k_1\) 个一操作和 \(k_2\) 个二操作。所以设 \(f(x,y)\) 表示操作数为 \(x,y\) 的答案，我们要求的就是 \(f(k_1,k_2)\)。显然它在两维上都有凸性，所以我们可以 wqs 二分求解。
然后二维 wqs 有一篇著名的文章，可以规避掉普通二分取不到对应点的问题。复杂度 \(O(n\log^2 n)\)，也能通过。
F CF1696F Tree Recovery
\(\text{Link}\)
- 超高复杂度暴力草飞。
考虑到我们的信息是知道两点与其他所有点的距离是否相等 ，目标是构造一棵树。考虑找出所有直接相连的节点，这样就可以构造出整棵树。
考虑我们已经知道一条边 \((u,v)\)，此时枚举 \(i\)，如果判定 \(d(u,i)=d(u,v)\) 则说明 \((u,i)\) 相连。根据这个信息我们可以 \(O(n^2)\) 的构建出整棵树。问题是我们根本不知道这样的一条边。
但是 \(n=100\)，所以我们可以以超高复杂度通过此题。考虑枚举这条边，令其为 \((1,x)\)，然后暴力建树。建树后需要判断是否合法，先 \(O(n^2)\) 预处理两点距离然后暴力 \(O(n^3)\) 判断所有信息即可。这样总复杂度是 \(O(n^4)\) 的。
每组数据都这样做似乎复杂度会爆炸，但是跑不满所以可以通过。实际上这个东西在 CF 的 32 位机子上只跑了 100 ms。
G CF1725L Lemper Cooking Competition
\(\text{Link}\)
- 还是套路题，和 B 题比较像。
考虑到这个操作非常复杂，肯定不好做。一般这种时候我们就考虑差分或者前缀和，这道题里我们考虑前缀和。设 \(a_i\) 前缀和为 \(s_i\)，考虑这个操作的实质。
经过手玩分析可以发现，对位置 \(i\) 进行操作实际上相当于交换 \(s_{i-1},s_i\)。而最后要求 \(a_i\ge 0\)，也就要求 \(s_i\) 单调不减。现在我们的操作是交换相邻的两个数，最后要求序列有序。这是经典问题，答案就是序列逆序对个数，树状数组求即可。复杂度 \(O(n\log n)\)。
H CF1924D Balanced Subsequences
\(\text{Link}\)
- 经典套路题，但是没做出来。对格路计数的理解还不够。
考虑将括号序列放到网格上，令 ( 为向右上走，) 为向右下走。那么原题就相当于从 \((0,0)\) 走到 \((n+m,n-m)\)。然后我们要求匹配上的括号有 \(k\) 对，这个看上去很难做，实际上也不好直接做。
考虑我们贪心匹配括号的过程，维护一个左括号的栈，遇到一个右括号就弹出栈顶然后匹配。那么没有匹配到就意味着此时栈为空。此时我们的折线不会再向下走，而是会向右走，也就相当于将后面的折线整体往上抬一格。
然后就可以想到，右括号匹配失败的次数就是折线最低点的纵坐标，而它应该等于 \(k-m\)。然后考虑如何计数，我们无法直接求出最低点为某个值的折线个数，但是我们可以用反射容斥求出不穿过某个值的折线个数。于是我们做一次差分即可求出正确答案。
最后推出来的式子是 \(\binom{n+m}{k}-\binom{n+m}{k-1}\)，可以做到单次 \(O(1)\) 计算。
I CF1682E Unordered Swaps
\(\text{Link}\)
- 比较巧妙的拓扑排序的应用，可以解决一类固定元素偏序关系的重排问题。
首先最优策略肯定是将序列划分成若干个置换环，然后每个置换花费 \(k-1\) 的代价恢复。那么反之同理，我们给出的操作一定是在每个置换环中给出 \(k-1\) 个操作，那么这 \(k-1\) 个操作显然构成了一棵树。
考虑到我们需要将每一个点放回它原来的地方，这在树上体现为一条路径，那么这要求这条路径上的操作在答案序列中必须以相同顺序出现。考虑将它们顺次连边，然后跑出整张图的拓扑序，很显然可以满足条件。
每条边只会被考虑两次，时间复杂度 \(O(n)\)。
J CF1970A3 Balanced Unshuffle (Hard)
\(\text{Link}\)
- 手玩找规律题。
首先可以发现，序列前面会存在一段连续的 (，很显然他们可以将整个括号序列分成若干段，每一段的最外层是一个匹配。接下来将会有一些 )，显然可以发现第一个 ) 匹配第一个 (，第二个 ) 匹配第二个 ( ……
同时还会发现，这些右括号中间会有一些左括号，他们就是被包在匹配括号内部的括号。例如第一个 ) 和第二个 ) 之间的 ( 都会被包在第一组匹配括号中间，我们倒序枚举这些 ( 并将它们与对应的匹配括号连边。很显然这样将构成一个树形结构。最后我们按照正确的顺序遍历整棵树即可输出正确的括号序列。
每个括号最多经过 \(O(1)\) 次，时间复杂度 \(O(n)\)。实现时可以用链表删除。
K CF1720D2 Xor-Subsequence (hard version)
\(\text{Link}\)
- 怎么在最后又来一个原题。这个题的套路属于是新瓶装旧酒了。
考虑原题中的这个式子 \(a_i \oplus j< a_j\oplus i\) 实在太丑，我们肯定要将他进行一些处理，使得一边只有 \(i\)，另一边只有 \(j\)。但是这个东西是不可能完成的，因为不等式并没有良好的性质。
考虑另一个套路，比较两个二进制数的大小可以枚举哪一位不同，设前 \(k\) 位相同。此时我们对于前 \(k\) 位的关系就是一个等式，此时我们可以在两边同时异或 \(i\oplus j\)，可以得到：\(a_i\oplus i\) 和 \(a_j \oplus j\) 的前 \(k\) 位必须相同。而在第 \(k+1\) 位不同的同时我们也得满足 \(a_i\) 和 \(j\) 的第 \(k+1\) 位相同，如此即可保证 \(a_i\oplus j< a_j\oplus i\)。
那么枚举完 \(k\) 之后我们直接取前面的最大值即可。实现的时候可以直接在 01-Trie 上记录最大值，复杂度 \(O(n\log V)\)。
L CF1442D Sum
\(\text{Link}\)
- 最后一道原题了。缺一分治的经典模板题。
考虑先发现性质，有一个性质是最多只有一个数组只会选一部分，剩下的一定全选或全不选。证明是容易的，考虑调整法，如果有两个数组同时没有选满，设他们的下一个数分别是 \(a,b\)，并令 \(a<b\)。那么很显然我们可以将第一个数组的元素不断换成第二个数组后面的元素，这样一定不劣。直到第一个数组被删完或者第二个数组被填满，结论就对了。
然后我们枚举这个数组是哪一个，然后对剩下的部分做背包，复杂度是 \(O(n^2k)\)。考虑缺一分治，每次递归到一边的时候加入另一边的贡献，这样递归到一个元素的时候就可以将剩下的所有元素的贡献全部加进去。最后枚举一下当前数组选几个数即可。复杂度 \(T(n)=2T(\frac{n}{2})+O(nk)\)，根据主定理可得复杂度是 \(O(nk\log n)\)。
M CF1545C AquaMoon and Permutations
\(\text{Link}\)
- 很巧妙的构造题。
我们先考虑如何求出一个合法的拉丁方。考虑有没有一种情况是能够确定一行的，很显然的一个条件是，如果存在某一列，使得这一列上这一行的元素只在这一行出现了一次，那么这一行肯定是要选的。选完之后我们枚举一下剩下的行，将矛盾的行删掉。
由题目条件可以知道，如果我们确定了 \(x\) 行，则至少删去了 \(2x\) 行。此时剩下的每一列上有 \(n-x\) 种颜色，行数最多只有 \(2n-2x\)。所以行数是小于等于二倍的颜色数的。
这就告诉我们，如果当前剩下的部分没有满足上面条件的行，则说明每一列上每种元素都出现了两次。那么此时剩下的部分可以分成两个完整的拉丁方，我们钦定其中的一种情况，即任意选一列，然后将答案乘以二即可。
直接暴力做的话复杂度 \(O(n^3)\)，可以直接通过。