A.
倒着模拟。
B.
观察 2 操作会改变奇偶性，全部排序。如果 2 操作不会改变奇偶性，分开排序。
C.
每个数不能被加两次，很容易的想到二进制（因为 0/1）。
然后先找到最大的 $2^k \leq n$，再由高到低逐位构造即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| vector<int> ans{1};
while (ans.back() * 2 <= x) {
ans.emplace_back(ans.back() * 2);
}
x -= ans.back();
for (int i = 30; i >= 0; i--) {
if (x >> i & 1) {
ans.emplace_back(ans.back() + (1LL << i));
}
}
reverse(all(ans));
cout << sz(ans) << "\n";
for (int x : ans) {
cout << x << " ";
}
|
D.
不难观察出来，对一个数进行操作其实是对一整个三角形进行翻转。
如果对 $(i,j)$ 进行翻转的话，那么对 $x$ 行的影响其实是 $[j+i-x,j-i+x]$ 翻转。
观察到 $j + i$ 和 $j - i$ 最多只有 $O(n)$ 种取值，所以直接打上标记，整体处理。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
| unordered_map<int, int> mp1, mp2;
vector<int> b(n);
int row = 0, ans = 0;
while (row < n) {
rep (j, 0, n) b[j] = 0;
for (auto [x, c] : mp1) {
b[max(0, x - row)] ^= c;
}
for (auto [x, c] : mp2) {
if (x + row < n)
b[x + row] ^= c;
}
for (int j = 0; j < n; j++) {
if (j) {
b[j] ^= b[j - 1];
}
a[row][j] ^= b[j];
}
for (int j = 0; j < n; j++) {
if (a[row][j] == 1) {
ans += 1;
int y0 = j + row;
int y1 = j - row;
mp1[y0] ^= 1;
mp2[y1 + 1] ^= 1;
}
}
row++;
}
cout << ans << "\n";
|
E.
对于任意一组 (a, b)，答案为最长1前缀+(a<b)+1（忽略二进制下为0的位）
可以用字典树维护（当然也可以直接分治）
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
long long ans = 0;
auto dfs = [&](auto &dfs, int p) {
if (p == 0) {
return;
}
int lc = ch[p][0];
int rc = ch[p][1];
ans += sz[lc] * sz[rc] % P;
if (ans >= P) {
ans -= P;
}
dfs(dfs, lc);
ans += sz[rc] * sz[rc] % P;
if (ans >= P) {
ans -= P;
}
dfs(dfs, rc);
};
dfs(dfs, 1);
ans += 1ll * n * n % P;
if (ans >= P) {
ans -= P;
}
|
F.
对于值域 $[l, r]$，最多的次数显然是 $[l,r]$ 值域内的数字个数，考虑相邻的相同数字 $v$ 的位置 $pos1, pos2$，当 $(pos1,pos2)$ 内小于 $v$ 的最大值小于 $l$ 的时候可以少做一次操作（因为可以把对这俩数的操作直接连起来）
扫描线即可。
submission
G.
咕咕。
H.
