A. Dora’s Set （思维）

题意：

$Dora$有一个包含整数的集合 $s$。一开始，她会将 KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲l, r\]中的所有整数放入集合 $s$。也就是说，整数 $x$最初会在集合中，当且仅当 $l\le x\le r$时。然后执行以下操作：

• 从集合 $s$中选择三个不同的整数 $a$、 $b$和 $c$，使得 $\gcd (a,b)=\gcd (b,c)=\gcd (a,c)=1$。

• 从集合 $s$中删除这三个整数。

请问可以执行的最大操作数是多少？

分析：

我们考虑倒偶数彼此之间不互质。相邻的奇数是互质的，那么我们只需要统计出区间中奇数个数，两个一对凑对数，除以$2$即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int N = 3e5 + 10;
const int InF = 2e9 + 5;
const int mod = 998244353;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){int l, r;cin >> l >> r;int ans;if (l & 1){ans = (r - l + 1 + 1) / 2;}else{ans = (r - l + 1) / 2;}ans /= 2;cout << ans << endl;}return 0;
}

B. Index and Maximum Value （思维）

题意：

给出一个整数数组 $a\_1,a\_2,\dots ,a\_n$按顺序执行 $m$个操作。每个操作都属于以下两种类型之一：

• $\text{+ l r}$。给定两个整数 $l$和 $r$，对于所有 $1\le i\le n$且 $l\le a\_i\le r$，$a\_i:=a\_i+1$。

• $\text{- l r}$。给定两个整数 $l$和 $r$，对于所有 $1\le i\le n$且 $l\le a\_i\le r$， $a\_i:=a\_i-1$。

例如，如果初始数组为 KaTeX parse error: Undefined control sequence: \[ at position 5: a = \̲[̲7, 1, 3, 4, 3\]，执行操作 $\text{+}24$后，数组变为 KaTeX parse error: Undefined control sequence: \[ at position 5: a = \̲[̲7, 1, 4, 5, 4\]。然后，执行操作 $\text{-}110$后，数组变为 KaTeX parse error: Undefined control sequence: \[ at position 5: a = \̲[̲6, 0, 3, 4, 3\]。

输出每执行一次操作后的数组最大值。

分析：

发现只有最大值被操作覆盖到才会改变最大值，我们只需要维护最大值是否改变即可。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int N = 3e5 + 10;
const int InF = 2e9 + 5;
const int mod = 998244353;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){LL n, ma = 0, m, x = 0;cin >> n >> m;for (int i = 1; i <= n; i++){cin >> x;ma = max(ma, x);}for (int i = 1; i <= m; i++){char op;LL l, r;cin >> op >> l >> r;if (ma >= l && ma <= r){if (op == '+')ma++;elsema--;}cout << ma << " ";}cout << endl;}return 0;
}

C.Dora and C++ （数学）

题意：

给出一个长度为$n$的数组和两个整数 $a$和 $b$。可以选择进行以下操作之一。

• 选择一个整数 $i$，使得 $1\le i\le n$，并将 $c\_i$增加 $a$。

• 选择一个整数 $i$，使得 $1\le i\le n$，并将 $c\_i$增加 $b$。

让我们将数组 $d$的范围定义为 $\max (d\_i)-\min (d\_i)$。例如，数组 KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲1, 2, 3, 4\]的范围是 $4-1=3$，数组 KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲5, 2, 8, 2, 2, …的范围是 $8-1=7$，数组 KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲3, 3, 3\]的范围是 $3-3=0$。

经过任意数量的操作（可能是 $0$），我们会计算出新数组的范围。现在我们需要最小化这个值。输出这个值。

分析：

我们每次可以让两个数字之间相对移动的数为$a$和$b$的最大公约数的倍数。那么我们计算出公约数后，再对数组内所有的数都取模。这样可以通过取模使得每个数字都在一个区间内，该区间大小为模的大小。此时的答案是排序后最大值减去最小值，之后我们滑动区间，计算能取到的最小值，答案同样是取区间的最大值和最小值的差。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int N = 3e5 + 10;
const int InF = 2e9 + 5;
const int mod = 998244353;
LL A[N];
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){LL n, a, b;cin >> n >> a >> b;LL cc = __gcd(a, b);for (int i = 1; i <= n; i++){cin >> A[i];A[i] %= cc;}sort(A + 1, A + 1 + n);n = unique(A + 1, A + 1 + n) - A - 1;LL ans = A[n] - A[1];for (int i = 2; i <= n; i++){ans = min(A[i - 1] + cc - A[i], ans);}cout << ans << endl;}return 0;
}

D.Iris and Game on the Tree （博弈论）

题意：

$Iris$和$Dora$玩游戏。有一棵以顶点 $1$为根的树。每个顶点的值为 $0$或 $1$。让我们考虑树的一片叶子（顶点 $1$永远不会被视为叶子）并定义其权重。构造一个由从根开始到此叶子结束的路径上顶点的值组成的字符串。叶子的权重是其中子串 $10$和 $01$的出现次数之差。 树的得分定义为树中权重非零的叶子的数量。但有些顶点的值尚未确定，将以 $\text{?}$的形式提供给你。$Iris$和$Dora$每次选择值为 $\text{?}$的顶点，并将其 值更改为 $0$或 $1$，$Iris$先手。游戏持续进行，直到树中没有值为 $?$的顶点。$Iris$的目标是最大化树的得分，而 $Dora$的目标是最小化得分。 假设两个人都发挥出最佳水平，请确定树的最终得分。

分析：

我们可以发现除了叶子结点和根节点外，其余节点对于叶子节点的权重无任何影响，那么游戏本质是改变根和叶子的值。如果某个叶节点的值和根节点一样，那么就有分数，反之无分数。那么如果一开始根节点非空，先手必须给叶节点填另一个数字，后手给叶节点填和根节点一样的数字。否则，如果叶节点为?，先手可以根据当前叶节点情况考虑抢先填叶节点，选择最终分数高的那个情况。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int N = 3e5 + 10;
const int InF = 2e9 + 5;
const int mod = 998244353;
vector<int> edge[N];
char a[N];
LL b[2], ans, res;
void dfs(int u, int father)
{int sum = 0;for (int i = 0; i < edge[u].size(); i++){int v = edge[u][i];if (v == father){continue;}dfs(v, u);sum++;}if (sum == 0){if (a[u] == '?')ans++;else if (a[u] == '0')b[0]++;elseb[1]++;}else{if (u != 1 && a[u] == '?'){res++;}}
}
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){int n;cin >> n;ans = b[1] = b[0] = res = 0;for (int i = 1; i <= n; i++)edge[i].clear();for (int i = 1; i < n; i++){int u, v;cin >> u >> v;edge[u].push_back(v);edge[v].push_back(u);}for (int i = 1; i <= n; i++)cin >> a[i];dfs(1, 0);if (a[1] == '?'){LL ma = 0;if (b[1] < b[0])swap(b[1], b[0]);ma = max(b[1] + ans / 2, ma);ma = max(min(b[1], b[0] + 1) + (ans) / 2, ma);if (res & 1)ma = max(ma, b[1] + b[0] + ans - ma);cout << ma << endl;}else{if (a[1] == '1')cout << b[0] + (ans + 1) / 2 << endl;elsecout << b[1] + (ans + 1) / 2 << endl;}}return 0;
}

E.Iris and the Tree （图论）

题意：

给定一个有根树，其根位于顶点 $1$。对于树中的任何顶点 $i$，都有一条边连接顶点 $i$和 $p\_i$,其权重等于 $t\_i$。 $Iris$不知道 $t\_i$的值，但她知道 $\sum \_{i=2}^{n}t\_i=w$和每个 $t\_i$都是非负整数。树的顶点以特殊方式编号：每个子树中顶点的编号都是连续的整数。换句话说，树的顶点按深度优先搜索的顺序编号。

我们将 $\mathrm{dist}(u,v)$定义为树中顶点 $u$和 $v$之间的简单路径的长度。

接下来，将有 $n-1$个事件：

• 为 $Iris$提供整数 $x$和 $y$，表示 $t\_x=y$。

在每个事件之后，$Iris$想知道对于每个 $i$( $1\le i\le n$) 而言， $\mathrm{dist}(i,i\mathrm{mod}n+1)$最大可能值。她只需要知道这些 $n$个值的总和。

请注意，在计算 $i\ne j$的 $\mathrm{dist}(i,i\mathrm{mod}n+1)$和 $\mathrm{dist}(j,j\mathrm{mod}n+1)$的最大可能值时，未知边权重可能不同。

分析：

对于每条路径，其收益为$w$减去路径外已经确定的边权和。但是我们要进行特判：如果路径上边全部确定，那么其值就是路径权值和。其次可以注意到每条边在所有路径中一共出现两次。初始时，收益为$n\times w$。如果考虑已经满了的路径，我们发现我们的收益就是：已满路径的带权长度和 $+$未满路径条数 $\times$$(w$$-$已出现路径长度和$)$$+$$\Sigma$未满路径上已出现的边权和。 再考虑对于一条边KaTeX parse error: Undefined control sequence: \[ at position 1: \̲[̲p\[u\], u\]，我们如何找到两条路径的端点。我们找到$u-1$和 $u$所在子树最大 $dfs$序，我们逆着 $dfs$序进行计算，那么有$lca(i,(i+1)\%n)=fa(i+1)$，所以我们可以很容易处理出每条路径的边的数目。

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
#define endl '\n'
#define PII pair<LL, LL>
const int N = 3e5 + 10;
const int InF = 2e9 + 5;
const int mod = 998244353;
int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);int t;cin >> t;while (t--){int n;LL w;cin >> n >> w;vector<int> p(n), d(n), res(n), submax(n);vector<vector<int>> adj(n);for (int i = 1; i < n; ++i){cin >> p[i], --p[i];adj[p[i]].push_back(i);}for (int u = 0; u < n; ++u)for (int v : adj[u])d[v] = d[u] + 1;for (int i = 0; i + 1 < n; ++i)res[i] = d[i] + d[i + 1] - d[p[i + 1]] * 2;res[n - 1] = d[n - 1];iota(submax.begin(), submax.end(), 0);for (int i = n - 1; i; --i)submax[p[i]] = max(submax[i], submax[p[i]]);vector<LL> len(n);LL ans = 0, sum = 0, o = 0;int cnt = 0;for (int i = 1, v; i < n; ++i){LL t;cin >> v >> t;--v;int u = v - 1, sub = submax[v];sum += t;len[u] += t, len[sub] += t;o += 2 * t;if (!--res[u]){ans += len[u];o -= len[u];++cnt;}if (!--res[sub]){ans += len[sub];o -= len[sub];++cnt;}cout << ans + (n - cnt) * (w - sum) + o << " ";}cout << endl;}return 0;
}

赛后交流

在比赛结束后，会在交流群中给出比赛题解，同学们可以在赛后查看题解进行补题。

群号： 704572101，赛后大家可以一起交流做题思路，分享做题技巧，欢迎大家的加入。