Global Round 18
A. Closing The Gap
题意
给定 $n$ 个数字，每次操作可以选择其中两个数字 $a_i, a_j$ ，令 $a_i-1$ 且 $a_j + 1$ 。
问若干次操作后，极差最小为多少。
分析
显然如果 $n | \sum_{i=1}^na_i$ ，那么我们一定能找到方案使得每个数字都相同，那么极差为 $0$ 。
否则，我们可以取每个数字为 $\lfloor \dfrac {\sum_{i=1}^n a_i} n \rfloor$ ，剩下的数量小于 $n$ ，平均地分布在每个数字上，这样极差为 $1$ 。
Code
/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
void solve ()
{
int n, sum = 0; cin >> n;
for (int i = 1, x; i <= n && cin >> x; i ++ ) sum += x;
cout << (sum % n ? 1 : 0) << endl;
}
signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}
B. And It’s Non-Zero
题意
给出范围 $[l, r]$ ，你拥有这个范围内的所有正整数。你可以删除某些数字。
问，最少删除多少数字，满足剩下的数字按位和为 $0$ 。
分析
要使得一些数字的按位和不为 $0$ ，那么只需要满足存在某一个位，所有数字在这一个位上都为 $1$ 。
具体来说，我们可以枚举每一位，求出要使所有数字都在这个位上为 $1$ 的最小删除数量，求最小值即可。
预处理 $f(i, j)$ 表示前 $i$ 个数字第 $j$ 位为 $0$ 的数量。
Code
/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
const int N = 200010, INF = 0x3f3f3f3f;
int f[N][30]; // 前i个数字第j个位为0的数量
void init ()
{
for (int i = 1; i < N; i ++ )
for (int j = 0; j <= 20; j ++ )
f[i][j] = f[i-1][j] + !(i >> j & 1);
}
void solve ()
{
int l, r, res = INF; cin >> l >> r;
for (int i = 0; i <= 20; i ++ ) res = min(f[r][i] - f[l-1][i], res);
cout << res << endl;
}
signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (init(), cin >> _; _--; ) solve();
return 0;
}
C. Menorah
题意
有 $n$ 个蜡烛，给出每个蜡烛的起始状态（亮或者灭）。
每次操作可以选择一个 亮着的 蜡烛，让它保持状态不变，且其他所有蜡烛改变状态。
给出每个蜡烛的目标状态，问从起始状态到目标状态至少需要操作几次，如果无解输出 $-1$ 。
分析
首先我们可以发现，对于起始状态 != 目标状态的所有蜡烛，他们被操作的次数的奇偶性是相同的；对于起始状态 == 目标状态的所有蜡烛，他们被操作的次数的奇偶性也是相同的。但是上述两类的蜡烛操作次数奇偶性不同。
证明：设 $x_i$ 表示第 $i$ 个蜡烛的操作次数。
对于第 $i$ 个蜡烛而言，它改变状态的次数为 $S = \sum_{j=1}^{i-1}x_i + \sum_{j=i+1}^{n}x_i$ 。
对于任意一个其他的蜡烛 $j$ ，它改变的次数为 $S’ = S + x_i - x_j$ 。
如果 $i$ 蜡烛是需要改变状态的，比如从原始的 $0$ 变成最终的 $1$ ，那么对于 $j$ 而言，如果它也需要改变状态，那么 $S’ = S = 1 \pmod 2$ ，从而推出 $x_i = x_j \pmod 2$ 。如果 $j$ 不需要改变状态，那么 $S’ != S \pmod 2$ ，推出 $x_i != x_j \pmod 2$ 。
同理如果 $i$ 蜡烛不需要改变状态，我们同理可得上述结论。
然后我们可以发现每个蜡烛如果被操作，它最多被操作一次。
所以我们实际上只有两种可能的解法。
- 只对所有起始和目标不同的蜡烛每个做一次操作。
- 只对所有起始和目标相同的蜡烛每个做一次操作。
那么如何求出解法是否可行？
容易发现，我们的操作对象一定为 $101010101 \ldots$ 。（这里指的是原始的状态）
我们先对原始状态的 $1$ 操作，由于这个已经操作过了，所以对剩下没有操作的蜡烛，本来是 $0$ 的现在变成 $1$ ，我们对 $1$ 操作，本质上是对原始状态的 $0$ 操作。
同时，我们对 $10$ 操作后，本质上是交换了这两个状态，其他状态没有改变。
第一种解法：
假设起始和目标为 $01$ 的蜡烛数量为 $k_0$ ，起始和目标为 $10$ 的蜡烛数量为 $k_1$ 。那么我们只能每次交换一个 $01$ 。所以如果 $k_0 != k_1$ ，那么无法通过交换来达到目标，无解。否则我们交换 $2 \times k_0$ 次即可交换所有的 $01$ 对。
第二种解法：
假设起始和目标为 $00$ 的蜡烛数量为 $e_0$ ，起始和目标为 $11$ 的蜡烛数量为 $e_1$ 。那么我们需要交换 $01$ 使得他们与目标都不相同，这样如果最后只剩下一个 $1$ （也就是 $e_0 = e_1 - 1$） ，那么操作这个 $1$ 就可以把其他所有状态改变，也就是全部变成目标状态。
注意特判起始和目标相同的情况。
Code
/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
void solve ()
{
int n; cin >> n;
string a, b; cin >> a >> b;
if (a == b) return cout << 0 << endl, void();
int k1 = 0, k0 = 0;
int e1 = 0, e0 = 0;
for (int i = 0; i < n; i ++ )
{
if (a[i] == '1' && b[i] == '0') ++ k1;
else if (a[i] == '0' && b[i] == '1') ++ k0;
else if (a[i] == '1' && b[i] == '1') ++ e1;
else if (a[i] == '0' && b[i] == '0') ++ e0;
}
if (k1 != k0)
{
if (e0 == e1 - 1) return cout << e0 * 2 + 1 << endl, void();
return cout << -1 << endl, void();
}
if (e0 == e1 - 1) return cout << min(e0 * 2 + 1, k1 + k0) << endl, void();
cout << k1 + k0 << endl;
}
signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}
D. X(or)-mas Tree
题意
给定 $n$ 个结点的带权无根树和 $m$ 个限定条件 $(u, v, w)$ 。求出任意一个满足限制的树。
给出的边权如果为 $-1$ ，表示这个边权待定。
限定条件 $(u, v, w)$ ，表示从 $u$ 出发到达 $v$ 的路径上的所有边的异或和的 $popcount$ 的奇偶性 。
$popcount$ 指一个数字二进制位下 $1$ 的数量。
分析
首先有一个等式 $popcount(x \bigoplus y) = popcount(x) \bigoplus popcount(y) \pmod 2$ 。
证明：假设 $popcount(x) = k_1, popcount(y) = k_2$ 。
那么 $popcount(x \bigoplus y) = k_1 + k_2 - cnt \times 2$ ，其中，$cnt$ 表示在某一位上 $x = y = 1$ ，这样的位的个数。
显然 $k1 + k2 - cnt \times 2 = k_1 + k_2 \pmod 2$ 。
设 $a(u)$ 表示从结点 $u$ 到达根节点的路径异或和的 $popcount$ 。
对于限制条件 $(u, v, w)$ ， 其实就是 $a(u) \bigoplus a(v) = w$ 。
对于给出的边 $(u, v, w)$ ，如果给定了边权，其实也是一个限制条件，因为 $a(u) \bigoplus a(v) = popcount(w)$ 。
我们先把这些限制条件全部扔到另外一张图上。
容易发现，我们给边权填上 $0, 1$ 即产生两种不同的奇偶性，只需要填 $0$ 或者 $1$ 即可。
那么我们对限制图做染色法求出 $a(i)$ 即可。
Code
/* 终点是一切概率的结束，也是一切期望的开始 */
#include <bits/stdc++.h>
using namespace std;
const int N = 200010, M = 1200010;
#define pop(x) __builtin_popcount(x)
int n, m;
int h[N], rh[N], e[M], w[M], ne[M], idx;
int a[N];
bool vis[N]; // vis 用来染色
bool cant;
/*
a(i) 表示从i到根节点路径上的异或和的popcount
cant 表示无解
*/
void init (int n)
{
for (int i = 1; i <= n; i ++ ) h[i] = rh[i] = -1;
idx = 0;
for (int i = 1; i <= n; i ++ ) a[i] = vis[i] = 0;
cant = 0;
}
void add (int h[], int a, int b, int c)
{
e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx ++ ;
}
void dfs (int u, int fa, int c)
{
if (cant) return ;
a[u] = c; vis[u] = true;
for (int i = rh[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
if (!vis[j]) dfs(j, u, c ^ w[i]);
else if ((a[j] ^ a[u]) != w[i]) { cant = true; return; }
// 如果j被染色过，需要满足限制，否则无解
}
}
void print (int u, int fa)
{
for (int i = h[u]; ~i; i = ne[i])
{
int j = e[i];
if (j == fa) continue;
if (w[i] != -1) cout << u << ' ' << j << ' ' << w[i] << endl;
else cout << u << ' ' << j << ' ' << (a[u] ^ a[j]) << endl;
print(j, u);
}
}
void solve ()
{
cin >> n >> m;
init(n);
for (int i = 1; i < n; i ++ )
{
int a, b, c; cin >> a >> b >> c;
add(h, a, b, c); add(h, b, a, c);
if (c != -1) // 边不为-1，做一条限制
add(rh, a, b, pop(c) & 1), add(rh, b, a, pop(c) & 1);
}
// 后面还有m条限制
for (int i = 1; i <= m; i ++ )
{
int a, b, c; cin >> a >> b >> c;
add(rh, a, b, c); add(rh, b, a, c);
}
// 染色
for (int i = 1; i <= n; i ++ ) if (!vis[i]) dfs(i, -1, 0);
if (cant) return cout << "NO\n", void();
cout << "YES\n";
print(1, -1);
}
signed main ()
{
cout.tie(0)->sync_with_stdio(0);
int _; for (cin >> _; _--; ) solve();
return 0;
}
