by TheBigYellowDuck
CF1119D Frets On Fire
对于查询 \([l,r]\)，我们把 \(n\) 行的信息看成 \(n\) 条线段 \([s_i+l,s_i+r]\)，答案就是这些线段并的长度。
令 \(L=r-l\)，这些线段都可以平移成 \([s_i,s_i+L]\) 而答案不变。
把线段按照 \(s_i\) 排序，考虑覆盖每个线段起始位置之间的空隙。设 \(c_i=s_{i+1}-s_i\)，答案就是
\[L+\sum \min\{c_i,L\} \]多加一个 \(L\) 是因为 \([s_n,s_n+L]\) 也被盖上了。
这个式子就很好做了。对 \(c_i\) 排序后求前缀和，二分一下 \(\min\) 的作用位置即可。
时间复杂度 \(\mathcal{O}((n+q)\log n)\)。
CF1148D Dirty Deeds Done Dirt Cheap
发现 \(a_i<b_i\) 的数对和 \(a_i>b_i\) 的数对是独立的。第一类只能用 \(a_i<b_i\) 的数对构成，第二类只能用 \(a_i>b_i\) 的数对构成。
以第一类为例讨论，第二类同理。
\(a_i\) 之间没有限制，对相邻两项的限制是 \(b_i>a_i<b_{i+1}\)。那我们按照 \(b_i\) 从大到小排序即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
Submission #231744925 - Codeforces
CF1179B Tolik and His Uncle
神秘构造。
考虑只有一行的情况怎么做。可以 \(1\rightarrow m\rightarrow 2\rightarrow m-1\rightarrow \cdots\) 下去。容易说明每一步的向量不同。
考虑扩展到多行，可以 \((1,1)\rightarrow (n,m)\rightarrow (1,2)\rightarrow (n,m-1)\rightarrow \cdots\) 这样跳。上下两行配对，这样每一步的向量也是不同的。如果最后剩下一行，就按照一行的情况跳。
时间复杂度 \(\mathcal{O}(nm)\)。
Submission #231755500 - Codeforces
CF1190B Tokitsukaze, CSL and Stone Game
神秘博弈。
考虑先手必败的状态有哪些。
- 存在两个 \(0\)。
- 出现了 \(\geq 2\) 对数量相同的石子。此时无论破坏掉哪一对，另一对都会让先手失败。
- 数量为 \(x\) 的石子出现了 \(\ge 3\) 次。理由同上。
- 存在一对数量为 \(x\) 的石子，同时存在数量为 \(x-1\) 的石子。此时无论破坏还是不破坏都会失败。
- 石子的状态为 \(0,1,2,\cdots,n-1\)。无论取走哪一个都会出现一对相同的。
可以发现，除了最后一种情况，其他情况只会在初始状态出现。因为这些情况都要求出现一对数量相同的石子，如果某方取完出现了这些情况，他就直接输了，不会等到下一个人取。
对于最后一种情况，只需要统计初始总和和结束总和，判一下奇偶性即可。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1207D Number Of Permutations
无序不好求，正难则反，考虑容斥。
用总排列数减去 \(a_i\) 有序的排列数，减去 \(b_i\) 有序的排列数，再加上 \(a_i,b_i\) 都有序的排列数。
\(a_i\) 有序的排列数，相当于 \(a_i\) 不同的元素之间的顺序已经被定下来了，\(a_i\) 相同的元素内部可以随便排。\(b_i\) 有序的同理。
\(a_i,b_i\) 同时有序的排列数，将元素按照双关键字排序，如果不存在 \(a_i \le a_{i+1}\) 且 \(b_i \gt b_{i+1}\) 就存在这样的排列。\((a_i,b_i)\) 不完全相同的元素的顺序已经定了。完全相同的元素内部可以随便排。
所有情况都是一个阶乘的乘积。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1208C Magic Grid
\(4\mid n\) 这个条件很可疑。注意到 \(0\oplus 1\oplus 2\oplus 3=0\)，不妨向这个方向思考构造。
将矩形切成四块，在每一块中都顺次填下 \(0\sim \left(\dfrac{n^2}{4}-1\right)\)，这样就能满足每行每列的异或和都为 \(0\)。
不能填重复数字，考虑把所有数 \(\times 4\)，每一块内再分别 \(+0,+1,+2,+3\)。同时 \(\times 4\) 会把二进制下的末两位都空出来，再加上偏移量，显然是对的。
于是，我们就得到了一个类似这样的构造。
\[\begin{matrix} 0&4& 1&5 \\ 8&12& 9&13 \\ 2&6&3&7 \\ 10&14&11&15 \end{matrix}\]时间复杂度 \(\mathcal{O}(n^2)\)。
CF1280B Beingawesomeism
首先，如果矩阵中有 A，答案应该不超过 \(4\)。用一个 A 向上下分别扩展到头就可以得到一列完整的 A，再用这一列向左右推平就好。
现在考虑什么情况下可以减少扩展的次数。
- 有一行/列完整的贴边的
A。用这一条直接推平整个矩阵即可，答案为 \(1\)。 - 有一行/列完整的
A，但是不贴边。用这一条向两侧推平即可，答案为 \(2\)。 - 四个角上有
A。一次扩展到头得到一条完整的贴边A，再推平整个矩阵。答案为 \(2\)。 - 四条边上有
A。一次扩展到头得到一条完整的不贴边A，答案为 \(3\)。
依次检查就可以了。时间复杂度 \(\mathcal{O}(Tnm)\)。
CF1286A Garland
设 \(f(i,j,0/1)\) 表示前 \(i\) 个数中用掉了 \(j\) 个奇数，且第 \(i\) 个数为偶数/奇数时的答案。
转移平凡。根据 \(a_i\) 的奇偶性或者 \(0\) 来转移即可。
时间复杂度 \(\mathcal{O}(n^2)\)。
CF1286B Numbers on Tree
数据范围只到 \(n\leq 2000\)，可以考虑一些暴力点的做法。
最直观的想法就是对每个点 \(u\) 的子树排序，将 \(u\) 插入到合适的位置上，赋予其一个权值。
直接暴力做这件事情就好了。对于每个点，用一个桶将其子树里的点按照权值从小到大装起来。将儿子 \(v\) 的桶合并到 \(u\) 的桶时，将 \(u\) 插入到合理的位置。用 vector 实现。
从根出发 dfs 一遍就可以得到每个点根据点权从小到大的顺序。依次赋权 \(1 \sim n\) 即可。
时间复杂度 \(\mathcal{O}(n^2)\)。
CF1290B Irreducible Anagrams
抽象结论题。
一眼看过去没什么头绪。但是大概感觉，如果字符集相同，想构造不合法的串是很困难的。
考虑从一些可能构造不出来的 Corner Case 下手。
- \(l=r\)。显然构造不出来。
- \(S_l \neq S_r\)。可以将所有 \(S_r\) 排在最前面，\(S_l\) 排在最后面，那就切割不出来了。
- 存在 \(\geq 3\) 种不同字符。设 \(S_l=S_r=x\)，存在另外两种字符 \(y,z\) 且 \(y\) 的最后一次出现早于 \(z\)。我们把 \(z\) 全部排到开头，\(y\) 全部排到结尾即可。
其他情况无论怎么排都可以切割出来。
对每种字符做前缀和即可。时间复杂度 \(\mathcal{O}((n+m)|\Sigma|)\)。
CF1295D Same GCDs
\(x\in [0,m)\) 很好，但是 \(a+x\) 可能会超过 \(m\)。考虑辗转相除法。
\[\gcd(a+x,m)=\gcd((a+x)\bmod m,m) \]当 \(x\in [0,m)\) 时，也有 \((a+x)\bmod m\in [0,m)\)。从而只需要求
\[\sum_{x=0}^{m-1}[\gcd(a,m)=\gcd(x,m)] \]其中 \(d=\gcd(a,m)\) 为定值，则有
\[\sum_{x=0}^{m-1}[\gcd(x,m)=d]=\sum_{d\mid x}\left[\gcd\left(\dfrac{m}{d},\dfrac{x}{d}\right)=1\right] \]这就是一个 \(\varphi\left(\dfrac{m}{d}\right)\)。算一下就好了。
时间复杂度 \(\mathcal{O}(\sqrt{m})\)。
Submission #231955255 - Codeforces
CF1299B Aerodynamic
神秘题。
画一些特殊情况或者根据样例分析会发现中心对称的图形一定可以，否则一定不行。中心对称的图形一定由偶数个顶点组成。
现在只需要判断是否中心对称。注意到点集是逆时针给的，那么 \(i\) 号点和 \(i+\dfrac{n}{2}\) 号点就是对角顶点。判断一下每条对角线的交点是不是重合即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF1304D Shortest and Longest LIS
Solution 1:
考虑在 \(a_i\) 和 \(a_{i+1}\) 之间连边，小的指向大的。那么一组合法的拓扑序一定可以满足所有限制。
考虑让 LIS 更大，我们希望把更大的数往后放，更小的数往前放。也就是说，编号更小的点的拓扑序应该更小。用小根堆替换掉队列即可。
让 LIS 更小同理，要把更小的数往后放，用大根堆做拓扑排序即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
Solution 2:
聪明一点的做法。
对于 LIS 最小，考虑先从 \(n \sim 1\) 倒着排。对于每段连续的 <，把这一段数翻转过来。这样 LIS 就为最大连续 < 的长度，无论如何 LIS 都不能更小了。
对于 LIS 最大同理。L这样 LIS 就为连续 < 段的数量 \(+1\)，无论如何 LIS 都不能更大了。
时间复杂度 \(\mathcal{O}(n)\)。
CF1316C Primitive Primes
诈骗题。
考虑一个过程，每次代入 \(p\) 计算 \(f(p)\) 和 \(g(p)\)。如果 \(p \nmid f(p)\) 且 \(p \nmid g(p)\)，说明卷出来的多项式的常数项 \(c_0\) 不能被 \(p\) 整除。否则，我们扔掉 \(a_0\) 和 \(b_0\) 中能被 \(p\) 整除的项，多项式次数 \(-1\)，重复这个过程。
会发现这个东西等价于找到第一个 \(a_i\) 和 \(b_j\) 使得 \(p \nmid a_i\) 且 \(p \nmid b_j\)。
时间复杂度 \(\mathcal{O}(n)\)。
CF1326D1 & D2 Prefix-Suffix Palindrome
1500 & 1800。
贪心地考虑，可以删去最长的互为反串的前缀和后缀。对于剩下的串，只需要求出最长的回文前缀或回文后缀。可以 manacher，时间复杂度 \(\mathcal{O}(n)\)。
由于我们钦定了串的开头或结尾的位置，所以可以暴力哈希。时间复杂度 \(\mathcal{O}(n)\)。
CF1327E Count The Blocks
简单题。
考虑到一些 Corner Case，可以分几种情况讨论。
- \(i=n\)，此时答案就是 \(10\)。
- \(i=n-1\)，此时只有两个位置可以作为块的开头，剩下一个位置需要填一个不同的数字，从而答案为 \(2 \times 10 \times 9=180\)。
- 其他情况，先选出块开头的位置，块两端需要填不同的数字，其他位置随便填，这部分答案为 \(10 \times (n-i-1)\times9^2 \times 10^{n-i-2}\)。还要加上这个块放在开头和结尾的情况，这部分答案为 \(2\times10\times 9\times 10^{n-i-1}\)。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1329A Dreamoon Likes Coloring
考虑贪心，先把 \(p_i\) 定为 \(i\)，这样可以得到最紧凑的一种排列方式。如果这样都会让某些颜色染不上去，那就必然无解。
但是这么做可能会让最后剩下一些格子没染上。可以把颜色向后拉，恰好首尾相接。这样是最宽松的排列方式。如果这样开头又会露出来，那么依然无解。
时间复杂度 \(\mathcal{O}(n+m)\)。
CF1334D Minimum Euler Cycle
手玩几下会发现，最小字典序应该长成 \(1,2,1,3,\cdots,1,n,2,3,2,4,\cdots,2,n,3,\cdots\) 这样下去。
这个东西还算有规律。做个前缀和，二分一下 \(l,r\) 都在哪个段里，暴力输出即可。注意一下散块和整块之类的细节。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1338B Edge Weight Assignment
先随便找一个度数 \(>1\) 的点为根。
先考虑最小值。如果任意两个叶子之间的距离都是偶数，那么全填一种数就可以，最小值为 \(1\)。否则填 \(1,2,3\) 就可以构造出来了。
考虑最大值。如果一些叶子有着相同的父亲，那么这些边都需要填一样的数。这些边中只保留一条，剩下的所有边都可以任意填数。由于填的数无限大，所以一定有解。
时间复杂度 \(\mathcal{O}(n)\)。
CF1355C Count Triangles
数据范围允许枚举一维，但是枚举哪一条边都不太舒服。考虑枚举 \(x+y\) 的值，这样 \(z\) 能有一个确切的范围，再去统计合法的 \((x,y)\) 组数即可。
直接分类讨论太麻烦，可以无脑上差分统计答案。具体来说，可以枚举 \(x\)，那么合法的 \(x+y\) 的值就会出现在 \([x+B,x+C]\) 区间内。差分 + 前缀和统计一下，再去枚举 \(z \in [C,D]\) 查询有多少合法的 \(x+y\) 的值即可。
时间复杂度线性。
感觉这个做法还是很聪明的，避免了繁杂的分类讨论和推式子。
CF1381B Unmerge
神秘结论。
手玩几个样例会发现，如果一个数 \(p_i\) 比后面连续若干个都要更大，那么这些数必须来自同一个数组。否则会导致后面有些数跳到 \(p_i\) 前面去。
依据这个结论，可以将原数组划分为若干个连续块，每个块之间是独立的。只需要判断能不能用若干个块拼出长度为 \(n\) 的数组。这就是个背包。
时间复杂度 \(\mathcal{O}(n^2)\)，bitset 优化可以除一个 \(w\)。
Submission #239079453 - Codeforces
CF1394A Boboniu Chats with Du
把所有 \(a_i\) 分成 \(>m\) 和 \(\leq m\) 两类，分别从大到小排序，每一类都是先选大的。
考虑枚举选多少个 \(>m\) 的，贪心地考虑，肯定都放在最后选。那么选 \(i\) 个就要占掉 \((i-1) \times (d+1)+1\) 天，剩下的每天选一个 \(\leq m\) 的即可。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1396B Stoned Game
观察到如果存在 \(a_p > \sum_{i \neq p} a_i\)，那么先手一直选 \(a_p\) 就可以赢。
如果不存在，那么两人都会避免出现这样的局面，肯定会选得尽量平均。根据奇偶性直接判断即可。
时间复杂度 \(\mathcal{O}(n)\)。
CF1442A Extreme Subtraction
考虑在差分序列上操作。
一次前缀减就是在 \([2,n]\) 找一个位置 \(+1\)，一次后缀减就是在 \([2,n]\) 找一个位置 \(-1\)。前缀减和后缀减能进行的最大次数就是 \(a_1\) 和 \(a_n\)。
把差分数组上 \(>0\) 以及 \(<0\) 的和都算出来，比一下大小就好了。
时间复杂度 \(\mathcal{O}(n)\)。
CF1442B Identify the Operations
看着很神秘，先尝试能不能推出什么结论。
假设我们当前要加入序列的数为 \(a_i\)，那么就必然要删去 \(a_{i-1}\) 或 \(a_{i+1}\)。如果这两个数都不能删那就寄了，如果都能删那么答案要 \(\times 2\)。
怎么判断一个数能不能被删？以 \(a_{i-1}\) 为例，发现当且仅当 \(a_{i-1}\) 不在 \(b\) 中出现，或者在 \(b\) 中出现的位置比 \(a_i\) 更早时才可以删掉。这个也比较自然。
时间复杂度 \(\mathcal{O}(n)\)。
CF1446B Catching Cheaters
看着就很 dp 的样子。
注意到 LCS 增长一位会导致答案 \(+2\)，而没有匹配上则会使答案 \(-1\)。用类似 LCS 的 dp 方法即可。
时间复杂度 \(\mathcal{O}(nm)\)。
CF1450D Rating Compression
考虑从简单的 \(k\) 下手。
对于 \(k=1\)，只有当 \(a\) 为一个 \(1 \sim n\) 的排列时才成立。
对于 \(k=n\)，只要 \(a\) 中存在 \(1\) 就对了。
对于 \(1<k<n\)，会发现 \(1\) 只能放在序列的头尾。而我们把 \(1\) 去掉，剩下的序列对于 \(2\) 依然有相同结论。
这件事情启发我们维护一个双端队列。遍历 \(i=1\cdots n\)，表示正在处理 \(k=n-i+1\) 时候的答案。每次判断队列首尾是否为 \(i\) 即可。
维护 \(c_i\) 表示 \(i\) 的出现次数，如果 \(c_i \geq 2\) 就说明对于所有 \(k< n-i+1\) 都至少会有两个区间包含 \(i\)，那么 \(b\) 就一定不是排列了。直接跳出循环就好。
时间复杂度 \(\mathcal{O}(n)\)。
CF1466E Apollo versus Pan
这个式子看着很吓人，其实就是交换求和号的 trick。
会发现整个式子是以 \(j\) 为联系串在一起的，那我们把 \(j\) 提到最前面，整理一下可以得到
\[\sum_{j=1}^n \left(\sum_{i=1}^n x_i \operatorname{and} x_j\right) \times \left(\sum_{k=1}^n x_k \operatorname{or} x_j\right) \]对于这个式子，枚举 \(j\) 拆位考虑即可。
时间复杂度 \(\mathcal{O}(n \log W)\)。
CF1477A Nezzar and Board
令 \(S=\{a_i\}\)，先找一些特殊元素，看看有没有好的性质。
考虑 \(0\)，会发现如果 \(0 \in S\)，那么我们可以通过令 \(y=0\) 构造出任意 \(nx\)。
如果把 \(a_i\) 扔到数轴上，会发现 \(2x-y\) 其实是 \(y\) 关于 \(x\) 的对称点，这样我们只需要考虑相对位置。为了得到 \(0\)，可以把 \(k\) 和所有 \(a_i\) 减去 \(a_1\)，得到 \(S'=\{a_i-a_1\}\)。
在 \(S'\) 中，我们可以构造元素的整数倍以及它们的线性组合，只需要判断是否存在系数 \(c_i\) 使得
\[\sum_{i=1}^nc_i\times(a_i-a_1)=k \]成立。
这个东西就是 \(n\) 元裴蜀定理，充要条件是 \(\gcd(a_i-a_1) \mid k\)。
时间复杂度 \(\mathcal{O}(n \log V)\)。
CF1491D Zookeeper and The Infinite Zoo
\(u \operatorname{and}v=v\) 等价于 \(v\in u\)，这样 \(u+v\) 的意义相当于在 \(u\) 中选择一些 \(1\)，在这些位上 \(+1\) 并向前进位。
我们把一条路径看成 \(u\) 变到 \(v\) 的变化过程，会发现每一步都会消去 \(u\) 低位上的一些 \(1\) 并向高位进位。如果我们从低位到高位统计 \(1\) 的个数，那么 \(u\) 一定会在任意时刻 \(\geq v\)。
如果这件事情满足，由于图是无限大的，那么我们自然可以找到合法的构造。
时间复杂度 \(\mathcal{O}(q\log V)\)。
CF1500A Going Home
神秘题。
在一个数组里找到满足要求的四元组是很困难的。一个朴素的暴力是对 \(a_i+a_j\) 的和开一个桶，如果某个桶里的元素的出现次数 \(\geq 2\) 说明找到了。
自然认为时间复杂度为 \(\mathcal{O}(n^2)\)，然而实际上复杂度上限为 \(\mathcal{O}(\min\{n^2,n+V\})\)，暴力做即可通过。
简单证明一下，如果我们找到了四对两两不完全相同的无序数对 \((x_i,y_i)\) 满足
\[a_{x_1}+a_{y_1}=a_{x_2}+a_{y_2}=a_{x_3}+a_{y_3}=a_{x_4}+a_{y_4} \]就可以找到合法的 \((x,y,z,w)\) 了。
- 如果 \(a_{x_i}\) 全部相同，那么 \((y_i)\) 就是合法的 \((x,y,z,w)\)。
- 如果 \(a_{x_i}\) 有三个相同，不妨设 \(a_{x_4}\) 与其他三个不同，那么 \((x_1,y_1,x_4,y_4)\) 就是合法的 \((x,y,z,w)\)。
- 对于其他情况，随便取两组都合法。
这件事情告诉我们，如果我们枚举到一个值四次，那么必然能找到一组合法的解。
\(a_i+a_j\) 一共只有不超过 \(5\times 10^6\) 种取值，所以枚举上界不超过 \(2\times 10^7\) 就可以找出一组解。
CF1508B Almost Sorted
妙妙题。
\(a_{i+1}\geq a_i-1\) 保证了如果出现 \(a_{i+1}<a_i\) 则必然有 \(a_{i+1}=a_i-1\)，也就是说，所有合法的序列应该是由若干极长子段构成的，每一个子段都是公差为 \(-1\) 的等差数列。
每一个合法序列都可以看成由 \(1,2,3,\cdots,n\) 切成若干个区间，每个区间翻转得到的结果。一共有 \(n-1\) 个空隙可以选择，所以一共会生成 \(2^{n-1}\) 个合法序列。
我们把合法序列看成一个 \(n-1\) 位的二进制数，如果 \(a_i>a_{i+1}\) 则填上 \(1\)，否则填上 \(0\)。例如 \([3,2,1,4,6,5,7]\rightarrow (110010)_2\)。二进制数和合法序列构成了双射。
断言，字典序第 \(k\) 小的序列对应的二进制数为 \(k-1\)。证明可以考虑 \(m\) 与 \(m+1\) 生成的序列的关系，会发现 \(m+1\) 永远比 \(m\) 字典序更大。由于二者构成双射，所以得证。
这样我们只需要对 \(k-1\) 进行二进制分解，按照极长子段进行构造，把每一段倒序填入即可。
时间复杂度 \(\mathcal{O}(n+\log k)\)。
CF1517D Explorer Space
四联通网格图必然是二分图，不存在奇环，所以当 \(k\) 为奇数时无解。
由于可以重复走，那么最优的路径必然是向外走最短的 \(\dfrac{k}{2}\) 步再原路返回，答案乘以 \(2\)。
考虑 dp，设 \(f(i,j,d)\) 表示走到格子 \((i,j)\) 且花了 \(d\) 步的最短路，层与层之间转移，转移方式显然。
时间复杂度 \(\mathcal{O}(nmk)\)。
CF1534D Lost Tree
一次询问可以得到一个点的邻域，也就是所有与这个点距离为 \(1\) 的点。
注意到询问次数不超过点数的一半，启发我们按照深度分层。
先随便找一个点询问，得到每个点的深度。按照深度奇偶性将点划分为两个集合，取点数更少的集合询问其中每个点，就可以得到每条边了。\(|S|+|T|=n\)，显然有 \(\min\{|S|,|T|\}\leq \dfrac{n}{2}\)。
注意一些实现细节，不要浪费每一次询问。
CF1548B Integers Have Friends
自然考虑差分，那么就是找到一个最大的区间，使得 \(\gcd \neq 1\)。
对差分数组用 ST 表维护区间 \(\gcd\)，二分区间长度，扫一遍判断有没有合法的区间即可。
时间复杂度 \(\mathcal{O}(n \log n \log V)\)。
CF1552C Maximize the Intersections
考虑一条线段什么时候的贡献最大，应该是它分割出的两段弧上的点尽量两两匹配，这样经过这条线段的次数最多，交点也就最多。
具体地，我们把剩下的 \(2(n-k)\) 个点重标号，让 \(i\) 与 \(i+n-k\) 相连。会发现交换任意两条弦的端点都会让交点个数减少，从而这样做是最优的。先连上线，最后暴力数交点。
时间复杂度 \(\mathcal{O}(Tn^2)\)。
CF1552D Array Differentiation
首先，\(a_i\) 的正负不重要，可以根据我们的需要任意定符号。其次，\(a_i\) 的顺序也不重要，可以根据我们的需要任意打乱重排。
如果 \(a\) 的长度为 \(n-1\)，那么这件事情就好办了。我们可以让 \(b_1=0\)，\(b_{i+1}=b_i+a_i\)，通过构造前缀和的方式表达出所有的 \(a_i\)。
但是这样做可能导致 \(a_n\) 构造不出来。如果存在区间 \([l,r]\) 满足 \(a_l+a_{l+1}+\cdots+a_r=a_n\)，那么 \(a_n\) 就可以表示为 \(b_r-b_{l-1}\)。更进一步，如果存在 \(a\) 的两个不交子集，满足它们的和相等，就可以通过构造前缀和的方式得到 \(b\)。
暴力枚举 \(\mathcal{O}(Tn4^n)\)，通过子集枚举可以做到 \(\mathcal{O}(Tn3^n)\)。
CF1556C Compressed Bracket Sequence
\(n\leq 1000\)，考虑 \(n^2\) 做法。
固定左端点在某个段 \(i\) 里，考虑右端点变化带来的影响。如果某个时刻右括号多于左括号，则需要用 \(i\) 中的一部分左括号与其匹配来保证括号串的合法性。
右端点向右扫的过程中，维护 \(L,R\) 未匹配的左右括号数量，\(S\) 表示第 \(i\) 段中能用来补齐的左括号还剩多少。由于左右括号交替被添加，所以能匹配一定是第一时间匹配上。扫一遍就好了。
时间复杂度 \(\mathcal{O}(n^2)\)。
CF1556D Take a Guess
想通过位运算直接得到第 \(k\) 小是不可能的。注意到 \(a+b=(a\operatorname{and}b)+(a\operatorname{or}b)\)，可以通过两次询问得到 \(a_i+a_j\)，正好符合了 \(2n\) 的询问次数上限。
先用六次询问得到 \(a_1+a_2,a_2+a_3,a_1+a_3\)，解出 \(a_1,a_2,a_3\) 的值。后面每次询问得到 \(a_1+a_i\) 的值，减去 \(a_1\) 就可以得到 \(a_i\)。得到所有数之后排序输出第 \(k\) 小即可。
CF1572A Book
对于 \(x\) 依赖 \(y\)，考虑连边 \(y\rightarrow x\)。如果依赖有环，那就无解，否则整张图是个 DAG。
发现「至少读几遍书」描述的其实就是「被访问最晚的点在第几轮被访问」。由于读书是从前往后读，所以编号小的优先级更大。
用优先队列做拓扑，以被访问的轮数为第一关键字，编号大小为第二关键字。如果 \(u\rightarrow v\) 但是 \(v<u\)，说明想读 \(v\) 需要先在上一轮读了 \(u\)，轮数要 \(+1\)。
时间复杂度 \(\mathcal{O}(n\log n)\)。
CF1630B Range and Partition
曾经 vp 过，但是想不起来怎么做了。
挺不错的题。
设在 \([x,y]\) 之间的数有 \(t\) 个，那么有 \(t\geq n-t+k\)，也就是 \(t\geq\dfrac{n+k}{2}\)。容易说明，\(t\) 更大，区间的长度就要更大，那么 \(y-x\) 就要更大。所以直接取 \(t=\left\lceil\dfrac{n+k}{2}\right\rceil\)。
注意到 \(x,y\) 一定都是 \(a\) 中的数，否则扩大 \(x\) 并缩小 \(y\) 可以使得答案更优。对 \(a\) 排序，用长度为 \(t\) 的滑动窗口扫一遍，找到差最小的 \([a_{i-t+1},a_i]\) 就是 \([x,y]\)。
构造划分方案，会发现这个 \(t\) 是恰好卡死的，所以仍然是在序列上扫，对在 \([x,y]\) 内外的数的个数计数，如果内比外大了就立刻切一刀。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1637D Yet Another Minimization Problem
先拆一下式子。
\[\begin{aligned} \sum_{i=1}^n\sum_{j=i+1}^n(x_i+x_j)^2&=\sum_{i=1}^n\sum_{j=i+1}^nx_i^2+2x_ix_j+x_j^2 \\ &=(n-1)\sum_{i=1}^nx_i^2+2\sum_{i=1}^n\sum_{j=i+1}^nx_ix_j \end{aligned} \]平方项都是定值，交换 \(a_i,b_i\) 也不会产生改变。只需最小化交叉项。
注意到值域很小，考虑对交叉项进行 dp。设 \(f(i,j)\) 表示前 \(i\) 项中 \(a\) 的和为 \(j\) 的最小值。为了方便转移，这里先不带系数 \(2\)，后面再乘。
预处理 \(a_i+b_i\) 的前缀和 \(S_i\)，这样能快速得到前 \(i\) 项中 \(b\) 的和为 \(S_i-j\)。
如果不交换，那么 \(a_i\) 的贡献为 \(a_i\times (j-a_i)\)，\(b_i\) 的贡献为 \(b_i\times (S_{i-1}-(j-a_i))\)。如果交换，那么 \(a_i\) 的贡献为 \(a_i\times (S_{i-1}-(j-b_i))\)，\(b_i\) 的贡献为 \(b_i\times (j-b_i)\)。
时间复杂度 \(\mathcal{O}(n\sum a_i+b_i)\)。
CF1648B Integral Array
值域很小，考虑反过来从倍数上下手。
枚举 \(y\) 及其倍数 \(x\)，想要判断 \(t=\dfrac{x}{y}\) 是否应该存在于集合中。而满足 \(\left\lfloor\dfrac{x'}{y}\right\rfloor=t\) 应该满足 \(ty\leq x'\leq(t+1)y-1\)，也就是 \(x\leq x'\leq x+y-1\)。
用桶装一下所有数，对桶做前缀和，就可以快速查询一个区间内有没有数。如果 \([x,x+y-1]\) 存在 \(x'\) 且 \(t\) 没有在数组中出现，那就寄了。
时间复杂度 \(\mathcal{O}(n\ln n)\)。
CF1666C Connect the Points
观察到答案总是 \(x_{\max}-x_{\min}+y_{\max}-y_{\min}\)。由于只有三个点，这件事情也易于说明。
考虑构造。找到 \(x\) 坐标处于中间的点 \((x_{\text{mid}}, y_{\text{mid}})\)，在这里弄一条竖直线，其他两个点用水平线与这条竖直线相交，多余的部分擦掉即可。交点都是好找的。
时间复杂度 \(\mathcal{O}(1)\)。
CF1666L Labyrinth
搜索题。
我们从起点的能到达的点开始搜索，把能到达的点染色，染过色的点不重复经过。如果某一次走到了之前某次染色的点，那就找到了两条不相交路径。
时间复杂度 \(\mathcal{O}(n+m)\)。
CF1750D Count GCD
\(b_i\) 只需要满足 \(\gcd(a_{i-1},b_i)=a_i\) 即可，这说明 \(b_i\) 的选取是独立的。那么 \(b_i\) 的选法就是
\[\sum_{x=1}^m[\gcd(a_{i-1},x)=a_i] \]把 \(a_i\) 除掉，同时记 \(m'=\left\lfloor\dfrac{m}{a_i}\right\rfloor\)，\(w=\dfrac{a_{i-1}}{a_i}\)，则有
\[\sum_{x=1}^{m'}[\gcd\left(w,x\right)=1] \]这个东西是很标准的莫反的形式。直接上莫反即可。
\[\begin{aligned} \sum_{x=1}^{m'}[\gcd\left(w,x\right)=1] &= \sum_{x=1}^{m'}\sum_{d\mid\gcd(x,w)}\mu(d) \\ &=\sum_{d\mid w}\mu(d)\sum_{d\mid x}1 \\ &=\sum_{d\mid w}\mu(d)\left\lfloor\dfrac{m'}{d}\right\rfloor \end{aligned}\]这个东西直接暴力算就可以，复杂度 \(\mathcal{O}(\sqrt{m}\log m)\)。
CF1801B Buying Gifts
把所有数对 \((a_i,b_i)\) 按照 \(a\) 从大到小排序，钦定 \(a_k\) 作为给 A 的最大礼物，那么 \([1,k-1]\) 都给了 B，可以通过前缀 \(\max\) 算出来。
考虑 \(k\) 后面的决策。首先，只有在 \(a_k\) 大于前缀最大值 \(M_{k-1}\) 时才能进行决策。否则 \(a_k \leq M_{k-1}\)，后面更小的 \(b_i\) 显然不会做贡献，而更大的 \(b_i\) 则不如 \(M_{k-1}\) 带来的答案优。
为了让极差最小，给 B 的只需要考虑 \(a_k\) 的前驱和后继，其他都给 A。用 multiset 维护即可。为了实现动态插入，可以从后往前扫 \(k\) 的位置。
注意实现细节。只需要对能做贡献的情况算了即可，多算可能会导致答案被算小。
时间复杂度 \(\mathcal{O}(n \log n)\)。
CF1824B1 LuoTianyi and the Floating Islands (Easy Version)
对 \(k=1,2,3\) 分类讨论。
当 \(k=1\) 时，好的节点就是它自己。答案为 \(1\)。
当 \(k=2\) 时，好的节点就是 \((u,v)\) 链上的所有点。考虑反过来统计，每个点被算到的次数应该是其两边的子树大小乘起来。算完方案数，最后除以 \(n(n-1)\) 就是期望。
当 \(k=3\) 时，好的节点就是三个点两两 \(\text{lca}\) 中更大的那个点。证明可以移动它，发现无论怎么移动都会让距离变大。从而答案也为 \(1\)。
时间复杂度 \(\mathcal{O}(n)\)。
CF1852A Ntarsis' Set
很精彩的题目！
我们不妨换一个角度，假设我们预先知道了答案，观察答案在集合中的位置变化。
可以发现，如果给定一个数的位置，那么它的位置在后续过程会一直前移，如何变化是可以知道的。而我们知道最后答案的位置，考虑倒推过程。
设最后的集合为 \(\{A,\cdots\}\)，可以这样进行倒推：遍历操作数组，如果 \(a_i\) 小于等于目前 \(A\) 的位置，则代表操作前该位置有数被删除，且在 \(A\) 之前，故应该将 \(A\) 的位置右移。
可以发现，这个过程中 \(A\) 的位置一直在后移，所以之前让 \(A\) 移动过的操作在下一轮还会让 \(A\) 右移，直接加上即可。
时间复杂度 \(\mathcal{O}(n+k)\)。
CF1870D Prefix Purchase
首先，如果 \(a_i \geq a_{i+1}\)，那么就可以踢掉 \(a_i\)。用单调栈踢掉没有用的操作，只需要对递增的序列考虑。
贪心，优先级的第一关键字应该是选择次数，其次是每次选择能覆盖的长度。从小到大考虑，先贪心地选尽量多 \(a_i\)，剩余的钱可以和一个 \(a_i\) 一起补一个 \(a_{i+1}\) 过来。
注意一点细节，不能出现类似买了 \(3\) 个 \(a_i\) 但是补了 \(5\) 个 \(a_{i+1}\) 这种情况。
时间复杂度 \(\mathcal{O}(n)\)。
标签：选做,1800,复杂度,记录,CF,提交,mathcal,可以,sum From： https://www.cnblogs.com/duckqwq/p/18132121