CF 补题记录

2022-03-31

Codeforces Round #761 (Div. 2)

• D1：通过询问连续的区间，用 $n-2$ 次询问找到一个 $0$ 和一个 $1$ 的位置，再用 $n-2$ 次确定剩下的情况。
• D2：将元素分为每三个一组，先查询每组的情况。由于题目中 $k$ 的特殊范围，可以知道必然有连续的两组返回的结果不同。再从这两组中用 D1 的方法找到一个 $0$ 和一个 $1$ 的位置，使用 $\frac{k}{3}+2$ 次询问。
• 发现可以通过已知的两个位置 $a,b$，对剩下的组进行分类讨论。每组 $3$ 个元素共 $8$ 种情况，之前询问出的 $0$ 或 $1$ 可以排除一半，将 $(i,i+1)$ 和对应的元素（$a$ 或 $b$，取决于该组的情况）进行询问，可以再排除一半。最后再询问一次得出结果。可以发现每 $3$ 个元素使用了 $2$ 次询问，即整道题目需要 $n+2$ 次询问。
• E：将固定的转换关系连边，可以将原题转化为树的直径问题。发现树高为 $\log n$ 级别，可以直接暴力跳父亲将需要的部分建出来，计算树的直径即可。

Codeforces Round #762 (Div. 3)

• D：二分答案，如果每一列都至少有一个数大于等于当前二分的 $x$，且至少一行有不少于 $2$ 个数大于等于 $x$，则 $x$ 合法。
• F：按顺序往下排大桌的座位。
• G：并查集维护每个连通块自行爆炸的最短时间，手动引爆时倒着选。
• H：预处理每个位置能跳到的下一个位置、前一个位置和下 $\sqrt{n}$ 个位置是什么，交换元素的时候都交换一下，并且重新跳 $\sqrt{n}$ 次即可消除影响。

Codeforces Round #763 (Div. 2)

• D：题解给出了最简单直接的做法。假设机器人在一个 $2\times 2$ 网格的对角线上来回走，则可以设 $x_1$ 为在 $(1,1)$ 时期望的完成步数，$x_2$ 为在 $(2,2)$ 是期望的完成步数，不难得到 $x_1=(1-p)(1+x_2),x_2=(1-p)(1+x_1)$，即 $x_1=(1-p)(1+(1-p)(1+x_1))$，可以解出 $x_1$。现在模拟一个循环，扩展一下上述的方程组，便可以得到形如 $x=kx+b$ 的形式，可以直接解出。注：暴力模拟一个循环即可，但也可以 $\Theta(1)$ 跳下一个有贡献的位置，做到 $\Theta(n+m)$。

• E：细节题。很容易想到贪心地复制，优先考虑左子树的节点。可以先复原字符串，找出哪些位置复制后更优，再贪心地选即可。注意如果 dfs 过程中左子树已经确定选上，则当前节点也一定选；而只有选了当前节点，再去考虑右子树。

Educational Codeforces Round 125

• A：最多走两步。如果 $\sqrt{x^2+y^2}$ 是正整数只走一步。
• B：能加就加，不能加就减。这样一定最优。
• C：左括号下一个字符是什么都能同时删掉这一对；右括号找到下一个右括号删除。
• D：显然 $\dfrac{d_1}{h_2}>\dfrac{d_2}{h_1}$ 等价于 $d_1h_1>d_2h_2$，因此贪心地预处理出对于每个 $c$ 最大的 $d\cdot h$，查询时二分。
• E：一个完全图有一个以 $1$ 为根的菊花图作为最小生成树的充要条件是：对于任意一条边 $(x,y)(x>1,y>1,x\ne y)$，满足 $w_{x,y}\ge\max(w_{1,x},w_{1,y})$。必要性考虑最小生成树的定义，充分性可以归纳证明。
• 设 $f_{i,j}$ 为当前有 $i$ 个结点连到了 $1$ 号点上，这些连到 $1$ 号点的边中最大的边权为 $j$。从 $f_{i,j}$ 转移到 $f_{i+k,j+1}$ 时枚举边权为 $j+1$ 的边的条数，方案数 $\dbinom{n-1-i}{k}$，新加进去的点还要和剩下已经连到 $1$ 的点连边，边权可以从 $[j+1,m]$ 选择，方案数 $(\dfrac{k(k-1)}{2}+ik)^{m-j}$。
• F：考虑每条路径时，每个位置最多有两个合法的字符。我们定义 $sel_{x,0/1}$ 数组为覆盖了 $x$ 这个点的，最近考虑的串正放/倒放时对应的字符。2-SAT 维护每条路径产生矛盾时的限制条件，对于每个串，该串正放/反放，$x$ 位置填 $sel_{x,0/1}$，会对应产生最多 $4$ 条限制。最后如果有合法答案序列 $ans$ 则依次输出 $sel_{i,ans_i}$。

Codeforces Round #779 (Div. 2)

• A：每两个 0 之间至少有 $2$ 个 1，开头的 0 无限制，直接模拟。
• B：反证法得到题目中所求的 $\gcd$ 最大为 $2$，只有 $n$ 是偶数时将偶数放在奇数位置上，奇数放在偶数位置上方案数为 $(\dfrac{n}{2}!)^2$，$n$ 是奇数答案为 $0$。
• C：对于第 $i$ 次循环变换后的排列，如果有 $p_1> p_2$ 则一定 $c_{i+1}\le c_i$，否则 $c_{i+1}=c_i+1$。所以 $c_{i+1}-c_i\le 1$ 且有且仅有一个 $c_i=1$ 时原序列有解。一种可能的构造方案：从 $1$ 到 $n$ 按照 $c_i$ 从大到小填，遇到 $c_i$ 相同的则先填编号小的。

• D：依次钦定原序列中每个位置为 $l$，01-trie 上查询 $a_i\operatorname{xor}l$ 能获得的最小/最大异或值，分别是 $l,r$ 则 $a_i\operatorname{xor} l$ 为答案。

• E：我们发现，如果先手选择了 $v_{x,y}$，后手无法再走到一个 $v_{x’,y’}$ 使得 $v_{x’,y’}> v_{x,y}$ 则先手下一步还可以走回去，后手必败。问题变成了从每个 $(x,y)$ 出发，是否满足曼哈顿距离 $> k$ 的格子中的权值均小于 $v_{x,y}$。

• 考虑 DP，设 $f_{i,j}$ 为 $(i,j)$ 是否合法，显然初始对于 $v_{sx,sy}=n^2$，有 $f_{sx,sy}=1$。我们维护一个当前合法点的集合 $S$，并从大到小枚举权值。考虑到当前权值时，如果 $S$ 中所有点距当前点的曼哈顿距离均 $\le k$ 则将当前点加入 $S$ 中。由于 $\abs{x-x’}+\abs{y-y’}\le k\Leftrightarrow\max(\abs{(x+y)-(x’-y’)},\abs{(x-y)-(x’-y’)})\le k$，我们只需要维护当前 $S$ 集合中所有 $(x+y),(x-y)$ 的最大值和最小值即可。
• F：首先，令 $u$ 为原串中 1 的个数，则这个串有解当且仅当 $u\cdot m\equiv 0\pmod{n}$。将原串拼成环形，则必定存在一个长度为 $m$ 的区间中 1 的个数恰好为 $\dfrac{u\cdot m}{n}$。如果这个区间跨过了环的连接处，则 $k=2$，否则 $k=1$。前缀和即可解决。

Records