Codeforces Round 969 (Div. 2)

比赛链接

Problems	AC
A. Dora’s Set	○
B. Index and Maximum Value	○
C. Dora and C++	○
D. Iris and Game on the Tree	○
E. Iris and the Tree	○
F. Eri and Expanded Sets

C

给定一个序列，你可以任意次单点 $+A$ 或 $+B$ ，最小化极差。

单点 $+A$ 或 $+B$ 等价于单点 $\pm \operatorname{gcd}(A, B)$ 。

设 $g=\operatorname{gcd}(a, b)$ ，在 $\bmod g$ 意义下考虑

D

给定一棵树, 点权为 01 。定义一个叶子的权值为: 考虑从根到叶子的这条路径的点权组成的字符串，权值为其中 01 作为连续子串出现次数减去 10 作为连续子串出现次数。定义树的价值为：权值非零的叶子个数。现在一些点权变成?，博弈的两人分别填充，分别最大化和最小化树的价值。求最终树的价值。

观察发现，一条路径计入答案当且仅当叶子和根权值不同。所以只和根和叶子的权值有关。

若根的权值确定，则策略是唯一的。

如果根的权值不确定，则此时可以消耗非叶子结点的 ? 来转换先后手。策略也是显然的

E

给定一棵 dfs 序标号的树。每条边有不确定的非负整数边权，但你只知道边权和。定义 $f_i$ 为所有安排边权的情况下， $i$ 与 $(i \bmod n)+1$ 的距离的最大值。每次告诉你—条边的边权，求此时所有 $f_i$之和。

树按 dfs 序标号，所以最终的 $n$ 条路径中，每条边恰好被经过两次。

一条路径的权值可能是：已经全部确定，那就确定了；没有全部确定，权值是边权和减去路径外知道的边的权值和。

用全局加的 tag 维护即可。