Codeforces Round 900 (Div. 3) 题解 A-E
目录
- A. How Much Does Daytona Cost?
- B. Aleksa and Stack
- C. Vasilije in Cacak
- D. Reverse Madness
- E. Iva & Pav
A. How Much Does Daytona Cost?
本题要求判断整数 k 是否出现在给定的数组中。这是一个基础的查找问题，直接遍历数组或使用哈希表即可解决。
B. Aleksa and Stack
构造一个满足条件的序列，使得任意相邻两个元素之和不能被后面的元素整除。
一种简单有效的构造方法是：全部使用奇数
- 奇数 + 奇数 = 偶数
- 奇数 × 3 = 奇数
由于奇数无法被偶数整除，因此满足题目要求。从2或3开始，后续依次选取奇数即可。
C. Vasilije in Cacak
在等差数列 [1, 2, 3, ..., n] 中选取 k 个数，求能达到的最小和与最大和。
- 最小和：选取最小的 k 个数，即 1 + 2 + ... + k = k(k+1)/2
- 最大和：选取最大的 k 个数，即 n + (n-1) + ... + (n-k+1)
可以证明，最小和与最大和之间的任何值都可以通过适当的选取得到。
D. Reverse Madness
本题的关键在于理解题目中的特殊性质。给定区间 [l_i, r_i] 和位置 x，令：
a = min(x, l_i + r_i - x)
b = max(x, l_i + r_i - x)
区间 [a, b] 表示的是 [l_i, r_i] 中 x 关于区间中点的对称子区间。
由于 l_i ≤ l_i + r_i - x ≤ r_i，且 (x + l_i + r_i - x)/2 = (l_i + r_i)/2，可见这是对称翻转。
每个区间的翻转操作相互独立，因此可以使用差分数组统计每个位置的翻转次数：
- 翻转奇数次：输出对称位置的字符
- 翻转偶数次：输出原位置的字符
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n, k;
cin >> n >> k;
string str;
cin >> str;
str = " " + str;
vector<int> L(k + 1), R(k + 1);
for (int i = 1; i <= k; ++i) cin >> L[i];
for (int i = 1; i <= k; ++i) cin >> R[i];
vector<int> diff(n + 2, 0);
int q;
cin >> q;
while (q--) {
int x;
cin >> x;
int idx = lower_bound(R.begin() + 1, R.end(), x) - R.begin();
int left = min(x, L[idx] + R[idx] - x);
int right = max(x, L[idx] + R[idx] - x);
diff[left]++;
diff[right + 1]--;
}
for (int i = 1; i <= k; ++i) {
for (int pos = L[i]; pos <= R[i]; ++pos) {
diff[pos] += diff[pos - 1];
if (diff[pos] % 2 == 1) {
cout << str[L[i] + R[i] - pos];
} else {
cout << str[pos];
}
}
}
cout << '\n';
}
return 0;
}E. Iva & Pav
本题要求在区间 [l, r] 中找到最大的右端点，使得该区间的位与值大于等于 k。
关键观察：从左向右依次进行位与运算，结果是单调递减的。这允许我们使用二分查找。
解法一：线段树维护区间位与
建立线段树，每个节点存储对应区间的位与值，查询复杂度为 O(log n)。结合二分查找，整体时间复杂度为 O(q log² n)。
#include <bits/stdc++.h>
using namespace std;
struct SegmentTree {
int n;
vector<int> tree;
SegmentTree(int n): n(n), tree(n * 4, 0) {}
void build(int node, int l, int r, const vector<int>& arr) {
if (l == r) {
tree[node] = arr[l];
return;
}
int mid = (l + r) / 2;
build(node * 2, l, mid, arr);
build(node * 2 + 1, mid + 1, r, arr);
tree[node] = tree[node * 2] & tree[node * 2 + 1];
}
int query(int node, int l, int r, int ql, int qr) {
if (ql <= l && r <= qr) return tree[node];
int mid = (l + r) / 2;
int result = (1 << 31) - 1;
if (ql <= mid) result &= query(node * 2, l, mid, ql, qr);
if (qr > mid) result &= query(node * 2 + 1, mid + 1, r, ql, qr);
return result;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> arr(n + 1);
for (int i = 1; i <= n; ++i) cin >> arr[i];
SegmentTree st(n);
st.build(1, 1, n, arr);
int q;
cin >> q;
while (q--) {
int l, k;
cin >> l >> k;
int left = l, right = n, ans = l - 1;
while (left <= right) {
int mid = (left + right) / 2;
int val = st.query(1, 1, n, l, mid);
if (val >= k) {
ans = mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
if (ans < l) cout << -1 << ' ';
else cout << ans << ' ';
}
cout << '\n';
}
return 0;
}解法二：倍增预处理 + 二分
预处理跳跃表，f[i][j] 表示从位置 i 跳 2^j 步后的区间位与值，next[i][j] 表示跳跃后的位置。查询时从大到小枚举跳跃长度。
#include <bits/stdc++.h>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
const int LOG = 20;
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
vector<int> a(n + 1);
for (int i = 1; i <= n; ++i) cin >> a[i];
vector<vector<int>> jump(n + 2, vector<int>(LOG));
vector<vector<int>> nxt(n + 2, vector<int>(LOG, n + 1));
for (int i = 1; i < n; ++i) {
jump[i][0] = a[i + 1];
nxt[i][0] = i + 1;
}
for (int j = 1; j < LOG; ++j) {
for (int i = 1; i <= n; ++i) {
if (nxt[i][j - 1] <= n) {
jump[i][j] = jump[i][j - 1] & jump[nxt[i][j - 1]][j - 1];
nxt[i][j] = nxt[nxt[i][j - 1]][j - 1];
}
}
}
int q;
cin >> q;
while (q--) {
int l, k;
cin >> l >> k;
if (a[l] < k) {
cout << -1 << ' ';
continue;
}
int cur = a[l];
int pos = l;
for (int j = LOG - 1; j >= 0; --j) {
if (nxt[pos][j] <= n && (cur & jump[pos][j]) >= k) {
cur &= jump[pos][j];
pos = nxt[pos][j];
}
}
cout << pos << ' ';
}
cout << '\n';
}
return 0;
}