这场也没打，但是C比较恶心，VP的时候没开出来，D很简单，E是火箭毛毛虫，需要一些ds功底，整体确实很Edu。
C
题目大意：给定一个 $m$ ，问是否能构造 $a_1,\ldots,a_n$ ，且每个 $a_i$ 都是 $m$ 子集，且 $\sum\limits_{i=1}^{n}a_i=s$ ，若能则求 $n$ 的最小值。
数据范围： $1 \leq s,m \leq 10^18$
思路：这个数据范围显然一眼二分，而且答案确实有单调性。
但是问题是，check函数怎么写？
很自然的思路是从高位向低位贪心，然后每次最多减掉 $mid$ 个当前位，证明思路是如果当前位少减了，那么后面的位需要堆更多才能做到，因此是不划算的。
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
|
void solve() {
ll s, m;
cin >> s >> m;
ll ans = -1;
ll l = 1, r = s, mid;
auto check = [&](this auto&& check, ll mid) -> bool {
ll tem = s;
frep(i, 60, 0) {
if ((m >> i) & 1) {
tem -= 1LL * (min(tem >> i, mid) << i);
}
}
return tem == 0;
};
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
r = mid - 1;
ans = mid;
} else
l = mid + 1;
}
cout << ans << endl;
return;
}
|
D
题目大意：Alice和Bob正在玩一个游戏，给定一个 $n$ 个元素组成的数组 $a$ 和 $m$ 个元素组成的数组 $b$ 。
他们轮流进行游戏，Alice先下，轮到自己时，需要从 $a$ 中选择一个数字 $x$ ，从 $b$ 中选择一个数字 $y$ ，他们选择的规则不一样。
Alice选择 $x,y,x \mid y$ ，Bob选择 $x,y, x \nmid y$ ，随后删除 $y$ ，不删除 $x$ ，若谁无法下棋了，就输掉。
请判断，最后谁会赢？
数据范围： $1 \leq n,m \leq 10^6, 1 \leq a_i,b_i \leq n+m, 1 \leq sum(n) \leq 10^6,1 \leq sum(m) \leq 10^6$
思路：显然可以将 $b$ 中的数分为两部分，一部分是可以被所有 $a$ 整除的，一部分是可以被一部分 $a$ 整除的，一部分是完全无法被 $a$ 整除的，显然双方都在争抢中间那部分。
接着，就可以对 $a$ 去重，并且使用调和级数做一下就可以。
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
|
void solve() {
int n, m;
cin >> n >> m;
vi a(n);
vi b(m);
rep(i, 0, n - 1) cin >> a[i];
rep(i, 0, m - 1) cin >> b[i];
ranges::sort(a);
a.erase(unique(all(a)), a.end());
vi res(n + m + 1);
rep(i, 0, sz(a) - 1) {
for (int j = a[i]; j <= n + m; j += a[i]) {
res[j]++;
}
}
int cnt1 = 0, cnt2 = 0, cnt3 = 0;
rep(i, 0, m - 1) {
if (res[b[i]] == 0)
cnt1++;
else if (res[b[i]] > 0 && res[b[i]] < sz(a))
cnt2++;
else if (res[b[i]] == sz(a))
cnt3++;
}
if (cnt2 % 2 == 0) {
if (cnt3 > cnt1)
cout << "Alice" << endl;
else
cout << "Bob" << endl;
} else {
if (cnt3 >= cnt1)
cout << "Alice" << endl;
else
cout << "Bob" << endl;
}
return;
}
|
E
题目大意：Alice和Bob在玩一副扑克牌，最初是空的，他们玩了 $m$ 轮，每轮的规则如下：
一张值为 $a_i$ 的牌被添加进牌组（保证之前没有为 $a_i$ 的），如果牌组中的牌少于3，则游戏结束。
否则，Alice从牌组中选择一张牌，Bob在知道Alice选了哪张牌的情况下选一张牌（不能选择同一张牌），再从剩下的牌中均匀随机选择一张牌，最终三张牌都放回牌组。
假设 $a$ 是Alice选出的牌， $b$ 是Bob选出的牌， $c$ 是随机抽出的牌，那么 Bob会收到以下规则的积分：
若 $|a-c| \leq |b-c|$ ，或者 $a < c < b $ 或者 $b < c < a$ ，则收到零分。
否则收到 $|b-c|$ 分。
Alice每轮的目标都是最小化Bob的期望得分，Bob是最大化期望得分，在最佳策略下，Bob每轮的期望得分是多少？如果是分数请乘 $998244353$ 的逆元。
数据范围： $3 \leq m \leq 2 \cdot 10^5, 1 \leq a_i \leq 10^12$ 。
思路：显然的是，如果每轮都按递增顺序排列，Bob需要把牌取到Alice每次取的两侧来保证自己的期望最大。
也就是说，需要维护一个数据结构，保证它是递增的，同时要动态维护它的前缀和，想到动态我们通常会想到树状数组。
但是递增很难办啊，必须维护一个treap吗？有点麻烦了，其实在cf只要玩会树状数组和线段树就很强了，说明完全没有必要。
考虑某个元素的贡献，只需要计算比它小的元素的数量和前缀总和即可，那么完全可以考虑权值树状数组，并对原数组做一个离散化。
接着考虑Alice，显然每次查找是 $O(n)$ 的，非常慢，那么从贪心的角度考虑，贡献最小的地方一定是 前缀贡献 $\leq $ 后缀贡献的最后一个地方，或者 后缀贡献 $>$ 前缀贡献的第一个地方，而这两个函数都是单调的，因此可以使用二分查找出这个交点。
同时，每次离散化后的权值树状数组中，查找某个下标在离散化后数组的排名，根据树状数组二分，是 $O(\log n)$ 的，总体时间复杂度为 $O(n \log^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
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
|
template <typename T = long long>
class Tree {
vector<T> tree;
public:
// 构造函数：初始化大小为 n 的树状数组，初始所有元素值为 val（外部表现为 0-based）
Tree(int n, T val = 0) : tree(n + 1) {
for (int i = 1; i <= n; i++) {
tree[i] += val;
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 构造函数：使用给定的 vector 在 O(N) 时间内快速初始化建树
Tree(const vector<T>& data) {
int n = data.size();
tree.resize(n + 1);
for (int i = 1; i <= n; i++) {
tree[i] += data[i - 1]; // data是 0-based
int nxt = i + (i & -i);
if (nxt <= n) {
tree[nxt] += tree[i];
}
}
}
// 单点修改：将 0-based 下标 i 处的元素增加 val
void add(int i, T val = 1) {
for (++i; i < tree.size(); i += i & (-i)) {
tree[i] += val;
}
}
// 前缀求和：计算 0-based 下标区间 [0, i] 内的所有元素之和
T pre(int i) const {
T res = 0;
for (++i; i > 0; i &= i - 1) {
res += tree[i];
}
return res;
}
// 区间求和：计算 0-based 下标区间 [l, r] 内的所有元素之和
T query(int l, int r) const {
if (r < l) {
return 0;
}
return pre(r) - pre(l - 1); // 当 l=0 时, pre(-1) 会合理地返回 0
}
// 树上二分查找：返回满足前缀和 >= val 的最小 0-based 下标
int lower_bound(T val) const {
int w = bit_width(tree.size() - 1);
int res = 0;
T s = 0;
for (int i = w - 1; i >= 0; i--) {
int nxt = res + (1 << i);
if (nxt < tree.size() && tree[nxt] + s < val) {
res += (1 << i);
s += tree[nxt];
}
}
return res; // 返回 0-based 下标：内部 1-based 下标为 res + 1，因此 0-based 为 res
}
};
constexpr int MOD = 998244353;
int mul(int x, int y) { return x * 1LL * y % MOD; }
int qpow(int x, int y) {
int z = 1;
while (y > 0) {
if (y & 1) z = mul(z, x);
x = mul(x, x);
y >>= 1;
}
return z;
} // 求x**y%MOD
void solve() {
int n;
cin >> n;
vl a(n);
rep(i, 0, n - 1) cin >> a[i];
auto sorted = a;
ranges::sort(sorted);
sorted.erase(unique(all(sorted)), sorted.end());
int m = sz(sorted);
Tree cnt(m);
Tree fen(m);
rep(i, 0, n - 1) {
auto x = ranges::lower_bound(sorted, a[i]);
int tem = x - sorted.begin();
cnt.add(tem, 1);
fen.add(tem, a[i]);
if (i < 2) continue;
int l = 2, r = i, mid, ans;
auto calc = [&](int mid) -> pll {
int c = cnt.lower_bound(mid);
ll left_cost = 0, right_cost = 0;
int c1 = cnt.lower_bound(mid - 1);
int c2 = cnt.lower_bound(mid + 1);
if (c1 > 0) {
ll left_cnt = cnt.query(0, c1 - 1);
ll left_sum = fen.query(0, c1 - 1);
left_cost = left_cnt * sorted[c1] - left_sum;
}
if (c2 < m - 1) {
ll right_cnt = cnt.query(c2 + 1, m - 1);
ll right_sum = fen.query(c2 + 1, m - 1);
right_cost = right_sum - right_cnt * sorted[c2];
}
return {left_cost, right_cost};
};
auto check = [&](int mid) -> bool {
auto [a1, b1] = calc(mid);
return a1 <= b1;
};
while (l <= r) {
mid = (l + r) / 2;
if (check(mid)) {
ans = mid;
l = mid + 1;
} else
r = mid - 1;
}
auto [l1, r1] = calc(max(1, ans));
auto [l2, r2] = calc(min(ans + 1, i + 1));
ll res = min(max(l1, r1), max(l2, r2));
cout << res % MOD * qpow(i - 1, MOD - 2) % MOD << endl;
}
cout << endl;
return;
}
|
