UPCPC2025网络预选赛

应 🐸 的建议，不能光埋头刷题，还应该 水水博客 写写题解，所以后续会时不时更新训练赛和 CSES Problem Set 部分我会的题的题解。

我个人网络预选赛打的还是挺顺利的，虽然榜一差点被抢了。 大部分题都是非常基础的签到题难度的题，主要可能是有的题比较阴间，这种难度应该也不怎么用看代码吧，绝对不是打的时候着急赶时间就没存代码。

A. ACM 常识问答

这“常识”反正我是不知道，用 python 随机了七十多次答案未果。

B. 割圆术

真正的签到题，只需要注意开 long long，或者用 python 就行。

C. 大小

签到题，直接 if-else 就行

D. 子序列

维护前缀和数组s，对每一个位置i，二分查找 0 ~ i - 1 中第一个 ≤ $s_i-k$ 位置，加起来就是答案，二分可以直接用 upper_bound。

E. 神秘咒符

签到题，遍历字符串挨个比较就行，

F. 油专串

略微有点阴间的签到题 (我绝对没有 3 tries)，注意字符串里有空格和不合法的数据，多加一步判断是否整个串都是大写字母即可。

G. 海人的数学题1

利用差分的思想和容斥原理，设 f(x) = x - (x / div1 + x / div2 - x / 最小公倍数(div1, div2))，答案是 f(number2) - f(number1 - 1) 。

H. 这是签到题吗

这不是 😭（超大声）

拼尽全力没有看懂题，看榜二已经开摆了，我也不想看了。

I. 紊乱的静脉

每次操作都会增加2，所以答案是 min(原来的通畅个数 + 2 * k, n - 1)。

• ps : 这道是最后一个写的，所以有代码。

#include <iostream>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    int n, m, t = 0;
    string s;
    cin >> n >> m;
    cin >> s;
    s = " " + s + " ";
    for (int i = 1; i <= n; ++i) {
        if (s[i] == 'L' && s[i - 1] == 'L') t++;
        else if (s[i] == 'R' && s[i + 1] == 'R') t++;
    }
    cout << min(n - 1, t + m * 2) << endl;
    return 0;
}

K. 卡牌游戏

直接 $n^2$ 挨个试就行了。

L. 魔法

• 如果 R - L + 1 ≥ 2025 那肯定会有一个 i 能让 i mod 2025 取到 0，所以答案是 0；

• 否则一共就两千多个数，挨个试就行。

M. 海人的数学题2

直接暴力就行，先算总和，然后遍历数组，一直 res = min(res, abs((总和 - 前缀和) - 前缀和))。