2025 YAC Round 8 题解

比赛大图来源:pixiv_id=70066287

A 歳月-雲流れ-

出题人:MarisaMagic

题意简述

给定一个长度为 nn0101 序列,求一个长度最小的连续区间 [l,r][l, r] 包含所有的 11

解题思路 (模拟)

去除开头和结尾连续的 00 得到的子区间即包含所有 11 的长度最小的连续区间。时间复杂度 O(n)\mathcal{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
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)

void marisa(){
int n; cin >> n;
vector<int> a(n + 1);
for(int i = 1; i <= n; i ++ ) cin >> a[i];
int l = 1;
while(l <= n && !a[l]) l ++ ;
int r = n;
while(r >= l && !a[r]) r -- ;
cout << r - l + 1 << "\n";
}

int main(){
fastio;

int T = 1; // cin >> T;
while(T -- ) marisa();

return 0;
}

B 饼干的搬运工

出题人:MarisaMagic

题意简述

给定数字 nnmm,第一次最多可以减去 mm,第二次最多可以减去 x1=m2x_1 = \left \lceil \frac{m}{2} \right \rceil,第三次最多可以减去 x2=x12x_2 = \left \lceil \frac{x_1}{2} \right \rceil,依次类推。求最少需要多少次使得 nn 减为 00

解题思路 (模拟)

可以发现 mm 经过 log2m\log_2 m 级别次数操作后会变为 11,且之后一直都是 11。故可以先暴力模拟直至 mm 变为 11,或者在 mm 变为 11 之前 nn 即可减为 00。最后 nn 若还有剩余,答案加上 nn 即可。时间复杂度 O(logm)\mathcal{O}(\log m)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)

void marisa(){
int n, m; cin >> n >> m;
int ans = 0;
while(n > 0 && m != 1){
n -= m;
ans ++ ;
m = (m + 1) / 2;
}
cout << ans + (n <= 0 ? 0 : n) << "\n";
}

int main(){
fastio;

int T = 1; // cin >> T;
while(T -- ) marisa();

return 0;
}

C 舒芙蕾还是巴斯克

出题人:MarisaMagic

题意简述

给定数字 aabb,每次进行如下两种操作之一:

  1. 花费 xx 代价,使得 aa 减去 22 或者 bb 减去 22。(前提 aa 至少为 22bb 至少为 22);
  2. 花费 yy 代价,使得 aa 减去 11 并且 bb 减去 11。(前提 aa 至少为 11bb 至少为 11)。

求使得 aa bb 减为 00 所需的最少次数。

解题思路 (数学)

  • x>2×yx > 2 \times y。显然一个一个减去所需的次数更少,此时对 aabb 中的较小值一个一个减去即可。故此时答案为 min(a,b)×y\min (a, b) \times y

  • x2×yx \le 2 \times y。显然两个两个减去的效率更高,此时考虑先将 aabb 其中一个值优先两个两个减,最后可能还余 11。故此时答案为 min(a2×x+amod2×y,b2×x+bmod2×y)\min(\left \lfloor \frac{a}{2} \right \rfloor \times x + a \bmod 2 \times y, \left \lfloor \frac{b}{2} \right \rfloor \times x + b \bmod 2 \times y)

    由于可能 x>yx > ya,ba, b 分别所需的操作次数相同,所以并不是 aabb 哪个更小就对哪个进行操作,故最后需要取一下最小值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)
using ll = long long;

void marisa(){
ll a, b, x, y; cin >> a >> b >> x >> y;
if(x > 2 * y){
cout << min(a, b) * y << "\n";
return;
}
cout << min(a / 2 * x + (a % 2) * y, b / 2 * x + (b % 2) * y) << "\n";
}

int main(){
fastio;

int T = 1; cin >> T;
while(T -- ) marisa();

return 0;
}

D THO 地铁 1 号线

出题人:MarisaMagic

题意简述

有一个长度为 nn 的环形数组 aa,找到一个长度不超过 nn 的非空子数组使得子数组总和最大。

解题思路 1 (DP,最大最小子数组和)

  • 考虑不跨环的情况。直接 DP 求数组 aa 的最大子数组和即可。
  • 考虑跨环的情况。相当于用整个数组的和减去一个子数组的和,故此时可以先 DP 求数组 aa 的最小子数组和,然后再用整个数组 aa 的和减去这个最小子数组和。

最终答案为两种情况的较大值。特别的,如果数组 aa 的元素均为负数,由于要找的子数组非空,不满足上述跨环的情况,故此时答案为 aa 的最大子数组和。时间复杂度 O(n)\mathcal{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
31
32
33
34
35
36
37
38
39
40
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)
using ll = long long;

void marisa(){
int n; cin >> n;
vector<int> a(n + 1);
bool all_minus = true;
for(int i = 1; i <= n; i ++ ){
cin >> a[i];
if(a[i] >= 0) all_minus = false;
}
ll sum = 0;
ll mx = -1e18; // 选择中间一段最大子数组和
for(int i = 1; i <= n; i ++ ){
sum = max(0ll, sum) + a[i];
mx = max(mx, sum);
}
sum = 0;
ll mn = 1e18; // 整个数组减去中间一段最小子数组和
for(int i = 1; i <= n; i ++ ){
sum = min(0ll, sum) + a[i];
mn = min(mn, sum);
}
sum = 0;
for(int i = 1; i <= n; i ++ ) sum += a[i];
if(!all_minus) cout << max(mx, sum - mn) << "\n";
else cout << mx << "\n";
}

int main(){
fastio;

int T = 1; // cin >> T;
while(T -- ) marisa();

return 0;
}

解题思路 2 (前缀和,单调队列)

复制一遍数组 aa,预处理前缀和 ss。对于每个位置 ii,最优的答案为 simaxmax(0,in)j<isjs_i - \max_{\max(0, i - n) \le j < i} s_{j}

可以用单调队列维护前面位置最小前缀和的下标,对于每个位置 ii 更新答案。注意开始时需要放入初始状态 00。时间复杂度 O(n)\mathcal{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
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)
using ll = long long;

void marisa(){
int n; cin >> n;
vector<int> a(2 * n + 1);
for(int i = 1; i <= n; i ++ ){
cin >> a[i];
a[n + i] = a[i];
}
using pii = pair<int, ll>;
ll mx = -1e18, sum = 0;
deque<pii> q;
q.emplace_back(0, 0); // 加入初始状态
for(int i = 1; i <= 2 * n; i ++ ){
sum += a[i]; // 记录前缀和
while(q.size() && i - q.front().first > n){
q.pop_front(); // 长度超过n
}
mx = max(mx, sum - q.front().second); // 减去前面最小的前缀和
while(q.size() && q.back().second > sum){
q.pop_back(); // 比当前sum更大,不会作为后续答案
}
q.emplace_back(i, sum);
}
cout << mx << "\n";
}

int main(){
fastio;

int T = 1; // cin >> T;
while(T -- ) marisa();

return 0;
}

E 豪德寺三花的祝福

出题人:MarisaMagic

题意简述

给定一个数组 a1,a2,,ana_1, a_2, \ldots, a_n,求有多少个不同的区间 1lrn1 \le l \le r \le n 满足 i=lraix\sum_{i=l}^{r} a_i \ge x

解题思路 (离散化,树状数组)

一个区间 [l,r][l, r] 满足 i=lraix\sum_{i=l}^{r} a_i \ge x 即前缀和 srsl1xs_r - s_{l - 1} \ge x,相当于 sl1srxs_{l-1} \le s_r - x

对于每个位置 ii,需要求出在 0j<i0 \le j < i 中有多少个 jj 满足 sjsixs_{j} \le s_i - x,答案就是每个位置 ii 前面满足条件 jj 的个数。

我们可以在顺序遍历数组 aa 的过程中,累计前缀和,并用 树状数组 维护 sis_i 出现的次数。因此,对于每个位置 ii,对答案的贡献为之前树状数组中小于等于 sixs_i - x 的数出现的总次数。

由于 109x109-10^9 \le x \le 10^9109ai109-10^9 \le a_i \le 10^9,无法直接存储到树状数组中。但不同的前缀和个数不会超过 nn,再加上不同 sixs_i - x 的个数,不同的数总共不会超过 2n2n。故可以将 sis_isixs_i - x 进行离散化,再用树状数组维护即可。时间复杂度 O(nlogn)\mathcal{O}(n\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
#include <bits/stdc++.h>
using namespace std;

#define fastio ios::sync_with_stdio(false), cin.tie(0)
using ll = long long;

const int N = 4e5 + 10;
int tr[N];

void add(int x, int c){
for(int i = x; i < N; i += i & -i){
tr[i] += c;
}
}

int query(int x){
int res = 0;
for(int i = x; i; i -= i & -i){
res += tr[i];
}
return res;
}

void marisa(){
int n, x; cin >> n >> x;
vector<ll> s(n + 1);
for(int i = 1; i <= n; i ++ ){
cin >> s[i];
s[i] += s[i - 1];
}
// 离散化
vector<ll> v;
for(int i = 0; i <= n; i ++ ){
v.emplace_back(s[i]);
v.emplace_back(s[i] - x);
}
sort(begin(v), end(v));
v.erase(unique(begin(v), end(v)), end(v));

auto get_id = [&](ll x){
return lower_bound(begin(v), end(v), x) - begin(v) + 1;
};
// 用树状数组维护前面 s_i 出现的次数
ll ans = 0;
add(get_id(0), 1); // 注意加入初始的状态
for(int i = 1; i <= n; i ++ ){
ans += query(get_id(s[i] - x));
add(get_id(s[i]), 1);
}
cout << ans << '\n';
}

int main(){
fastio;

int T = 1; // cin >> T;
while(T -- ) marisa();

return 0;
}

F MyGo!!!的共鸣时刻

出题人:AveMujica

题意简述

给定两个升序序列 A,BA, B,长度分别为 n,mn, m,相邻元素固定且严格为 1122。从序列 AABB 中分别取一个元素相加并去重排序得到一个集合 CC。每次询问集合 CC 中第 qq 个元素的值。

解题思路 (分类讨论,数学,思维)

本题实质上就是要求我们从公差为 1 或者 2 的集合 AA 和集合 BB 中任取一个数 aia_i (1in1 \leq i \leq n) 和 bjb_j (1jm1 \leq j \leq m),构造集合 CC,满足集合 CC 的元素 ck=ai+bjc_k = a_i + b_j,且 ckck+1c_k \neq c_{k + 1} (1k<len(C)1 \leq k < \text{len}(C)),ck<ck+1c_k < c_{k + 1} (1k<len(C)1 \leq k < \text{len}(C))。

​ 如果用暴力算法来求解 ckc_k,并用集合 setset 去重的话,解法的时间复杂度为 O(nmlogn)O(nm\log n),在 1n,m1051 \leq n, m \leq 10^5 的数据限制下显然无法通过本题。考虑通过某些性质来优化求解方案。集合 AABB 的公差都被限制为 1 或者 2,我们从公差切入,不难发现 AA 表和 BB 表只可能有 4 种情况:

​ (1) $ A$ 表和 BB 表的公差都为 1,AA 表和 BB 表长度都大于等于2;
​ (2) AA 表和 BB 表的公差都为 2,AA 表和 BB 表长度都大于等于2;
​ (3) AA 表和 BB 表的公差一个为 1,一个为 2,AA 表和 BB 表长度都大于等于2;
​ (4) AA 表和 BB 表其中一个长度为1,或长度都为 1。

​ 情况 (4) 很好求解,实质上就是其中一个集合,其每个元素都加上了长度为1的集合中的元素值 xx

​ 对于情况 (1) 和情况 (2),我们可以统一理解为 AA 表和 BB 表的公差相同。我们可以证明,公差相同的连续数列 AABB,任取两数相加后得到的新数列 CC,经升序排序和去重后,公差不变,且首项为 min(a)+min(b)\min(a) + \min(b),末项为 max(a)+max(b)\max(a) + \max(b)。这里给出公差为 2 的证明,公差为 1 的同理可证。

​ 设数列 aaa1,a1+2,a1+4,,a1+2(n1)a_1, a_1 + 2, a_1 + 4, \dots, a_1 + 2(n-1),数列 bbb1,b1+2,b1+4,,b1+2(m1)b_1, b_1 + 2, b_1 + 4, \dots, b_1 + 2(m-1)。两数列的最小项分别为 a1a_1b1b_1,最大项分别为 a1+2(n1)a_1 + 2(n - 1)b1+2(m1)b_1 + 2(m - 1)

​ 两数列中任取两数相加,和为:

s=(a1+2i)+(b1+2j)=(a1+b1)+2(i+j),s = (a_1 + 2i) + (b_1 + 2j) = (a_1 + b_1) + 2(i + j),

​ 其中 i[0,n1]i \in [0, n-1]j[0,m1]j \in [0, m-1]

​ 所有可能的和为 S=a1+b1+2kS = a_1 + b_1 + 2k,其中 k=i+jk = i + jkk 的取值范围为 0k(n1)+(m1)=n+m20 \leq k \leq (n - 1) + (m - 1) = n + m - 2

​ 因此,SS 的值为公差 2 的等差数列,覆盖从 a1+b1a_1 + b_1a1+b1+2(n+m2)a_1 + b_1 + 2(n + m - 2),首项为 a1+b1a_1 + b_1,末项为 a1+b1+2(n+m2)=max(a)+max(b)a_1 + b_1 + 2(n + m - 2) = \max(a) + \max(b),公差为 2,命题得证。

​ 由此我们解决了以公差相同的 AA 表和 BB 表构造 CC 表的难题,只需要求出 AA 表和 BB 表的最小值 min(a)+min(b)\min(a) + \min(b) 和最大值 max(a)+max(b)\max(a) + \max(b),从最小值以 2 或 1 为步长即可构造出集合内的任一元素 ckc_k

​ 现在考虑情况 (3),情况 (3) 中 AA 表和 BB 表的公差不同,且一个为 1,一个为 2,我们可以证明以下命题:

设数列 aa 是公差为 1 且长度 n2n \geq 2 的连续数列,数列 bb 是公差为 2 的连续数列(长度 m1m \geq 1)。从 aabb 中各任取一个数相加,组成的新数列 cc 经升序和去重后,公差为 1,且首项为 min(a)+min(b)\min(a) + \min(b),末项为 max(a)+max(b)\max(a) + \max(b)。证明如下:

​ 设数列 aa 的首项为 a1a_1,公差为 1,长度为 nn,则:

a={a1,a1+1,a1+2,,a1+(n1)}.a = \{ a_1, a_1 + 1, a_1 + 2, \dots, a_1 + (n - 1) \}.

​ 数列 bb 的首项为 b1b_1,公差为 2,长度为 mm,则:

b={b1,b1+2,b1+4,,b1+2(m1)}.b = \{ b_1, b_1 + 2, b_1 + 4, \dots, b_1 + 2(m - 1) \}.

​ 两数列的最小项分别为 a1a_1b1b_1,最大项分别为 a1+(n1)a_1 + (n - 1)b1+2(m1)b_1 + 2(m - 1)

​ 任取 aiaa_i \in abjbb_j \in b,其和为:

s=ai+bj=(a1+(i1))+(b1+2(j1))=a1+b1+(i1)+2(j1),s = a_i + b_j = (a_1 + (i - 1)) + (b_1 + 2(j - 1)) = a_1 + b_1 + (i - 1) + 2(j - 1),

​ 即 s=a1+b1+ks = a_1 + b_1 + k,其中 k=(i1)+2(j1)k = (i - 1) + 2(j - 1),则和为:

s=a1+b1+k.s = a_1 + b_1 + k.

​ 对任意 k[0,n+2m3]k \in [0, n + 2m - 3],取:

j=k2+1,i=k2(j1)+1.j = \left\lfloor \frac{k}{2} \right\rfloor + 1, \quad i = k - 2(j - 1) + 1.

​ 当 kk 为偶数时,

j=k2+1,2(j1)=k,此时i=1.j = \frac{k}{2} + 1, \quad 2(j - 1) = k, \quad \text{此时} \, i = 1.

​ 当 kk 为奇数时,

j=k12+1,2(j1)=k1,此时i=2.j = \frac{k - 1}{2} + 1, \quad 2(j - 1) = k - 1, \quad \text{此时} \, i = 2.

​ 由于 n2n \geq 2,无论 kk 奇偶,i2ni \leq 2 \leq n,且 jn+2m32+1mj \leq \left\lfloor \frac{n + 2m - 3}{2} \right\rfloor + 1 \leq m

​ 因此,所有 kk 均被覆盖,和数列 cc 为公差 1 的等差数列,覆盖从 a1+b1a_1 + b_1a1+b1+n+2m3a_1 + b_1 + n + 2m - 3

​ 由此,我们解决了公差为 1 和公差为 2 的数列的组合难题,对于长度大于等于 2 的公差为 1 的数列 AA / BB 和公差为 2 的数列 AA / BB,我们只需要知道 min(a)+min(b)\min(a) + \min(b)max(a)+max(b)\max(a) + \max(b),即可构造出集合 CC 中的任一元素 ckc_k

综上,所有情况讨论完毕,对于任一询问,我们都能以 O(1)O(1) 的时间复杂度输出答案,总的时间复杂度为 O(T)O(T)

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
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

void solve() {
int n, m;
cin >> n >> m;
vector<i64> A(n + 1), B(m + 1);
for (int i = 1; i <= n; i++) cin >> A[i];
for (int i = 1; i <= m; i++) cin >> B[i];
// 判断公差大小, 默认为0
int diffA = 0, diffB = 0;
if (n > 1) diffA = A[2] - A[1];
if (m > 1) diffB = B[2] - B[1];
// 如果公差相同, 则合并后的数列公差也相同
// 如果公差不同, 需要多判断公差为1的数列长度是否为1,如果A和B中有数列长度为1,我们也认为公差不同
bool flag = (n > 1 && m > 1) ? (diffA == diffB) : false;
// diff为合并后集合的公差
int t;
cin >> t;
while (t--) {
i64 q;
cin >> q;
i64 len, diff;
i64 c_min = A[1] + B[1];
i64 c_max = A[n] + B[m];
// 首先计算构造后数列的长度
if (flag) {
if (diffA == 1) {
len = c_max - c_min + 1;
diff = 1;
} else {
len = (c_max - c_min + 2) / 2;
diff = 2;
}
} else {
if (n == 1 && m == 1) {
len = 1;
diff = 0;
}
else if (m == 1) {
len = n;
diff = diffA;
}
else if (n == 1) {
len = m;
diff = diffB;
}
else {
len = c_max - c_min + 1;
diff = 1;
}
}
if (q > len) {
cout << -1 << "\n";
} else {
cout << c_min + (q - 1) * diff << "\n";
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
solve();
return 0;
}

2025 YAC Round 8 题解
https://marisamagic.github.io/2025/04/23/2025_YAC_8/
作者
MarisaMagic
发布于
2025年4月23日
许可协议