Codeforces Round 1079 (Div. 2)

/fendou

A

$d(y)$ 是 $\mathcal{O}(\log V)$ 的，枚举 $x+d(y)$ 并检查。

B

这个是经典结论，判一下 $a$ 去重后是不是 $p$ 的子序列即可。

证明：P10297 [CCC 2024 S3] Swipe - 洛谷

C

假设最后 Bob 赢了，此时的分数是 $\frac{2x}{3x}$ 。那么分子被操作了 $p-2x$ 次，分母被操作了 $q-3x$ 次。当 $p-2x=q-3x$ 时，Bob 有如下策略：如果 Alice 操作分子，那 Bob 就操作分母；如果 Alice 操作分母，那 Bob 就操作分子。否则，这是不可能的，因为 Alice 有如下策略：若 $p-2x<q-3x$ ，那么 Alice 一直操作分子，反之则一直操作分母，可以确保某个时刻分子 $<2x$ 或分母 $<3x$ 。可以解出唯一的 $x=q-p$ ，判一下是否满足 $x>0,p-2x>0,q-3x>0$ ，满足的话就是 Bob 赢，否则 Alice 赢。

D

因为 $j-i<n$ ，所以 $a_i\cdot a_j$ 同样 $<n$ ，即 $a_j<\frac{n}{a_i}$ 且 $a_i<\frac{n}{a_j}$ 。也就是二元组里一定至少有一个小于根号，用桶统计左右有没有满足条件的 $i$ 或 $j$ ，复杂度就是 $\mathcal{O}(n\sqrt n)$ 。

比赛的时候写复杂了一点。

E1, E2

这啥题啊，真不是模拟即可？？？

模拟过程：实现返回值类型为一条路径的函数 dfs(u,c)，代表当前 dfs 到点 $u$ ，字典序第 $c$ 大的路径是以 $u$ 为结尾的，同时维护以每个点为起点的路径条数 $f_u$ 。令 $c\leftarrow c+1$ ，查询 $c$ 。

如果结果为空说明做完了，立即退出。
如果结果是一个单独的点 $x$ ，立即退出，调用 dfs(x,c)。
如果结果里面的倒数第二个点不为 $u$ ，说明 $u$ 没有出边，将查询结果作为返回值并返回即可。
否则令结果里的最后一个点为 $v$ $v$ ，将 $(u,v)$ $(u, v)$ 加入边集。
- 如果 $v$ 是被访问过的点，令 $f_u\leftarrow f_u+f_v,c\leftarrow c+f_v$ 。返回 dfs(u,c)。
- 如果 $v$ $v$ 是未被访问过的点，调用 dfs(v,c+1)，令 $f_u\leftarrow f_u+f_v,c\leftarrow c+f_v$ $f_{u} \leftarrow f_{u} + f_{v}, c \leftarrow c + f_{v}$ 。
  - 如果其返回值里的倒数第二个点为 $u$ ，令最后一个点为 $v'$ ，令 $v\leftarrow v'$ ，跳转到开头。
  - 否则说明点 $u$ 的出边已经统计完毕，需要回溯到当前路径里在 $u$ 前面的点，直接返回这个返回值即可。

令 $k$ 为出度为 $0$ 的点的个数，这样做的询问次数最多是 $m+k+1\leq n+m$ 。

实现上细节有些多，赛时没过，离 ac 代码只差：

catch(pii e){
    f[u]+=f[v.back()];
    throw e;
}

F

首先肯定先把能匹配的部分给挖掉。经典地，在剩下的串里（后面的讨论都是基于剩下的串，将它叫做 $t$ ），对于圆括号和方括号，未匹配的串一定都是一堆右括号作为前缀，一堆左括号作为后缀。

考虑最终的匹配形式。对于最后的串中的一对匹配的括号，它们在修改前可能是：

((，([，(]，))，[)，])，花费一次操作成为 ()；
]]，)]，花费一次操作成为 []；

我们将这两种形式成为好的匹配。

][，)(，](，)[，花费两次操作。

对应地，我们将这种形式成为坏的匹配。若 $t$ 中的所有字符都能形成好的匹配，答案可以取到下界 $\frac{|t|}{2}$ 。考虑什么时候答案 $>\frac{|t|}{2}$ 。

观察到，任意两个方向相同的括号都可以形成好的匹配。那么先尝试将所有方向相同的括号两两配对，如果 $t$ 中的左括号有偶数个（因为 $n$ 是偶数，那么右括号一定也有偶数个），这个策略就可以构造出我们想要的 $\frac{|t|}{2}$ 。

反之， $t$ 中的左右括号都有奇数个。这种情况下，最后会剩下一个左括号和一个右括号。如果左括号在右括号左边（[) 或 (]），那答案仍为 $\frac{|t|}{2}$ 。于是可以贪心地取出所有左括号中位置最靠左（记其下标为 $i$ ）的和所有右括号中位置最靠右的（记其下标为 $j$ ），若 $i<j$ 答案为 $\frac{|t|}{2}$ ，否则答案为 $\frac{|t|}{2}+1$ 。

也就是说，答案为 $\frac{|t|}{2}+1$ 当且仅当左右括号分别有奇数个，且所有右括号在所有左括号左边。第二个约束使我们不可能进行左括号与右括号之间的好的匹配，而每次两个左括号之间进行的好的匹配不会改变左括号的奇偶性，最后一定剩下一个左括号无法进行好的匹配，因此进行 $1$ 次坏的匹配是必须的。

这个最优化问题的思考过程十分经典，先构造答案下界，再尽可能削减达不到答案下界的情况分支数量。