2025 YAC Round 7 题解

比赛大图来源：pixiv_id=100728200

A GPLT 第一道题

出题人：MarisaMagic

题意简述

输入字符串 $s$ 和 $t$，判断两个字符串是否相同。（字符串包含空格）

解题思路 （字符串基础）

C++ 使用 getline(cin, s) 输入字符串 $s$ 和 $t$，判断两个字符串是否相等。如果在 getline 之前使用了 cin 进行输入，需要调用 cin.ignore() 或 getchar() 吸收缓冲区中残余的换行符。

#include <bits/stdc++.h>
using namespace std;

void marisa(){
    string s, t;
    getline(cin, s);
    getline(cin, t);
    if(s == t) cout << "like a people!" << "\n";
    else cout << "shi ren wo chi." << "\n";
}

int main(){
    int T = 1; cin >> T;
    cin.ignore(); // 清除缓冲区残余的换行符
    while(T -- ) marisa();
    
    return 0;
}

B Attention! 计分规则

出题人：MarisaMagic

题意简述

给定一个参赛选手天梯赛各题的得分，求出其有效得分。计分规则参考 GPLT 团体程序设计天梯赛 命题与竞赛评分

解题思路 （语法）

分别统计各个阶段的得分，记为 $s_1, s_2$ 和 $s_3$。初始有效总分为 $s_1$。如果 $s_1 \ge 80$，有效总分加上 $s_2$。如果在 $s_1 \ge 80$ 的基础上 $s_2 \ge 40$，有效总分加上 $s_3$。

#include <bits/stdc++.h>
using namespace std;

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

void marisa(){
    vector<int> s(4);
    for(int i = 1, x; i <= 8; i ++ ) cin >> x, s[1] += x;
    for(int i = 1, x; i <= 4; i ++ ) cin >> x, s[2] += x;
    for(int i = 1, x; i <= 3; i ++ ) cin >> x, s[3] += x;
    int ans = s[1];
    if(s[1] >= 80) ans += s[2];
    if(s[1] >= 80 && s[2] >= 40) ans += s[3];
    cout << ans << '\n';
}

int main(){
    fastio;

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

C 冰之勇者的完美构造

出题人：MarisaMagic

题意简述

构造一个长度为 $n$ 的 非负整数 序列 $a_1,a_2,\dots,a_n$，满足如下条件：

• $\forall \ i \in[1, n]$，有 $0\le a_i\le m$。
• $a_1\oplus a_2\oplus\dots\oplus a_n=x$。其中 $\oplus$ 表示 按位异或 运算。

如果存在满足条件的序列 $a$，输出这个序列；否则输出 $-1$。

解题思路 （构造，贪心）

考虑将 $x$ 二进制拆分。由于 $0 \le a_i \le m$ 的限制，我们需要让 $x$ 二进制拆分后尽可能地小。由于序列异或和为 $x$ 的限制，我们还要避免出现两个不同元素 $a_i$ 和 $a_j$ 在同一个二进制位上都为 $1$。如果重复出现同一二进制位为 $1$，不仅不会对异或和有任何贡献，还会造成 $a_i$ 变大。

故直接将 $x$ 进行二进制拆分。例如 $x = 11011_2$，则直接拆分为 $10000_2, 1000_2, 10_2, 1_2$ 四个数字。可以发现，序列 $a$ 中的最大元素最小可以是 $10000_2$，而 剩余其它部分加起来不会比 $10000_2$ 大。因此，具体构造策略如下：

• 如果 $10000_2 > m$，那么 无解。
• 如果 $10000_2 \le m$，我们可以将这个值作为序列中的 $a_1$，然后将剩余部分加起来作为序列中的 $a_2$。由于 $x \oplus 0 = x$，故序列中剩余的 $a_3, \ldots, a_n$，直接赋值为 $0$ 即可。

上述构造方式适用于 $n \ge 2$ 的情况，故当 $n = 1$ 时，如果 $x > m$，无解；如果 $x \le m$，直接输出 $x$。

#include <bits/stdc++.h>
using namespace std;

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

void marisa(){
    int n, x, m; cin >> n >> x >> m;
    if(n == 1){
        if(x <= m) cout << x << '\n';
        else cout << -1 << "\n";
        return;
    }
    vector<int> a(n + 1);
    int idx = 1;
    for(int k = 30; ~k; k -- ){
        if((x >> k) & 1){
            if((1 << k) > m){
                cout << -1 << "\n";
                return;
            }
            if(idx == 1) a[idx ++ ] = (1 << k); // 作为 a_1
            else a[idx] |= (1 << k); // 剩余部分加起来作为 a_2
        }
    }
    for(int i = 1; i <= n; i ++ ){
        cout << a[i] << " \n"[i == n];
    }
}

int main(){
    fastio;

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

D 东之国的不眠夜

出题人：MarisaMagic

题意简述

给定一颗 $n$ 节点的树。从 $1$ 开始 深度优先搜索 访问 $n$ 个节点。求 $\forall i \in [1, n]$，节点 $i$ 最早 会在 第几个 被访问到 和 最晚 会在 第几个 被访问到。

解题思路 （树的遍历）

对于节点 $u$，要尽可能早到达该节点，只需要一开始就按照 $1 \rightarrow u$ 的路径进行搜索。故节点 $u$ 最早 会在 第几个 被访问到即 节点 $u$ 的深度。

对于节点 $u$，要尽可能晚到达该节点，需要尽可能地访问其它的节点，最后再访问节点 $u$。但是我们无法在访问 $u$ 之前访问 $u$ 子树中的节点。故节点 $u$ 最晚 会在 第几个 被访问到即 $n$ - 子树 $u$ 的大小 + $1$。

#include <bits/stdc++.h>
using namespace std;

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

void marisa(){
    int n; cin >> n;
    vector<vector<int>> e(n + 1);
    for(int i = 1, u, v; i < n; i ++ ){
        cin >> u >> v;
        e[u].emplace_back(v);
        e[v].emplace_back(u);
    }
    vector<int> d(n + 1);   // d[u]: 1 ~ u 距离
    vector<int> sz(n + 1);  // sz[u]: 子树 u 大小
    function<void(int, int)> dfs = [&](int u, int fa){
        sz[u] = 1;
        for(const auto& v : e[u]){
            if(v == fa) continue;
            d[v] = d[u] + 1; // 自顶向下
            dfs(v, u);
            sz[u] += sz[v];  // 自底向上
        }
    };
    dfs(1, 0);
    // 最小第几个: 点 u 的深度
    // 最大第几个: n - 子树 u 大小 + 1
    for(int i = 1; i <= n; i ++ ){
        cout << d[i] + 1 << ' ' << n - sz[i] + 1 << "\n";
    }
}

int main(){
    fastio;

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

E 永远亭的ACM姬

出题人：MarisaMagic

题意简述

从第 $x$ 年开始刷题，每年如果是闰年，做 $a$ 道题目；否则，做 $b$ 道题目。求第多少年达到至少 $n$ 道题目。

闰年 的判断规则： 年份 能被 4 整除但不能被 100 整除，或者 能被 400 整除。

解题思路 （二分，容斥原理）

假设最少到第 $y$ 年时达到至少 $n$ 道题目，那么总年份数为 $s_{year} = y - x + 1$。记 $s_{year}$ 年中有 $s_{leap}$ 个年份为闰年，另外 $s_{year} - s_{leap}$ 个年份为非闰年。此时的总做题数为 $s_{leap} \times a + (s_{year} - s_{leap}) \times b$。

$y$ 越大总做题数也越大，我们需要找到第一个使得 $s_{leap} \times a + (s_{year} - s_{leap}) \times b \ge n$ 的 $y$，显然此问题具有二段性，故考虑 二分答案。

关键在于如何快速计算第 $x \sim y$ 年中的闰年数量 $s_{leap}$。我们可以用 容斥原理 进行求解。显然，$1 \sim y$ 中能够被 $4$ 整除的年份数量为 $\left \lfloor \frac{y}{4} \right \rfloor$，能够被 $100$ 整除的年份数量为 $\left \lfloor \frac{y}{100} \right \rfloor$，能够被 $400$ 整除的年份数量为 $\left \lfloor \frac{y}{400} \right \rfloor$。

由于 $100$ 是 $4$ 的倍数，故能够被 $100$ 整除的年份都 包含 在能够被 $4$ 整除的年份中。因此，能被 $4$ 整除并且不能被 $100$ 整除的年份数量 可以由 $\left \lfloor \frac{y}{4} \right \rfloor - \left \lfloor \frac{y}{100} \right \rfloor$ 得到。

由于 $400$ 是 $100$ 的倍数，故能够被 $400$ 整除的年份都 包含 在能够被 $100$ 整除的年份中。因此， $1 \sim y$ 中的闰年数量 只需要再加上 能被 $400$ 整除的年份数量 $\left \lfloor \frac{y}{400} \right \rfloor$。

记 $1 \sim y$ 中闰年数量为 $f_y = \left \lfloor \frac{y}{4} \right \rfloor - \left \lfloor \frac{y}{100} \right \rfloor + \left \lfloor \frac{y}{400} \right \rfloor$， $x \sim y$ 中的闰年数量 $s_{leap}$ 即 $f_y - f_{x-1}$。

综上，我们二分答案，每次由上述方式计算出 $x \sim y$ 的闰年数量，检查是否满足 $s_{leap} \times a + (s_{year} - s_{leap}) \times b \ge n$。若满足，记录答案，并继续向左二分搜索；否则，继续向右二分搜索。

#include <bits/stdc++.h>
using namespace std;

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


inline ll f(ll y){ // 1 ~ y 中闰年数量
    return y / 4 - y / 100 + y / 400;
}

void marisa(){
    int x, a, b; cin >> x >> a >> b;
    ll n; cin >> n;
    auto check = [&](ll y){
        ll sy = y - x + 1; // 总年数
        ll sl = f(y) - f(x - 1); // 总闰年数
        return sl * a + (sy - sl) * b;
    };
    ll l = x, r = 1e15 + x; // 注意边界范围
    while(l < r){
        ll mid = l + r >> 1;
        if(check(mid) >= n) r = mid;
        else l = mid + 1;
    }
    cout << r << "\n";
}

int main(){
    fastio;

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

F 魔理沙偷走了重要的子串

出题人：MarisaMagic

题意简述

给定一个字符串 $s$，可以删除一个子串（子串可为空），求可得到最长回文串的长度。

解题思路 1 （字符串哈希）

可以先将字符串 $s$ 中本身已经构成回文的部分先去除，此部分可以用双指针 $l, r$ 分别从头和尾进行遍历，得到已有的回文前后缀长度 $l$。若 $l \ge r$ 说明本身就是回文串，此时可以提前输出字符串长度为答案。

接下来只需要考虑字符串 剩余部分 $s_{l, r}$，我们将其 视为新的字符串 $s$。现在 $s$ 的两端肯定不同（没有回文的前后缀），而我们需要删除一个子串，使得删去后的部分是一个小的回文串，加上先前去除的已经构成的回文前后缀得到一整个回文串。因此，我们一定是删除当前这个 $s$ 的一个前缀或一个后缀。

先考虑删除 $s$ 的一个后缀的情形。我们可以从大到小枚举 $i$，判断保留的 $s$ 的前缀 $s_{1, i}$ 是不是回文串（也就是删除 $s_{i + 1, |s|}$ 这个后缀）。判断一个字符串是否是回文串可以用 字符串哈希（正向哈希 和 反向哈希 相等）实现。如果当前 $i$ 满足 $s_{1, i}$ 是一个回文串，直接返回答案 $i$。

对于删除 $s$ 的一个前缀的情形，只需要将 $s$ 反过来再进行一次上述枚举即可。

最终答案就是 正反两次枚举得到的较大值 + 已有的回文前后缀长度 $l \times 2$。

#include <bits/stdc++.h>
using namespace std;

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

struct Hash{
    using ll = long long;
    const int base = 233;
    const int mod = 1e9 + 9;
    int n;
    vector<ll> b, h, rh; // 正向哈希，反向哈希
    Hash() {}
    Hash(const string& s){
        init(s);
    }
    void init(const string& s){
        n = s.size();
        b.resize(n + 1);
        h.resize(n + 1), rh.resize(n + 1);
        b[0] = 1;
        h[0] = rh[0] = 0;
        for(int i = 1; i <= n; i ++ ){
            b[i] = b[i - 1] * base % mod;
            h[i] = (h[i - 1] * base % mod + s[i - 1]) % mod;
            rh[i] = (rh[i - 1] * base % mod + s[n - i]) % mod;
        }
    }
    ll get_h(int l, int r){ // 正向哈希
        return (h[r] - h[l - 1] * b[r - l + 1] % mod + mod) % mod; 
    }
    ll get_rh(int l, int r){ // 反向哈希
    	return (rh[r] - rh[l - 1] * b[r - l + 1] % mod + mod) % mod;
    }
    bool same(int l1, int r1, int l2, int r2){
        return get_h(l1, r1) == get_h(l2, r2);
    }
    ll is_palindrome(int l, int r){ // 反向哈希下标范围反过来
    	return get_h(l, r) == get_rh(n - r + 1, n - l + 1);
    }
};

int get_ans(const string& s){
    Hash hs(s);
    int n = s.size();
    for(int i = n; i; i -- ){ // 枚举前缀长度
        if(hs.is_palindrome(1, i)){
            return i;
        }
    }
    return 0;
}

void marisa(){
    string s; cin >> s;
    int l = 0, r = s.size() - 1;
    for(; l < r && s[l] == s[r]; l ++ , r -- );
    if(l >= r){ // 本身就是回文串
        cout << s.size() << "\n";
        return;
    }
    s = s.substr(l, r - l + 1); // 剩余部分
    string t(s.rbegin(), s.rend()); 
    cout << max(get_ans(s), get_ans(t)) + l * 2 << "\n";
}

int main(){
    fastio;

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

解题思路 2 （Manacher）

同样只需要考虑剩余部分的 $s$，我们可以用 Manacher 算法 预处理求出每个位置的最右边回文边界 $r_i$。

在 Manacher 算法中我们通常会在字符串的 $|s| + 1$ 个空位中添加 # 字符来统一处理奇数长度和偶数长度的回文串，求出 $r$ 数组后枚举中心位置 $i$，如果有 $r_i - 1 = i$，则表明前缀 $s_{1, i}$ 是一个回文串，更新回文前缀的最大值。

同样也只要反过来求一次 Manacher 即可求出保留回文后缀的情形。

最终答案就是 正反两次 Manacher 的答案的较大值 + 已有的回文前后缀长度 $l \times 2$。

#include <bits/stdc++.h>
using namespace std;

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

vector<int> manacher(const string& s){
    string t = "#";
    for(const auto& ch : s){
        t += ch;
        t += '#';
    }
    int n = t.size();
    vector<int> r(n); // i - r[i] + 1 ~ i + r[i] - 1 是一个回文子串
    // j 记录上一个回文子串的中心
    for(int i = 0, j = 0; i < n; i ++ ){ 
        // 2 * j - i 为 i 在 j 为中心的回文串中的翻转位置的小回文子串的中心
        if(2 * j - i >= 0 && j + r[j] > i){ 
            // 取翻转位置的 r 和到 j 边界距离的较小值
            r[i] = min(r[2 * j - i], j + r[j] - i); 
        }
        while(i - r[i] >= 0 && i + r[i] < n && t[i - r[i]] == t[i + r[i]]){
            r[i] ++ ; // 此部分暴力计算
        }
        if(i + r[i] > j + r[j]){ // 如果超出 j 边界，更新当前 j 为 i
            j = i;
        }
    }
    return r;
}

int get_ans(const string& s){
    auto r = manacher(s);
    int ans = 0;
    for(int i = 0; i < r.size(); i ++ ){
        if(r[i] - 1 == i){ // 说明前缀是个回文串
            ans = max(ans, r[i] - 1); 
        }
    }
    return ans;
}

void marisa(){
    string s; cin >> s;
    int l = 0, r = s.size() - 1;
    for(; l < r && s[l] == s[r]; l ++ , r -- );
    if(l >= r){
        cout << s.size() << "\n";
        return;
    }
    s = s.substr(l, r - l + 1);
    string t(s.rbegin(), s.rend());
    cout << max(get_ans(s), get_ans(t)) + l * 2 << "\n";
}

int main(){
    fastio;

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

PS：F 题解 Manacher 模板参考 jiangly 算法模板收集 Manacher