当前位置：首页 > news >正文

2026-04-18 模拟赛总结

news 2026/4/19 15:41:29

链接

A

糖题。

简单手玩就可以发现，除了两个数只贡献一次之外，其它所有数对最后结果的贡献都是偶数次，而众所周知对某个数做两次异或就会抵消。

因此答案就是 \(\max\limits_{1 \le i < j \le n} \{a_i \oplus a_j \}\)。

代码

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const int INF = 0x3f3f3f3f, _INF = 0xc0c0c0c0;
const ll LLINF = 0x3f3f3f3f3f3f3f3f, _LLINF = 0xc0c0c0c0c0c0c0c0;namespace IO {
// 略
} // namespace IO
using IO::err;
using IO::read;
using IO::write;const int N = 3110;
int T, n, a[N];void solve() {read(n);for (int i = 1; i <= n; i++) read(a[i]);int ans = 0;for (int i = 1; i <= n; i++) {for (int j = i + 1; j <= n; j++) {ans = std::max(ans, (a[i] ^ a[j]));}}write(ans, '\n');
}int main() {// freopen(".in", "r", stdin);// freopen(".out", "w", stdout);read(T);while (T--) solve();#ifdef CLOCKstd::cerr << "\033[95m" << clock() * 1.0 / CLOCKS_PER_SEC << "s\n\033[90m";
#endifreturn 0;
}

B

赛场上离做出这道题就差一步之遥，可惜由于脑子短路，将询问次数卡死在了 \(4 \log (2n + 1)\)，遗憾离场。
考虑到如果对某个下标集合 \(S\) 询问得到的结果是 \(\operatorname{ans}(S)\)，如果 \(|S| - \operatorname{ans}(S)\) 是奇数，那么说明其中一定有某个数出现了 \(3\) 次。

因此我们按以下流程依次找到这三个位置：

二分找到最小的 \(z \in [1, 2n + 1]\)，使 \([1, z]\) 是满足上述要求的 \(S\)。
二分找到最大的 \(x \in [1, z - 2]\)，使 \([x, z]\) 是满足上述要求的 \(S\)。
二分找到最小的 \(y \in [x + 1, z - 1]\)，使 \([x, y] \cup \{z\}\) 是满足上述要求的 \(S\)。

于是 \(x, y, z\) 就是要求的三个位置。

代码

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const int INF = 0x3f3f3f3f, _INF = 0xc0c0c0c0;
const ll LLINF = 0x3f3f3f3f3f3f3f3f, _LLINF = 0xc0c0c0c0c0c0c0c0;const int N = 1e5 + 10;
int T, n;void solve() {std::cin >> n;n = 2 * n + 1;int pos1 = 0, pos2 = 0, pos3 = 0;int l = 1, r = n;while (l < r) {int mid = (l + r) >> 1;std::cout << "? " << mid << ' ';for (int i = 1; i <= mid; i++) {std::cout << i << ' ';}std::cout << std::endl;int ans;std::cin >> ans;if ((mid - ans) & 1) {r = mid;} else {l = mid + 1;}}pos3 = r;r = pos3 - 2; l = 1;while (l < r) {int mid = (l + r + 1) >> 1;std::cout << "? " << pos3 - mid + 1 << ' ';for (int i = mid; i <= pos3; i++) {std::cout << i << ' ';}std::cout << std::endl;int ans;std::cin >> ans;if ((pos3 - mid + 1 - ans) & 1) {l = mid;} else {r = mid - 1;}}pos1 = l;l = pos1 + 1, r = pos3 - 1;while (l < r) {int mid = (l + r) >> 1;std::cout << "? " << mid - pos1 + 2 << ' ';for (int i = pos1; i <= mid; i++) {std::cout << i << ' ';}std::cout << pos3 << ' ';std::cout << std::endl;int ans;std::cin >> ans;if ((mid - pos1 + 2 - ans) & 1) {r = mid;} else {l = mid + 1;}}pos2 = r;std::cout << "! " << pos1 << ' ' << pos2 << ' ' << pos3 << std::endl;
}int main() {std::ios::sync_with_stdio(false); std::cin.tie(0);std::cin >> T;while (T--) solve(); #ifdef CLOCKstd::cerr << "\033[95m" << clock() * 1.0 / CLOCKS_PER_SEC << "s\n\033[90m";
#endifreturn 0;
}

C

并非很难的数据结构题，可惜我场上被 B 硬控了。

考虑在区间 \([l, r]\) 中，随着 \(d\) 的递增，\(\min(a_l, a_{l+1}, \cdots, a_{l+d})\) 是单调不增的。因此某个区间的 nastiness 不是 \(0\) 就是 \(1\)。同时我们注意到 \(\min(a_l, a_{l+1}, \cdots, a_{l+d}) - d\) 是单调递减的，因此可以二分找到其第一个小于等于 \(0\) 的位置，看其是否恰好等于 \(0\)。

因此只需要一个支持单点修改个区间求最小值的线段树即可。

代码

#include <bits/stdc++.h>
using ll = long long;
using ld = long double;
using ull = unsigned long long;
const int INF = 0x3f3f3f3f, _INF = 0xc0c0c0c0;
const ll LLINF = 0x3f3f3f3f3f3f3f3f, _LLINF = 0xc0c0c0c0c0c0c0c0;namespace IO {
// 略
} // namespace IO
using IO::err;
using IO::read;
using IO::write;const int N = 2e5 + 10;
int a[N], n, T, q;struct Segtree {int tr[4 * N];void pushUp(int p) {tr[p] = std::min(tr[p*2], tr[p*2+1]);}void build(int s = 1, int t = n, int p = 1) {if (p == 1) memset(tr, 0x3f, sizeof(int) * (4 * n + 1));if (s == t) {tr[p] = a[s];return;}int mid = (s + t) >> 1;build(s, mid, p*2);build(mid+1, t, p*2+1);pushUp(p);}void update(int l, int c, int s = 1, int t = n, int p = 1) {if (s == t) {tr[p] = c;return;}int mid = (s + t) >> 1;if (l <= mid) update(l, c, s, mid, p*2);else update(l, c, mid+1, t, p*2+1);pushUp(p);}int query(int l, int r, int s = 1, int t = n, int p = 1) {if (l <= s && t <= r) {return tr[p];}int res = INF, mid = (s + t) >> 1;if (l <= mid) res = std::min(res, query(l, r, s, mid, p*2));if (r > mid) res = std::min(res, query(l, r, mid+1, t, p*2+1));return res;}
} tree;bool check(int p, int l) {return tree.query(l, p) - (p - l) <= 0;
}void solve() {read(n, q);for (int i = 1; i <= n; i++) read(a[i]);tree.build();while (q--) {int opt;read(opt);if (opt == 1) {int i, x;read(i, x);tree.update(i, x);} else {int ll, rr;read(ll, rr);int l = ll, r = rr;while (l < r) {int mid = (l + r) >> 1;if (check(mid, ll)) {r = mid;} else l = mid + 1;}if (tree.query(ll, r) - (r - ll) == 0) {write("1\n");} else write("0\n");}}
}int main() {read(T);while (T--) solve();#ifdef CLOCKstd::cerr << "\033[95m" << clock() * 1.0 / CLOCKS_PER_SEC << "s\n\033[90m";
#endifreturn 0;
}

查看全文

http://www.jsqmd.com/news/666601/