周日偶遇神秘小王赛。
比赛链接
A.
Easy-
简单模拟。
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, k;
cin >> n >> k;
int sum = 0;
for (int i = 0; i < n; i++) {
string s;
cin >> s;
if (s == "yin")
sum += 2;
else if (s == "tong")
sum += 1;
}
if (sum >= k)
cout << "NB!!!\n";
else if (sum == 0)
cout << "wo bu da XCPC le...\n";
else
cout << "T_T\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
B.
Easy
问在区间 $[L,R]$ 内有多少个数字 $x$ 满足二进制下每一位右侧的 $1$ 的个数与其自身的位数相等。
显然有且仅有满足 $x=2^n-1$ 才能成立。提前计算好所有的 $x$ 再查找即可。
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
|
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
vector<int> vec;
void solve() {
int l, r;
cin >> l >> r;
auto ll = lower_bound(vec.begin(), vec.end(), l);
auto rr = upper_bound(vec.begin(), vec.end(), r);
cout << (rr - ll) << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
vec.reserve(63);
for (int i = 1; i <= 63; i++) {
vec.emplace_back((1ULL << i) - 1);
}
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
C.
Easy
给定一个字符串，遇到 cf 加能量，遇到 zy 减能量（这里指序列），问能量最小值。
简单模拟一下，计算序列个数即可。
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
string s;
cin >> s;
int cc = 0, zc = 0;
int e = 0;
int me = 0;
for (char ch : s) {
if (ch == 'c')
cc++;
if (ch == 'f')
e += cc;
if (ch == 'z')
zc++;
if (ch == 'y')
e -= zc;
me = min(me, e);
}
if (me >= 0)
cout << "YES\n";
else
cout << "NO\n" << -me << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
I.
Mid
在完全图 $G$ 中选择一些边，使得任意 3 个顶点所张成的三角形里至少有 2 条边被选中。
我们可以反过来思考，对于我们图 $G$ 的补图 $\bar{G}$，不存在两个相交的边，即 $\bar{G}$ 的一种匹配。
我们考虑如何计算，首先我们假设我们已经提前计算好了 $x$ 个数的情形的方案数，记做 $f(x)$。当我们选择 $x+1$ 个数的时候，显然我们只有两种选择：
- 不把 $x+1$ 接入到之前的节点；
- 把 $x+1$ 接入到之前的节点。
对于第一种方案，方案数是 $f(x)$，而对于第二种方案，方案数是 $x\times f(x-1)$
根据此关系式递推即可。
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
|
#include <bits/stdc++.h>
using namespace std;
constexpr int maxn = 1e7;
constexpr int modn = 1e9 + 7;
int f[maxn + 10];
void solve() {
int n;
cin >> n;
cout << f[n] << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
f[0] = 1, f[1] = 1;
for (long long i = 2; i <= maxn; i++) {
f[i] = (f[i - 1] + (i - 1ll) * f[i - 2]) % modn;
}
while (T--) {
solve();
}
return 0;
}
|
F.
Mid
给定 $m, t’, P$ 三个整数和 $m$ 个 $t_i,p_i,id_i$ 诸元，在满足：
- $\sum t_i\le t'$
- $\sum p_i\ge P$
- $id_i$ 两两不等
的选择中，最大战斗力的最小值。
根据 $\mathbf{Lengling}$ 的说法：求最大的最小一般来说是二分，然后我们就可以开始思考 check 函数怎么写。
因为 $id$ 在选择中是唯一的，因此我们要做的就是在 $t’$ 的约束下最大化我们所选的 $\sum p_i$。
考虑最优化问题，使用一个分组背包可以解决。
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
using i3 = array<int, 3>;
constexpr int inf = 1e18;
void solve() {
int m, t, p;
cin >> m >> t >> p;
vector<i3> a(m);
vector<int> ans;
ans.reserve(m);
for (auto &[ti, pi, idi] : a) {
cin >> ti >> pi >> idi;
ans.emplace_back(pi);
}
sort(ans.begin(), ans.end());
ans.erase(unique(ans.begin(), ans.end()), ans.end());
auto check = [&](int x) {
unordered_map<int, vector<pair<int, int>>> grp;
grp.reserve(m);
for (auto [ti, pi, idi] : a) {
if (pi <= x)
grp[idi].emplace_back(ti, pi);
}
vector<int> dp(t + 1, -inf);
dp[0] = 0;
for (auto &[k, v] : grp) {
auto ddp = dp;
for (auto [ti, pi] : v) {
for (int w = t; w >= ti; w--) {
dp[w] = max(dp[w], ddp[w - ti] + pi);
}
}
}
int mx = 0;
for (int i = 0; i <= t; i++)
mx = max(mx, dp[i]);
return mx >= p;
};
int lo = 0, hi = ans.size() - 1, res = -1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
if (check(ans[mid])) {
res = mid;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
if (res < 0)
cout << "-1\n";
else
cout << ans[res] << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
H.
Mid
给定长度为 $n$ 的序列 $a$ 和 $q$ 个约束 $l,r,x$，构造一个序列 $a$ 使得 $a_i,(i\in [l,r])$ 的异或和为 $x$。
首先不难想到求区间的异或和可以用前缀异或和优化，然后我们可以建立一个无向图，节点是每一个下标，边是每条约束。
然后我们在图上做 BFS，对于每一个未访问的节点 $i$，令 pre[i]=0，然后入队，对于每一个队列中的节点 $u$，遍历其每一条边 $(u,v,w)$，若 $v$ 尚未访问，则 pre[v]=pre[u]^w ；若 $v$ 已经访问，则检查 pre[u]^pre[v]==w 即可。
最后第 $i$ 位的结果是 pre[i]^pre[i-1]。
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, q;
cin >> n >> q;
auto adj = vector(n + 1, vector<pair<int, int>>{});
for (int i = 0; i < q; i++) {
int l, r, x;
cin >> l >> r >> x;
l--;
adj[l].emplace_back(r, x);
adj[r].emplace_back(l, x);
}
vector<bool> vis(n + 1);
vector<int> pre(n + 1);
auto bfs = [&](int i) {
queue<int> q;
pre[i] = 0;
vis[i] = true;
q.push(i);
while (not q.empty()) {
int u = q.front();
q.pop();
for (auto [v, w] : adj[u]) {
if (vis[v]) {
if ((pre[u] ^ pre[v]) != w) {
cout << "-1\n";
return false;
}
continue;
}
pre[v] = pre[u] ^ w;
vis[v] = true;
q.push(v);
}
}
return true;
};
for (int i = 0; i <= n; i++) {
if (not vis[i]) {
if (not bfs(i))
return;
}
}
for (int i = 1; i <= n; i++) {
cout << (pre[i] ^ pre[i - 1]) << " \n"[i == n];
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
D & E.
Mid
给定 $n$ 个商品，第 $i$ 个商品价格为 $p_i$ 元，同时购买第 $i$ 件商品会获得 $k_i$ 张面额为 $w$ 元的优惠券。购买顺序必须严格按照输入顺序进行，求最少总花费。
我们先对每件商品做以下预处理：计算整额槽数
$$
f_i = \left\lfloor \frac{p_i}{w} \right\rfloor
$$
和零头
$$
r_i = p_i \bmod w.
$$
直观上，第 $i$ 件商品最多能完整使用 $f_i$ 张券，每张抵扣 $w$ 元，第 $f_i+1$ 张券能抵扣剩余的 $r_i$ 元，第 $f_i+2$ 张及以后则没有额外收益。
由于优惠券只能用在后续商品上，我们将问题转化为：有一批“券”从前往后发出，每张券需要匹配到某个后面商品的“槽”上，以最大化总抵扣。更晚时刻发出的券可选的槽更多。
我们从后往前逆序处理，维护两个数据结构：
- 一个计数器
c nt，记录当前可用的整额槽总数；
- 一个最大堆
pq，存放所有可用的零头值 $r_j$。
对于每个位置 $i$（从 $n$ 到 $1$）：
- 将第 $i+1$ 件商品产生的 $f_{i+1}$ 个整额槽累加到
full，若 $r_{i+1}>0$ 则将 $r_{i+1}$ 入堆；
- 处理第 $i$ 次手上的 $k_i$ 张券：
- 先用 $\min(k_i,\text{cnt})$ 张券在整额槽上，每张抵扣 $w$ 元；
- 剩余的券一张张从
pq 中取出当前最大的 $r$，每次抵扣该 $r$ 元，直到用完券或堆空。
所有步骤累计的总抵扣即为最大收益，总花费为
$$
\sum_{i=1}^n p_i - \text{总抵扣}.
$$
在 easy 版中有额外简化：$k_i \equiv 1$，每步只需处理一张券，用或不用整额槽，或弹出堆顶零头即可，逻辑更简单；在 hard 版中 $k_i$ 可任意，额外多张券的处理也按上述两步顺序执行，总体仍是 $O(n\log n)$，可应对 $\sum n \le 2.5\times10^5$ 的规模。
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
int n, w;
cin >> n >> w;
vector<int> p(n + 2);
for (int i = 1; i <= n; i++) {
cin >> p[i];
}
vector<int> k(n + 2);
for (int i = 1; i <= n; i++) {
cin >> k[i];
}
vector<int> f(n + 2), r(n + 2);
int sum = 0;
for (int i = 1; i <= n; i++) {
sum += p[i];
f[i] = p[i] / w;
r[i] = p[i] % w;
}
int cnt = 0, ans = 0;
priority_queue<int> pq;
for (int i = n; i >= 1; i--) {
if (i < n) {
cnt += f[i + 1];
if (r[i + 1] > 0)
pq.push(r[i + 1]);
}
int mc = min(k[i], cnt);
ans += mc * w;
cnt -= mc;
int t = k[i] - mc;
while (t > 0 and not pq.empty()) {
ans += pq.top();
pq.pop();
t--;
}
}
cout << sum - ans << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
J.
Mid
给定 $n$ 和 $k$ 以及排练 $p={1,2,3,…,n}$，求所有长度为 $k$ 的连续子序列的异或和的异或和。
其实本题可以不用考虑那么多，我们只需要考虑对于每一个数 $x$ 被多少个子序列覆盖即可，若覆盖数为偶数，则此数对答案没有贡献，若覆盖数为奇数，则计算答案。
然后我们考虑该排列中有三段，令 $m=n-k+1,h=\min(k,m)$：
- 左段：$[1,h-1]$
- 中段：$[h,n-h+1]$
- 右段：$[n-h+2,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
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
// 计算从 1..x 的异或和
constexpr auto px(int x) {
const int d = x % 4;
if (d == 0) {
return x;
} else if (d == 1) {
return 1ll;
} else if (d == 2) {
return x + 1;
} else {
return 0ll;
}
};
// 计算区间异或和
constexpr auto xr(int l, int r) {
if (l > r)
return 0ll;
return px(r) ^ px(l - 1);
};
// 计算区间内偶数的异或和
constexpr auto ex(int x) { return px(x >> 1) << 1; }
// 计算区间内奇数的异或和
constexpr auto ox(int x) { return px(x) ^ ex(x); }
void solve() {
int n, k;
cin >> n >> k;
int m = n - k + 1;
int ans = 0;
ans ^= ox(min(m, k - 1));
if (m + 1 <= k - 1 and (m & 1)) {
ans ^= xr(m + 1, k - 1);
}
if (k <= m and (k & 1)) {
ans ^= xr(k, m);
}
int x = max(k, m + 1);
if (x <= n) {
if (n % 2) {
ans ^= (ox(n) ^ ox(x - 1));
} else {
ans ^= (ex(n) ^ ex(x - 1));
}
}
cout << ans << "\n";
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
cin >> T;
while (T--) {
solve();
}
return 0;
}
|
L.
Hard?
给定长度为 $n$ 的数组 $a$ 和 $m$ 个操作 $\text{opt}\in{1,2}$，对于 $\text{opt}=1$，给定 $x,k$，将 $a_x\leftarrow k$；对于 $\text{opt}=2$，给定 $L, R, y$，求：
$$
\sum_{i=L,L+y,L+2y,...}^{R}a_i
$$
我们可以使用分块思想：将 $a$ 分成 $\sqrt{n}$ 个块，在每个块内维护公差为 $d$ 的前缀和，使用时查询即可。
可能需要注意一些细节部分。
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
|
#include <bits/stdc++.h>
using namespace std;
#define int long long
constexpr int maxn = 2e5;
constexpr int modn = (1LL << 31);
int a[maxn + 10];
void solve() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
int last = 0;
int sn = sqrt(n);
auto pre = vector(sn + 1, vector<int>(n + 2));
for (int i = 1; i <= sn; i++) {
for (int j = n; j >= 1; j--) {
if (i + j <= n)
pre[i][j] = a[j] + pre[i][i + j];
else
pre[i][j] = a[j];
}
}
while (m--) {
int opt;
cin >> opt;
if (opt == 2) {
int L, R, y;
cin >> L >> R >> y;
L ^= last, R ^= last, y ^= last;
int ans = 0;
if (y <= sn) {
ans = pre[y][L];
int nxt = L + y * ((R - L) / y + 1);
if (nxt <= n)
ans -= pre[y][nxt];
} else {
for (int i = L; i <= R; i += y)
ans += a[i];
}
cout << ans << "\n";
last = ans % modn;
}
}
}
signed main() {
cin.tie(nullptr)->sync_with_stdio(false);
int T = 1;
while (T--) {
solve();
}
return 0;
}
|