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 v) = 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;
}