A
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[107];
int f[107];
bool solve() {
int n, k;
cin >> n >> k;
for (int i = 1;i <= n;i++) cin >> a[i];
for (int i = 1;i <= n - 1;i++) f[i] = abs(a[i + 1] - a[i]);
sort(f + 1, f + n);
int sum = 0;
for (int i = 1;i <= n - k;i++) sum += f[i];
cout << sum << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
B
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int n;
cin >> n;
int sum = ~(1 << 31), cnt = 0;
for (int i = 1;i <= n;i++) {
int x;
cin >> x;
sum &= x;
if (sum == 0) cnt++, sum = ~(1 << 31);
}
cout << max(cnt, 1) << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
C
题意
开始时有 \(n\) 个数，每次操作可以取一个后缀异或和放到所有数后面，问能取到的最大数字是多少。
题解
方法一
知识点：位运算，字典树。
我们发现，无论我们怎么取，取到的值一定是原来 \(n\) 个数字的一个连续段的异或和，因此问题变成求最大子段异或和。
最大子段异或和非常经典，可以用01Trie解决。
时间复杂度 \(O(8n)\)
空间复杂度 \(O(8n)\)
方法二
知识点：位运算，枚举。
这里只有 \(2^8\) ，所以也可以枚举。
时间复杂度 \(O(n2^8)\)
空间复杂度 \(O(n)\)
代码
方法一
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
class Trie {
struct Node {
array<int, 2> nxt;
int val;
};
int bit;
vector<Node> node;
Node NIL;
public:
Trie(int _bit = 0) { init(_bit); }
void init(int _bit) {
bit = _bit;
NIL = { {0,0},0 };
node.assign(1, NIL);
}
void insert(int s) {
int p = 0;
for (int i = bit - 1;i >= 0;i--) {
int c = (s >> i) & 1;
if (!node[p].nxt[c]) {
node[p].nxt[c] = node.size();
node.push_back(NIL);
}
p = node[p].nxt[c];
}
node[p].val = s;
}
int find(int s) {
int p = 0;
for (int i = bit - 1;i >= 0;i--) {
int c = (s >> i) & 1;
if (node[p].nxt[c ^ 1]) p = node[p].nxt[c ^ 1];
else p = node[p].nxt[c];
}
return node[p].val;
}
};
int a[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
Trie trie(8);
trie.insert(0);
int sum = 0, ans = 0;
for (int i = 1;i <= n;i++) {
sum ^= a[i];
ans = max(ans, sum ^ trie.find(sum));
trie.insert(sum);
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
代码二
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
int a[100007];
bool solve() {
int n;
cin >> n;
for (int i = 1;i <= n;i++) cin >> a[i];
vector<int> vis(1 << 8);
int sum = 0, ans = 0;
vis[0] = 1;
for (int i = 1;i <= n;i++) {
sum ^= a[i];
for (int j = 0;j < (1 << 8);j++)
if (vis[j]) ans = max(ans, sum ^ j);
vis[sum] = 1;
}
cout << ans << '\n';
return true;
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int t = 1;
cin >> t;
while (t--) {
if (!solve()) cout << -1 << '\n';
}
return 0;
}
D
题意
给定一个长为 \(n\) 的 \(01\) 串 \(s\) ，取其 \(m\) 个子串 \(s[l_i,r_i]\) ，按取的顺序从左到右拼接得到 \(t(s)\) 。
在取子串前，可以执行一种操作：交换 \(s\) 中的两个不同位置的字符。
问最少需要执行多少次操作，才能使得 \(t(s)\) 是所有可能的结果中字典序最大的。
题解
知识点：并查集，树状数组，贪心。
显然，子串靠前的，位置在子串中靠前的，优先级更大。因此，按子串顺序，子串内从左到右，给 \(s\) 的位置规定排名 \(rk\) 。
排名中可能会遇到之前已经排名过的位置，这些位置的排名是不需要改变的，我们需要跳过它们。为了保证复杂度，可以用并查集实现跳转，当然也可以用 set 。
接下来，我们要尽可能把 \(1\) 交换到排名靠前的位置，因此我们需要知道 \(1\) 的总数 \(cnt\) ，以及排名前 \(cnt\) 个位置的 \(1\) 个数 \(sum[1,cnt]\) ，交换次数就是 \(cnt - sum[1,cnt]\) 。
时间复杂度 \(O((n+q)\log n)\)
空间复杂度 \(O(n)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template <class T>
class Fenwick {
int n;
vector<T> node;
public:
Fenwick(int _n = 0) { init(_n); }
void init(int _n) {
n = _n;
node.assign(n + 1, T());
}
void update(int x, T val) { for (int i = x;i <= n;i += i & -i) node[i] += val; }
T query(int x) {
T ans = T();
for (int i = x;i >= 1;i -= i & -i) ans += node[i];
return ans;
}
T query(int l, int r) {
T ans = T();
ans += query(r);
ans -= query(l - 1);
return ans;
}
int lower_bound(T val) {
int pos = 0;
for (int i = 1 << __lg(n); i; i >>= 1) {
if (pos + i <= n && node[pos + i] < val) {
pos += i;
val -= node[pos];
}
}
return pos + 1;
}
int upper_bound(T val) {
int pos = 0;
for (int i = 1 << __lg(n); i; i >>= 1) {
if (pos + i <= n && node[pos + i] <= val) {
pos += i;
val -= node[pos];
}
}
return pos + 1;
}
};
struct DSU {
vector<int> fa;
DSU(int n = 0) { init(n); }
void init(int n) {
fa.assign(n + 1, 0);
iota(fa.begin(), fa.end(), 0);
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void merge(int x, int y) { fa[find(x)] = find(y); }
};
int idx;
int rk[200007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n, m, q;
cin >> n >> m >> q;
string s;
cin >> s;
s = "?" + s;
int cnt = count(s.begin() + 1, s.end(), '1');
Fenwick<int> fw(n);
DSU dsu(n + 1);
for (int i = 1;i <= m;i++) {
int l, r;
cin >> l >> r;
for (int j = dsu.find(l);j <= r;j = dsu.find(j)) {
rk[j] = ++idx;
if (s[j] == '1') fw.update(rk[j], 1);
dsu.merge(j, j + 1);
}
}
while (q--) {
int x;
cin >> x;
if (s[x] == '0') {
s[x] = '1';
cnt++;
if (rk[x]) fw.update(rk[x], 1);
}
else {
s[x] = '0';
cnt--;
if (rk[x]) fw.update(rk[x], -1);
}
cout << min(cnt, idx) - fw.query(min(cnt, idx)) << '\n';
}
return 0;
}