Codeforces Round 1053 (Div. 1)

Codeforces Round 1053 (Div. 1)

Date 2025/09/25

A B C D E1 E2 F G
O O O Ø Ø

D - Attraction Theory

又是这个 trick,求 sum 不好求,转化为求 期望 乘上对应 概率。

让我们先做一些转化:

令 $f_i$ 表示 $i$ 这个位置上的人数

我们可以通过分析某个 attraction 放在不同位置时会发生什么,轻松得到以下必要条件:

  • 存在某个区间 $1 \le L \le R \le n$,使得当且仅当 $L \le i \le R$ 时 $f_i \ge 1$。
  • 对于所有满足 $L < i < R$ 的 $i$,都有 $f_i$ 是奇数。

进一步,这些条件也是充分的。一种简单的构造方式是:对于最终停在位置 $i$ 的那一组人,把 $\frac{f_i}{2}$ 个 attraction 放在该组人的中心位置(两端情况容易处理)。最后可能还需要做一些平移,这可以通过在位置 1 或 $n$ 上放 attraction 来完成。

现在假设 $L = 1, R = K (K > 1)$。我们有方程

$$
f_1 + f_2 + f_3 + \ldots + f_k = n
$$

并且 $f_i \ge 1$,且当 $i \ne 1, i \ne k$ 时 $f_i$ 是奇数。我们想要求的是所有情况的

$$
\sum f_i \cdot a_i
$$

固定 $f_1, f_k$ 的奇偶性,分别设为 $x, y$(其中 $1 \le x, y \le 2$),然后令:

  • 对于 $i \ne 1, i \ne k$,有 $f_i = 2 \cdot g_i + 1$;
  • $f_1 = 2 \cdot g_1 + x$;
  • $f_k = 2 \cdot g_k + y$。

$$
S = n - x - y - (k - 2)。
$$

那么方程变为

$$
\sum g_i = \frac{S}{2},
$$

若 $S$ 是奇数,则无解。那么 $S$ 是偶数。

我们可以把方程转化为

$$
\sum ways \cdot \mathbb{E}[f_i] \cdot a_i,
$$

其中 $ways$ 是解的个数,隔板法即可求出为

$$
ways = \binom{\frac{S}{2} + k - 1}{k - 1}
$$

由于 $g_i$ 对称,$\mathbb E[g_i]=\dfrac{S}{2k}$。中间位 $2\le i\le k-1$ 的期望 $ \mathbb E[f_i]=\dfrac{S}{k}+1$;两端 $i=1,k$ 的常数项由 $x,y$ 决定(为 1 或 2)。
目标是对所有有效 $[L,R]$(等价于所有长度为 $k$ 的区间、所有 $(x,y)$)累加 $\sum f_i\cdot a_{L+i-1}$。这可拆成:“中间位统一的期望系数” $(\dfrac{S}{k}+1)$ 乘上所有长度为 $k$ 的子数组的总和
两端若 $x=2$ 或 $y=2$ 的“多出来的 +1”各自乘上“所有长度为 $k$ 的子数组里左端/右端的元素总和”。

前缀和的前缀和一次性得到:
所有长度为 $k$ 的子数组和的总和;
所有长度为 $k$ 的左端元素之和、右端元素之和。

E1 - Hidden Single (Version 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
61
62
63
64
65
int ask(vector<int> S, int x) {
cout << "? " << x << " " << S.size() << ' ';
for (auto x : S) cout << x << ' ';
cout << endl;
return read();
}

vector<int> range(int l, int r) {
vector<int> res;
for (int i = l; i <= r; i++) {
res.eb(i);
}
return res;
}

int go(int l, int r, vector<int> vals, vector<int> waste) {
if (l == r) return vals.back();

int len = (r - l + 1) / 2;
int mid = l + len - 1;

vector<int> vl = range(l, mid);
vector<int> vr = range(mid + 1, r);

int siz = mid - l + 1;
vector<int> waste_l, waste_r;

for (auto x : waste) {
if (ask(vl, x)) {
waste_l.eb(x);
} else {
waste_r.eb(x);
}
}

vector<int> vals_l, vals_r;

for (auto x : vals) {
int r1 = ask(vl, x);
int r2 = ask(vr, x);

if (r1 and r2) {
waste_l.eb(x);
waste_r.eb(x);
} else if (r1 and !r2) {
vals_l.eb(x);
} else if (!r1 and r2) {
vals_r.eb(x);
}
}

siz -= waste_l.size();

if (siz & 1) {
return go(l, mid, vals_l, waste_l);
} else {
return go(mid + 1, r, vals_r, waste_r);
}
};

void solve() {
int n = read();
int ans = go(1, 2 * n - 1, range(1, n), {});
cout << "! " << ans << endl;
}

C - Limited Edition Shop

如果物品 $x$ 在 $A$ 里面的优先级高于 $y$,那么如果想只拿 $y$ 不拿 $x$,那么必须 $B$ 里面也是这个相对优先级顺序

因此可以令

$$
dp_{(i, j)} = \text{Alice 在前 } i \text{ 个物品中能够取得的最大总和,且 Bob 所选物品的 } pos_x \text{ 最大值为 } j
$$

转移方式:

  • 我们允许 Alice 拿物品 $i+1$ 当且仅当 $pos_i > j$。
  • Bob 可以无条件拿物品 $i+1$,此时 $j$ 更新为 $\max(j, pos_{i+1})$。

然后我们用线段树来优化存储状态 $j$。第一类转移对应一个区间加法操作,第二类转移可以拆分为 $j < pos_{i+1}$ 和 $j > pos_{i+1}$ 两种情况:前者不需要操作,后者需要做区间最大值查询。

所有这些操作都可以用懒标记线段树处理。时间复杂度是 $O(n \cdot \log 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
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
template<class Info, class Tag>
struct LazySegmentTree {
int n;
std::vector<Info> info;
std::vector<Tag> tag;
LazySegmentTree() : n(0) {}
LazySegmentTree(int n_, Info v_ = Info()) {
init(n_, v_);
}
template<class T>
LazySegmentTree(std::vector<T> init_) {
init(init_);
}
void init(int n_, Info v_ = Info()) {
init(std::vector(n_, v_));
}
template<class T>
void init(std::vector<T> init_) {
n = init_.size();
info.assign(4 << std::__lg(n), Info());
tag.assign(4 << std::__lg(n), Tag());
std::function<void(int, int, int)> build = [&](int p, int l, int r) {
if (r - l == 1) {
info[p] = init_[l];
return;
}
int m = (l + r) / 2;
build(2 * p, l, m);
build(2 * p + 1, m, r);
pull(p);
};
build(1, 0, n);
}
void pull(int p) {
info[p] = info[2 * p] + info[2 * p + 1];
}
void apply(int p, const Tag &v) {
info[p].apply(v);
tag[p].apply(v);
}
void push(int p) {
apply(2 * p, tag[p]);
apply(2 * p + 1, tag[p]);
tag[p] = Tag();
}
void modify(int p, int l, int r, int x, const Info &v) {
if (r - l == 1) {
info[p] = v;
return;
}
int m = (l + r) / 2;
push(p);
if (x < m) {
modify(2 * p, l, m, x, v);
} else {
modify(2 * p + 1, m, r, x, v);
}
pull(p);
}
void modify(int p, const Info &v) {
modify(1, 0, n, p, v);
}
Info rangeQuery(int p, int l, int r, int x, int y) {
if (l >= y || r <= x) {
return Info();
}
if (l >= x && r <= y) {
return info[p];
}
int m = (l + r) / 2;
push(p);
return rangeQuery(2 * p, l, m, x, y) + rangeQuery(2 * p + 1, m, r, x, y);
}
Info rangeQuery(int l, int r) {
return rangeQuery(1, 0, n, l, r);
}
void rangeApply(int p, int l, int r, int x, int y, const Tag &v) {
if (l >= y || r <= x) {
return;
}
if (l >= x && r <= y) {
apply(p, v);
return;
}
int m = (l + r) / 2;
push(p);
rangeApply(2 * p, l, m, x, y, v);
rangeApply(2 * p + 1, m, r, x, y, v);
pull(p);
}
void rangeApply(int l, int r, const Tag &v) {
return rangeApply(1, 0, n, l, r, v);
}
void half(int p, int l, int r) {
if (info[p].act == 0) {
return;
}
if ((info[p].min + 1) / 2 == (info[p].max + 1) / 2) {
apply(p, {-(info[p].min + 1) / 2});
return;
}
int m = (l + r) / 2;
push(p);
half(2 * p, l, m);
half(2 * p + 1, m, r);
pull(p);
}
void half() {
half(1, 0, n);
}

template<class F>
int findFirst(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findFirst(2 * p, l, m, x, y, pred);
if (res == -1) {
res = findFirst(2 * p + 1, m, r, x, y, pred);
}
return res;
}
template<class F>
int findFirst(int l, int r, F &&pred) {
return findFirst(1, 0, n, l, r, pred);
}
template<class F>
int findLast(int p, int l, int r, int x, int y, F &&pred) {
if (l >= y || r <= x) {
return -1;
}
if (l >= x && r <= y && !pred(info[p])) {
return -1;
}
if (r - l == 1) {
return l;
}
int m = (l + r) / 2;
push(p);
int res = findLast(2 * p + 1, m, r, x, y, pred);
if (res == -1) {
res = findLast(2 * p, l, m, x, y, pred);
}
return res;
}
template<class F>
int findLast(int l, int r, F &&pred) {
return findLast(1, 0, n, l, r, pred);
}

void maintainL(int p, int l, int r, int pre) {
if (info[p].difl > 0 && info[p].maxlowl < pre) {
return;
}
if (r - l == 1) {
info[p].max = info[p].maxlowl;
info[p].maxl = info[p].maxr = l;
info[p].maxlowl = info[p].maxlowr = -inf;
return;
}
int m = (l + r) / 2;
push(p);
maintainL(2 * p, l, m, pre);
pre = std::max(pre, info[2 * p].max);
maintainL(2 * p + 1, m, r, pre);
pull(p);
}
void maintainL() {
maintainL(1, 0, n, -1);
}
void maintainR(int p, int l, int r, int suf) {
if (info[p].difr > 0 && info[p].maxlowr < suf) {
return;
}
if (r - l == 1) {
info[p].max = info[p].maxlowl;
info[p].maxl = info[p].maxr = l;
info[p].maxlowl = info[p].maxlowr = -inf;
return;
}
int m = (l + r) / 2;
push(p);
maintainR(2 * p + 1, m, r, suf);
suf = std::max(suf, info[2 * p + 1].max);
maintainR(2 * p, l, m, suf);
pull(p);
}
void maintainR() {
maintainR(1, 0, n, -1);
}
};

struct Tag {
int x = 0;
void apply(const Tag &t) & {
x += t.x;
}
};

struct Info {
int x = -inf;
void apply(const Tag &t) & {
x += t.x;
}
};

Info operator+(const Info &a, const Info &b) {
return {std::max(a.x, b.x)};
}


void solve() {
int n = read();

vector<int> v(n);
for (auto &x : v) x = read();

vector<int> a(n), rka(n);
for (int i = 0; i < n; i++) {
int x = read() - 1;
a[i] = x, rka[x] = i;
}

vector<int> b(n), rkb(n);
for (int i = 0; i < n; i++) {
int x = read() - 1;
b[i] = x, rkb[x] = i;
}

LazySegmentTree<Info, Tag> seg(n + 1);
seg.modify(0, {0});

for (int i = 0; i < n; i++) {
int x = rkb[a[i]];

auto t = seg.rangeQuery(0, x + 1);
seg.modify(x + 1, t);

seg.rangeApply(0, x + 1, {v[a[i]]});
}

auto [ans] = seg.rangeQuery(0, n + 1);
cout << ans << '\n';
}

B - Grid Counting

翻译一下会发现限制很简单,dp 一下即可

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() {
int n = read();

vector<int> a(n);
for (auto &x : a) x = read();

Z ans = 1;

int len = -n;
for (int i = n - 1; i >= 0; i--) {
len += 2;
if (len <= 0) {
if (a[i]) {
cout << "0\n";
return;
}
} else {
ans *= comb.binom(len, a[i]);
}
len -= a[i];
}

if (len != 0) ans = 0;
cout << ans << '\n';
}

A - Incremental Path

直接模拟

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
void solve() {
int n = read(), m = read();

string s; cin >> s;
vector<int> a(m);
for (auto &x : a) x = read();

auto b = a;

int i = 0, x = 1;
for (auto c : s) {
if (c == 'A') {
x++;
b.eb(x);
} else {
while (i < m and a[i] <= x) {
i++;
}

x++;

while (i < m and a[i] == x) {
x++;
i++;
}
b.eb(x);

x++;
while (i < m and a[i] == x) {
x++;
i++;
}
}
}

ranges::sort(b);
b.erase(unique(b.begin(), b.end()), b.end());
cout << b.size() << '\n';
for (auto x : b) {
cout << x << " \n"[x == b.back()];
}
}
Author

TosakaUCW

Posted on

2025-09-28

Updated on

2025-09-28

Licensed under

Comments