P2007(div2)

C. Dora and C++

题目描述

Dora 有两个整数 \(a\) 和 \(b\) 。在一次运算中，她可以选择以下操作之一。

选择一个整数 \(i\) ，使得 \(1 \leq i \leq n\) ，并将 \(c _ i\) 增加 \(a\) 。
选择一个整数 \(i\) ，使得 \(1 \leq i \leq n\) ，并将 \(c _ i\) 增加 \(b\) 。

注意 \(a\) 和 \(b\) 是常数，它们可以相同。

我们把数组 \(d\) 的范围定义为 \(\max(d _ i) - \min(d _ i)\) 。例如，数组 \([1, 2, 3, 4]\) 的取值范围是 \(4 - 1 = 3\) ，数组 \([5, 2, 8, 2, 2, 1]\) 的取值范围是 \(8 - 1 = 7\) ，数组 \([3, 3, 3]\) 的取值范围是 \(3 - 3 = 0\) 。

经过任意次数的操作后(可能是 \(0\) )，Dora 会计算出新数组的范围。你需要帮助 Dora 最小化这个值，答案输出最小值即可。

输入

每个测试由多个测试用例组成。第一行包含一个整数 \(t\) ( \(1 \leq t \leq 10^4\) ) - 测试用例数。测试用例说明如下。

每个测试用例的第一行包含三个整数 \(n\) 、 \(a\) 和 \(b\) ( \(1 \leq n \leq 10^5\) , \(1 \leq a, b \leq 10^9\) )--分别是数组 \(c\) 的长度和常量值。

每个测试用例的第二行包含 \(n\) 个整数 \(c _ 1, c _ 2, \ldots, c _ n\) ( \(1 \leq c _ i \leq 10^9\) ) - 数组 \(c\) 的初始元素。

保证所有测试用例中 \(n\) 的总和不超过 \(10^5\) 。

输出

对于每个测试用例，输出一个整数 - 数组经过任意次数操作后的最小可能范围。

题解

根据裴蜀定理：

设 \(a,b\) 是不全为零的整数，对任意整数 \(x,y\)，满足 \(\gcd(a,b)\mid ax+by\)，且存在整数 \(x,y\), 使得 \(ax+by=\gcd(a,b)\).

在这个问题情境中，我们设 \(d = \gcd(a,b)\)，很容易发现，任意选择两个操作的过程，实际上等价于允许对数组中的任何一个数 \(\pm d\)。

因此，问题首先可以简化为对原数组每个元素 \(\mod d\) 之后，求最小极差。

在所有元素都在 \([0, d)\) 区间内的情况下，考虑对数列排序，那么答案就是 \(a_{n - 1} - a_0\)。要使得这个值更小，可进行的操作只有 \(a_0 = a_0 + d\)，重新检查答案。

这个过程可以考虑使用一个双端队列实现，最终时间复杂度是 \(O(n \log(n))\)，主要来自于排序。

AC 代码

#include <bits/stdc++.h>
using namespace std;

void solve() {
  int n;
  cin >> n;
  int x, y;
  cin >> x >> y;
  int g = __gcd(x, y);
  deque<int> a(n);
  for (int &i : a) {
    cin >> i;
    i = i % g;
  }
  if (n == 1) {
    cout << 0 << '\n';
    return;
  }
  sort(a.begin(), a.end());
  int ans = a[n - 1] - a[0];
  for (int i = 0; i < n; i++) {
    ans = min(a[0] + g - a[1], ans);
    a.push_back(a.front());
    a.pop_front();
  }
  cout << ans << '\n';
}

signed main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);

  int t = 1;
  cin >> t;
  while (t--) {
    solve();
  }
}

D. Iris and Game on the Tree

题目描述

艾里斯有一棵根植于顶点 \(1\) 的树。每个顶点的值为 \(\mathtt 0\) 或 \(\mathtt 1\) 。

让我们考虑树的一片叶子(顶点 \(1\) 不被视为叶子)并定义它的权重。构建一个字符串，字符串由从树根开始到这片叶子结束的路径上的顶点值构成。那么叶子的权重就是其中 \(\mathtt{10}\) 和 \(\mathtt{01}\) 子串出现次数的差值。

以下面这棵树为例。绿色顶点的权重为 \(\mathtt 1\) ，白色顶点的权重为 \(\mathtt 0\) 。

我们来计算叶子 \(5\) 的权重：形成的字符串为 \(\mathtt{10110}\) 。子串 \(\mathtt{10}\) 的出现次数为 \(2\) ，子串 \(\mathtt{01}\) 的出现次数为 \(1\) ，因此两者的差值为 \(2 - 1 = 1\) 。
我们来计算叶子 \(6\) 的权重：形成的字符串为 \(\mathtt{101}\) 。子串 \(\mathtt{10}\) 的出现次数为 \(1\) ，子串 \(\mathtt{01}\) 的出现次数为 \(1\) ，因此两者的差值为 \(1 - 1 = 0\) 。

树的得分定义为树上权重不为零的叶子的数量。

但是有些顶点的权重还没有确定，因此会给出 \(\texttt{?}\) 。填空会很无聊，所以 Iris 打算邀请 Dora 玩一个游戏。每轮游戏中，两个女孩中的一个选择剩余顶点中数值为 \(\texttt{?}\) 的任意一个，并将其数值更改为 \(\mathtt{0}\) 或 \(\mathtt{1}\) ，由 Iris 先来。游戏继续进行，直到树中不再有值为 \(\mathtt{?}\) 的顶点。 Iris 的目标是让树的得分最大化，而 Dora 的目标是让树的得分最小化。

假设两个女孩都以最佳方式进行游戏，请确定这棵树的最终得分。

输入

每个测试由多个测试用例组成。第一行包含一个整数 \(t\) ( \(1 \leq t \leq 5\cdot 10^4\) ) - 测试用例的数量。测试用例说明如下。

每个测试用例的第一行都包含一个整数 \(n\) ( \(2 \leq n \leq 10^5\) ) - 树的顶点数。

接下来的 \(n - 1\) 行分别包含两个整数 \(u\) 和 \(v\) ( \(1 \leq u, v \leq n\) ) - 表示顶点 \(u\) 和 \(v\) 之间的一条边。

可以保证给定的边构成一棵树。

最后一行包含长度为 \(n\) 的字符串 \(s\) 。 \(s\) 的 \(i\) -th 字符代表顶点 \(i\) 的值。可以保证 \(s\) 只包含字符 \(\mathtt{0}\) 、 \(\mathtt{1}\) 和 \(\mathtt{?}\) 。

保证所有测试用例中 \(n\) 的总和不超过 \(2\cdot 10^5\) 。

输出

对于每个测试用例，输出一个整数 - 树的最终得分。

题解

首先，必须做出一个重要的观察：

叶子的权重是从根节点到叶子节点的路径中， \(\mathtt{10}\) 和 \(\mathtt{01}\) 子串出现次数的差值。

记树的某一叶子节点为 \(u\)，其权重为 \(f(u)\)，其值为 \(v(u) \in [0, 1]\)，上述定义实际上等价为：

\[ w(u) = \left\{ \begin{aligned} 1 & & v(u) = v(root) \\ 0 & & v(u) \neq v(root) \\ \end{aligned} \right. \]

这个性质并不难验证，但是稍微有一些观察难度。

做出如上观察后，我们可以发现，对于博弈来说，最重要的问题是根节点的状态，由此可以做出分类讨论如下：

当根节点的颜色已经确定，博弈非常简单，Iris 和 Dora 每轮选择一个？叶子节点，设置成对自己有利的颜色。
当根节点的颜色未确定，且叶子节点中，1 和 0 的个数不一样多；此时，先手的玩家可以选定根节点的颜色，使游戏优势偏向自己，