2025 YAC Round 8 题解

比赛大图来源：pixiv_id=70066287

A 歳月-雲流れ-

出题人：MarisaMagic

题意简述

给定一个长度为 $n$ 的 $01$ 序列，求一个长度最小的连续区间 $[l, r]$ 包含所有的 $1$。

解题思路 （模拟）

去除开头和结尾连续的 $0$ 得到的子区间即包含所有 $1$ 的长度最小的连续区间。时间复杂度 $\mathcal{O}(n)$。

#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

题意简述

给定数字 $n$ 和 $m$，第一次最多可以减去 $m$，第二次最多可以减去 $x_1 = \left \lceil \frac{m}{2} \right \rceil$，第三次最多可以减去 $x_2 = \left \lceil \frac{x_1}{2} \right \rceil$，依次类推。求最少需要多少次使得 $n$ 减为 $0$。

解题思路 （模拟）

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

#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

题意简述

给定数字 $a$ 和 $b$，每次进行如下两种操作之一：

1. 花费 $x$ 代价，使得 $a$ 减去 $2$ 或者 $b$ 减去 $2$。（前提 $a$ 至少为 $2$ 或 $b$ 至少为 $2$）；
2. 花费 $y$ 代价，使得 $a$ 减去 $1$ 并且 $b$ 减去 $1$。（前提 $a$ 至少为 $1$ 或 $b$ 至少为 $1$）。

求使得 $a$ 或 $b$ 减为 $0$ 所需的最少次数。

解题思路 （数学）

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

• 当 $x \le 2 \times y$。显然两个两个减去的效率更高，此时考虑先将 $a$ 和 $b$ 其中一个值优先两个两个减，最后可能还余 $1$。故此时答案为 $\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 > y$ 且 $a, b$ 分别所需的操作次数相同，所以并不是 $a$ 和 $b$ 哪个更小就对哪个进行操作，故最后需要取一下最小值。

#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

题意简述

有一个长度为 $n$ 的环形数组 $a$，找到一个长度不超过 $n$ 的非空子数组使得子数组总和最大。

解题思路 1 （DP，最大最小子数组和）

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

最终答案为两种情况的较大值。特别的，如果数组 $a$ 的元素均为负数，由于要找的子数组非空，不满足上述跨环的情况，故此时答案为 $a$ 的最大子数组和。时间复杂度 $\mathcal{O}(n)$。

#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 （前缀和，单调队列）

复制一遍数组 $a$，预处理前缀和 $s$。对于每个位置 $i$，最优的答案为 $s_i - \max_{\max(0, i - n) \le j < i} s_{j}$。

可以用单调队列维护前面位置最小前缀和的下标，对于每个位置 $i$ 更新答案。注意开始时需要放入初始状态 $0$。时间复杂度 $\mathcal{O}(n)$。

#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

题意简述

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

解题思路 （离散化，树状数组）

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

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

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

由于 $-10^9 \le x \le 10^9$，$-10^9 \le a_i \le 10^9$，无法直接存储到树状数组中。但不同的前缀和个数不会超过 $n$，再加上不同 $s_i - x$ 的个数，不同的数总共不会超过 $2n$。故可以将 $s_i$ 和 $s_i - x$ 进行离散化，再用树状数组维护即可。时间复杂度 $\mathcal{O}(n\log n)$。

#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, B$，长度分别为 $n, m$，相邻元素固定且严格为 $1$ 或 $2$。从序列 $A$ 和 $B$ 中分别取一个元素相加并去重排序得到一个集合 $C$。每次询问集合 $C$ 中第 $q$ 个元素的值。

解题思路 （分类讨论，数学，思维）

本题实质上就是要求我们从公差为 1 或者 2 的集合 $A$ 和集合 $B$ 中任取一个数 $a_i$ ($1 \leq i \leq n$) 和 $b_j$ ($1 \leq j \leq m$)，构造集合 $C$，满足集合 $C$ 的元素 $c_k = a_i + b_j$，且 $c_k \neq c_{k + 1}$ ($1 \leq k < \text{len}(C)$)，$c_k < c_{k + 1}$ ($1 \leq k < \text{len}(C)$)。

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

​ (1) $ A$ 表和 $B$ 表的公差都为 1，$A$ 表和 $B$ 表长度都大于等于2；
​ (2) $A$ 表和 $B$ 表的公差都为 2，$A$ 表和 $B$ 表长度都大于等于2；
​ (3) $A$ 表和 $B$ 表的公差一个为 1，一个为 2，$A$ 表和 $B$ 表长度都大于等于2；
​ (4) $A$ 表和 $B$ 表其中一个长度为1，或长度都为 1。

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

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

​ 设数列 $a$ 为 $a_1, a_1 + 2, a_1 + 4, \dots, a_1 + 2(n-1)$，数列 $b$ 为 $b_1, b_1 + 2, b_1 + 4, \dots, b_1 + 2(m-1)$。两数列的最小项分别为 $a_1$ 和 $b_1$，最大项分别为 $a_1 + 2(n - 1)$ 和 $b_1 + 2(m - 1)$。

​ 两数列中任取两数相加，和为：

$$s = (a_1 + 2i) + (b_1 + 2j) = (a_1 + b_1) + 2(i + j),$$

​ 其中 $i \in [0, n-1]$，$j \in [0, m-1]$。

​ 所有可能的和为 $S = a_1 + b_1 + 2k$，其中 $k = i + j$，$k$ 的取值范围为 $0 \leq k \leq (n - 1) + (m - 1) = n + m - 2$。

​ 因此，$S$ 的值为公差 2 的等差数列，覆盖从 $a_1 + b_1$ 到 $a_1 + b_1 + 2(n + m - 2)$，首项为 $a_1 + b_1$，末项为 $a_1 + b_1 + 2(n + m - 2) = \max(a) + \max(b)$，公差为 2，命题得证。

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

​ 现在考虑情况 (3)，情况 (3) 中 $A$ 表和 $B$ 表的公差不同，且一个为 1，一个为 2，我们可以证明以下命题：

设数列 $a$ 是公差为 1 且长度 $n \geq 2$ 的连续数列，数列 $b$ 是公差为 2 的连续数列（长度 $m \geq 1$）。从 $a$ 和 $b$ 中各任取一个数相加，组成的新数列 $c$ 经升序和去重后，公差为 1，且首项为 $\min(a) + \min(b)$，末项为 $\max(a) + \max(b)$。证明如下：

​ 设数列 $a$ 的首项为 $a_1$，公差为 1，长度为 $n$，则：

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

​ 数列 $b$ 的首项为 $b_1$，公差为 2，长度为 $m$，则：

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

​ 两数列的最小项分别为 $a_1$ 和 $b_1$，最大项分别为 $a_1 + (n - 1)$ 和 $b_1 + 2(m - 1)$。

​ 任取 $a_i \in a$ 和 $b_j \in b$，其和为：

$$s = a_i + b_j = (a_1 + (i - 1)) + (b_1 + 2(j - 1)) = a_1 + b_1 + (i - 1) + 2(j - 1),$$

​ 即 $s = a_1 + b_1 + k$，其中 $k = (i - 1) + 2(j - 1)$，则和为：

$$s = a_1 + b_1 + k.$$

​ 对任意 $k \in [0, n + 2m - 3]$，取：

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

​ 当 $k$ 为偶数时，

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

​ 当 $k$ 为奇数时，

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

​ 由于 $n \geq 2$，无论 $k$ 奇偶，$i \leq 2 \leq n$，且 $j \leq \left\lfloor \frac{n + 2m - 3}{2} \right\rfloor + 1 \leq m$。

​ 因此，所有 $k$ 均被覆盖，和数列 $c$ 为公差 1 的等差数列，覆盖从 $a_1 + b_1$ 到 $a_1 + b_1 + n + 2m - 3$。

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

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

#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;     
}