A.
显然。
1
2
3
4
5
6
7
8
9
10
11
12
| void solve() {
int x, y, k;
cin >> x >> y >> k;
if (y <= x) {
cout << x << "\n";
} else {
int t = min(x + k, y);
cout << y + y - t << "\n";
}
}
|
B.
选择两个子集，极差之和最小。
显然是排序之后分两半。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| void solve() {
int n;
cin >> n;
vi a(n * 2);
rep(i, n * 2) cin >> a[i];
sort(all(a));
vi x, y;
rep(i, n) {
x.pb(a[i]);
}
rep(i, n) {
y.pb(a[i + n]);
}
int ans = a.back() - a[n] + a[n - 1] - a[0];
cout << ans << "\n";
rep(i, n) {
cout << x[i] << " " << y[i] << "\n";
}
}
|
C.
枚举偶数长度 $l$，然后选择可能的方案。
非常好写。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| int coef[10][50];
void solve() {
int n;
cin >> n;
vc<string> s(n);
rep(i, n) cin >> s[i];
ll ans = 0;
for (int l = 2; l <= 10; l += 2) {
memset(coef, 0, sizeof coef);
rep(i, n) {
if (sz(s[i]) < l) {
int sum = 0;
int c = 0;
for (int j = sz(s[i]) - 1; j >= 0; j--) {
c += 1;
if (c > l / 2) {
sum -= s[i][j] - '0';
} else {
sum += s[i][j] - '0';
}
}
if (sum >= 0) coef[sz(s[i])][sum] += 1;
sum = 0;
c = 0;
rep(j, sz(s[i])) {
c += 1;
if (c > l / 2) {
sum -= s[i][j] - '0';
} else {
sum += s[i][j] - '0';
}
}
if (sum >= 0) coef[sz(s[i])][sum] += 1;
}
}
rep(i, 1, l) {
rep(j, 50) {
ans += 1ll * coef[i][j] * coef[l - i][j];
}
}
}
cout << ans / 4 << "\n";
}
|
D.
简单讲讲我的做法。
考虑所有数字一定互不相同。（异或性质）
那么只需要满足 $\max \leq n-1$，即 $d_i \leq n - 1$，就可以满足这个序列是 ${0…n-1}$
我们假设 $x\ xor\ y_i = d_i$，使得 ${d_i}$ 为 ${0…n-1}$
那么 $x = y_i \ xor\ d_i$，由于 $y_i$ 互不相同，那么 $d_i$ 肯定也互不相同。
那只需要 $x \in \and {y_i\ xor\ 0, y_i\ xor\ 1…y_i\ xor\ n-1}$ 即可。
考虑对于一个数字 $y$，$y\ xor\ i$，$i \in [0, n-1]$ 会产生 $\log$ 个区间。
综上，可以用前缀和维护，交集的话相当于出现了 $n-1$ 次，复杂度 $O(n \log )$。
感觉别的做法都比我的简单啊。/ll
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| void solve() {
int n;
cin >> n;
vi a(n);
rep(i, 1, n) {
cin >> a[i];
a[i] ^= a[i - 1];
}
debug(a);
vi s(n * 4);
int t = n - 1;
rep(i, 1, n) {
int x = a[i];
for (int j = 20; j >= 0; j--) {
if (t >> j & 1) {
int k = 1 << j;
int l = x & ~(k - 1);
int r = l + k;
s[l] += 1;
s[r] -= 1;
x ^= k;
}
}
s[x] += 1;
s[x + 1] -= 1;
}
rep(i, 1, n) {
s[i] += s[i - 1];
}
rep(i, n) {
if (s[i] == n - 1) {
rep(j, n) {
cout << (a[j] ^ i) << " \n"[j + 1 == n];
}
return;
}
}
}
|
E.
贪心建边建立所有的关系，然后跑拓扑。
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| void solve() {
int n;
cin >> n;
vc<pii> a(n);
rep(i, n) cin >> a[i].fi;
rep(i, n) cin >> a[i].se;
int m;
cin >> m;
vc<pii> b(m);
rep(i, m) cin >> b[i].fi;
rep(i, m) cin >> b[i].se;
sort(all(a));
sort(all(b));
vc<pii> sa(n);
vc<pii> sb(m);
for (int i = n - 1; i >= 0; i--) {
sa[i] = {a[i].se, i};
if (i + 1 < n && sa[i + 1] > sa[i]) {
sa[i] = sa[i + 1];
}
}
for (int i = m - 1; i >= 0; i--) {
sb[i] = {b[i].se, i};
if (i + 1 < m && sb[i + 1] > sb[i]) {
sb[i] = sb[i + 1];
}
}
vc<vi> g(n + m);
vi d(n + m);
vi ans(n + m, -1);
rep(i, n) {
int j = lower_bound(all(b), pii(a[i].se + 1, 0)) - begin(b);
if (j == m) {
continue;
} else {
int x = n + sb[j].se;
int y = i;
g[x].pb(y);
d[y] += 1;
}
}
rep(i, m) {
int j = lower_bound(all(a), pii(b[i].se + 1, 0)) - begin(a);
if (j == n) {
continue;
} else {
int x = sa[j].se;
int y = n + i;
g[x].pb(y);
d[y] += 1;
}
}
queue<int> q;
rep(i, n + m) {
if (!d[i]) {
ans[i] = i < n;
q.emplace(i);
}
}
while (!q.empty()) {
int u = q.front();
q.pop();
for (auto v : g[u]) {
ans[v] = ans[u];
if (--d[v] == 0) {
q.emplace(v);
}
}
}
ans.resize(n);
cout << count(all(ans), 1) << " " << count(all(ans), -1) << " "
<< count(all(ans), 0) << "\n";
}
|
F.
假设 $x=0$，那么我们知道答案是 $k(2k+1)^{n-1}$。
可以让 $c_{i-1} = a_i - a_{i-1} \in [-k,k]$，那么我们只需确定 $c_{1…n-1}$ 就可以确定下来 $a_i$，再确定最小值 $t\in[0,k-1]$，就可以唯一确定一个序列 ${a}$。
现在 $x$ 不为 $0$，考虑容斥。
首先假设同样假设最小值为 $t \in [0, x+k-1]$，能算出来总方案数。
多算的部分就是所有的 $a_i \in [0, x)$，并且满足整个序列为非负整数的方案数。可以建立一个矩阵 $M$，$[M^{n-1}]{i,j}$ 就表示首为 $i$，尾为 $j$ 的方案数量。显然这部分是 $\sum{i,j} [M^{n-1}]_{i,j}$。
后者可以用矩阵快速幂，感觉难的部分在想到枚举最小值，然后容斥。
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
31
| void solve() {
int n, x, k;
cin >> n >> x >> k;
int ans = 1ll * (x + k) * power(2 * k + 1, n - 1) % P;
if (x == 0) {
cout << ans << "\n";
return;
}
vector<vector<int>> base(x, vi(x));
rep(i, x) {
rep(j, x) {
if (abs(i - j) <= k) {
base[i][j] = 1;
}
}
}
auto mat = power(base, n - 1);
rep(i, x) {
rep(j, x) {
ans += P - mat[i][j];
if (ans >= P) {
ans -= P;
}
}
}
cout << ans << "\n";
}
|
G.
wa53…
