CF2267 - Div2
2026-09-26 12:11:35
发布于：广东
39阅读
0回复
0点赞
前言：最爽的切题
AB
不讲
C
本质暴力题，预处理出 的质因数，然后对于每个质因数，按照题目意思模拟即可。
ll ma = 0;
for (int p : primes) {
ll cur = 0;
for (int i = 1; i <= n; ++i) {
if (a[i] % p == 0) {
cur += a[i];
}
}
ma = max(ma, cur);
}
D
一眼奇偶下标要分开，所以从这个出发，观察到我们要让 顺序入队，维护一个双指针 。若当前 和 奇偶性相同，当前数字所在坐标奇偶性也要一致，反之同理。
所以归纳一下：
- 为偶数，所以类似维护双指针，所以要保证 奇偶性相同才又解；
- 为奇数，所以 一定要填 位置（ 位置同理），然后转化为偶数情况。
int n;
cin >> n;
vec<int> p(n + 1);
for (int i = 1; i <= n; ++i) {
int x;
cin >> x;
p[x] = i & 1;
}
if (n & 1) {
if (p[1] != 1) {
cout << "NO" << endl;
return;
}
for (int i = 2; i < n; i += 2) {
if (p[i] == p[i + 1]) {
cout << "NO" << endl;
return;
}
}
} else {
for (int i = 1; i < n; i += 2) {
if (p[i] == p[i + 1]) {
cout << "NO" << endl;
return;
}
}
}
cout << "YES" << endl;
E
推式子。
一眼发现 是恒定的，跟 块有关，简单推一下 ，其中 表示 的数量。
接下来考虑一个 的幂，记为 ：
对于前面的那个式子，记为 。我们按照 的定义思考，对于一个 的点 所产生的贡献，就是左右点的个数，即 ，所以：
对于后面的式子，记为 。考虑到这个式子可以转化为异或的 移一下运算：
所以发现跟端点是否相同有关，当且仅当为 或者 才能产生贡献，所以得出
这样这个答案就是：
修改也很简单，单次影响的， 可动态更新。
ll get(ll i, ll n) { return (i + 1) * (n - i - 1); }
void Main() {
int n, q;
cin >> n >> q;
string s;
cin >> s;
ll c0 = 0, c1 = 0;
for (char c : s) {
if (c == '0')
++c0;
else
++c1;
}
ll val = 0;
for (int i = 0; i < n - 1; ++i) {
if (s[i] != s[i + 1])
val += get(i, n);
}
cout << (val + c0 * c1) / 2 << ' ';
while (q--) {
int pos;
cin >> pos;
int idx = pos - 1;
if (idx > 0 && s[idx - 1] != s[idx])
val -= get(idx - 1, n);
if (idx < n - 1 && s[idx] != s[idx + 1])
val -= get(idx, n);
if (s[idx] == '0') {
--c0, ++c1;
s[idx] = '1';
} else {
++c0, --c1;
s[idx] = '0';
}
if (idx > 0 && s[idx - 1] != s[idx])
val += get(idx - 1, n);
if (idx < n - 1 && s[idx] != s[idx + 1])
val += get(idx, n);
cout << (val + c0 * c1) / 2 << ' ';
}
cout << endl;
}
F1
本质暴力题，证明一下吧。
设当前二进制数最高有效位为第 位（即最大值属于 ）。
我们将数组分成两组：
- 第 位为 的元素，共 个；
- 第 位为 的元素，共 个，满足 。
当两个数来自同一组时，它们的异或值第 位为 （即 ）。这种数对的数量为：
- 当 时：。这意味着最高位为 0 的数对数量就已经 个了。因为我们取的是前 小的数，所以新数组中的所有数最高位都必然变成了 0。即每一轮变换至少彻底消除 1 个最高位。
- 当 时：最坏情况下每 2 轮也必然消除 1 个最高位。
- 当 很大时（例如 ）：根据抽屉原理，前 位相同的数对数量就已经超过 个了，仅需 2 到 3 轮数组就全变成 0 了！
数值 ，总共只有 30 个二进制位：
- 时，最多变换 30 轮；
- 时，最多变换 60 轮；
- 只要 ，所有元素相等，后续所有变换的数对异或全为 0，可以直接
break。
所以我们每次 暴力更新数组，记录答案即可。
int get(const vec<int> &a) {
auto [mx, mi] = minmax_element(a.begin(), a.end());
return *mx - *mi;
}
void Main() {
int n, q;
cin >> n >> q;
vec<int> a(n);
for (int &i : a)
cin >> i;
vec<int> ans;
ans.pb(get(a));
vec<int> tmp;
tmp.reserve(n * n);
while (ans.size() > 0 && ans.size() <= 100) {
tmp.clear();
for (int i = 0; i < n; ++i)
for (int j = i + 1; j < n; ++j) {
tmp.pb(a[i] ^ a[j]);
}
nth_element(tmp.begin(), tmp.begin() + n, tmp.end());
for (int i = 0; i < n; ++i)
a[i] = tmp[i];
ans.pb(get(a));
}
for (int i = 0; i < q; ++i) {
ll x;
cin >> x;
if (x < (ll)ans.size())
cout << -ans[x] << endl;
else
cout << 0 << endl;
}
}
有帮助，赞一个