Upcpc2025 - Star's Blog

更新记录#

本人实力有限，有一些题至今还没做出来，之后会时不时填坑，故把填坑记录加到最上面了，目前还差 I, K, L。

2025/03/11 更新了 J 题的解法。
2025/03/16 更新了 J 题解法的解释。

Problem A. 精准切割#

这里提供一种暴力的方法，以左下角为原点，长边为 x 轴，短边为 y 轴建立平面直角坐标系（为保证精度，所有坐标乘 n，因为 n 是分母），暴力尝试主对角线在一列格子左侧和右侧的截距，记为 $y_1,y_2$ 记 $t = \lfloor \frac{y_1}{n} \rfloor \times n$ ，如果 $(y_1 - t) + (y_2 - t) = n$ 表明切割是对称的，该块被均分。

我感觉一定有不暴力的办法，欢迎计算几何大佬的新点子。

参考代码

1
#include <iostream>
2

3
using namespace std;
4

5
int f(int n, int m) {
6
    if (n < m) swap(n, m);
7
    int res = 0;
8
    for (int i = 1; i <= n; ++i) {
9
        int t = (i - 1) * m / n * n;
10
        if ((i * m - t) + ((i - 1) * m - t) == n) res++;
11
    }
12
    return res;
13
}
14

15
int main() {
16
    cout << f(22, 38) << endl << f(21, 36) << endl;
17
    return 0;
18
}

Problem B. 让时间走走停停#

~~这道才是真签到题，下面那道签到题学学啊😭~~

记初始状态为 0，平年 +365，闰年 +366，对 7 取模，如果是 0，就是福利年。

参考代码

1
#include <iostream>
2

3
using namespace std;
4

5
int main() {
6
    int i, t = 1, cur = 0;
7
    for (i = 2001; t < 8; ++i) {
8
        cur += 365;
9
        if (i % 100 == 0 && i % 400 == 0 || i % 4 == 0) cur++;
10
        cur %= 7;
11
        if (cur == 0) t++;
12
    }
13
    cout << i - 1 << endl;
14
    return 0;
15
}

Problem C. 大力出奇迹#

看题目好像就是让暴力的（~~孩子只会暴力~~），赛后我在本地跑我的 O(n²) 暴力程序只跑了 4min 19s，思考下一道题的时候挂上暴力，下一道敲完了就跑完了。答案是 809/1001.

暴力的代码

1
#include <iostream>
2

3
using namespace std;
4

5
int gcd(int a, int b) {
6
    return b ? gcd(b, a % b) : a;
7
}
8

9
int main() {
10
    long long a = 0, b = 1;
11
    int n = 111111;
12
    for (int i = 2; i <= n; ++i) {
13
        int t = 0;
14
        for (int j = 2; j <= i; ++j) {
15
            if (gcd(i, j) != 1) t++;
16
        }
17
        if (a * i < t * b) a = t, b = i;
18
        printf("%d tries left\n", n - i);
19
    }
20
    int g = gcd(a, b);
21
    a /= g, b /= g;
22
    printf("%lld/%lld\n", a, b);
23
    return 0;
24
}

有图有真相（第一次跑的时候忘了约分了，但是无伤大雅，运行时间大致是准的）

Problem D. 时左时右#

直接按照题目的要求模拟即可，时间复杂度是 O(nm)，完全够用。维护 ne[i][j] 表示当前在第 i 个通道，在第 j 次移动时移动到的下一个点，默认为 i；然后遍历 [1, n]，分别模拟一遍并记录答案即可。

参考代码

1
#include <iostream>
2

3
using namespace std;
4

5
int ne[110][1010], res[110];
6

7
int main() {
8
    int n, m;
9
    cin >> n >> m;
10
    for (int i = 1; i <= n; ++i) {
11
        for (int j = 1; j <= m; ++j) {
12
            ne[i][j] = i;
13
        }
14
    }
15
    for (int i = 1; i <= m; ++i) {
16
        int t;
17
        cin >> t;
18
        ne[t][i] = t + 1, ne[t + 1][i] = t;
19
    }
20
    for (int i = 1; i <= n; ++i) {
21
        int t = i;
22
        for (int j = 1; j <= m; ++j) t = ne[t][j];
23
        res[t] = i;
24
    }
25
    for (int i = 1; i <= n; ++i) cout << res[i] << endl;
26
    return 0;
27
}

Problem E. “合作”#

从资质最弱的艾比这里考虑很困难，因为不好确定谁会和它合作，谁会攻击它。不妨从资质最强的艾比开始考虑。

资质最强的艾比一定会活下来，并且持续攻击资质比他弱的艾比；
考虑资质次强的艾比，为了留下来，它会选择帮助一定数量的艾比防御（这个数量尽可能小），直到这一个区间内的艾比的资质和大于或者等于资质最强的艾比。如此，一个区间内的艾比都能活下来；活下来之后他们会选择尽可能赶走其他艾比，因此会和最强的合作，攻击其他更弱的艾比；
循环往复，直到剩下的所有艾比合作都无法抵御攻击者，至此攻击者全部留下来，剩下的艾比全部被赶走。

接下来模拟这个过程即可。

参考代码

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
const int N = 500010;
7
int s[N];
8

9
int main() {
10
    int n;
11
    scanf("%d", &n);
12
    for (int i = 1; i <= n; ++i) {
13
        scanf("%d", &s[i]);
14
    }
15
    sort(s + 1, s + n + 1);
16
    long long rs = s[n], ls = 0;
17
    int p = n;
18
    for (int i = n - 1; i; --i) {
19
        ls += s[i];
20
        if (ls >= rs) {
21
            rs += ls;
22
            ls = 0;
23
            p = i;
24
        }
25
    }
26
    printf("%d\n", n - p + 1);
27
    return 0;
28
}

Problem F. 未完待续#

这道题非常的坑人，挖坑挖的非常巧妙，如果题面能加一句“通过旋转可以等价的情况视为多种”就更完善了。

一般情况#

考虑线性dp，记 f[i][0] 为第 i 列不放牌的方案个数，f[i][1] 为第 i 列放牌的方案个数，显然有

f_{i, 0} = f_{i - 1, 0} + f_{i - 1, 1}

f_{i, 1} = 2f_{i - 1, 0}

这个递推式可以用矩阵加速，构造递推式如下

\begin{pmatrix} f_{i - 1, 0} & f_{i - 1, 1} \end{pmatrix} * \begin{pmatrix} 1 & 2\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} f_{i, 0} & f_{i, 1} \end{pmatrix}

初始状态 $\begin{pmatrix} 1 & 0 \end{pmatrix}$ ，用矩阵快速幂求 $\begin{pmatrix} 1 & 2\\ 1 & 0 \end{pmatrix}^n$ ，然后相乘，就能得到 $\begin{pmatrix} f_{n, 0} & f_{n, 1} \end{pmatrix}$ . 这样就得到了 O(log n) 的做法。

特殊情况#

考虑 3 × 3 的情况，因为题目说平行于长度为 3 的边，此时平行于哪条边都是可以的，原来有 11 种情况，顺时针旋转 90°，还有 10 种情况，另外还有以下四种情况，共计 25 种，特判 n = 3 时输出 25 即可。

1
**_  __*  *__  _**
2
__*  __*  *__  *__
3
__*  **_  _**  *__

参考代码

1
#include <iostream>
2
#include <vector>
3

4
using namespace std;
5

6
const int MOD = 1000000007;
7

8
vector<vector<int>> mul(vector<vector<int>> a, vector<vector<int>> b) {
9
    vector<vector<int>> res(2, vector<int>(2, 0));
10
    for (int k = 0; k < 2; ++k) {
11
        for (int i = 0; i < 2; ++i) {
12
            for (int j = 0; j < 2; ++j) {
13
                res[i][j] = (res[i][j] + (long long)a[i][k] * b[k][j] % MOD) % MOD;
14
            }
15
        }
16
    }
17
    return res;
18
}
19

20
int solve(unsigned long long p) {
21
    if (p == 3) return 25;
22
    vector<vector<int>> res = {{1, 0}, {0, 1}}, base = {{1, 2}, {1, 0}};
23
    while (p) {
24
        if (p & 1) res = mul(res, base);
25
        base = mul(base, base);
26
        p >>= 1;
27
    }
28
    return (res[0][0] + res[0][1]) % MOD;
29
}
30

31
int main() {
32
    unsigned long long n; // 注意数据范围，别把 long long 爆了
33
    cin >> n;
34
    cout << ((solve(n * 2) - solve(n)) % MOD + MOD) % MOD << endl;
35
    return 0;
36
}

Problem G. 这里一定发生过什么#

XXX，G 题有一份……不，是 26 份提交，没有通过。~~没错，这就是我~~

拼音，不可战胜的。

豆包写的代码（一遍秒了，我不如豆包😭）

1
#include <iostream>
2
#include <string>
3
#include <vector>
4

5
int main() {
6
    std::vector<std::string> pinyinTexts = {
7
        "you ren shuo zhao ge ge zhu ban dan wei de yi ju jian jie zai qian mian jia shang you ren shuo zai hou mian jia shang ye you ren ren wei bu jin ru ci ni zen me kan jiu ke yi chu cheng ben ci xiao sai de qian dao ti ye you ren ren wei bu jin ru ci ni zen me kan",
8
        "ACM ju le bu shi gao xin jiu ye ming xiao shen zao de yao lan",
9
        "ji suan ji xue yuan shuang chuang zhong xin lang chao ju le bu zhuan zhu yu pei yang xue sheng chuang xin neng li",
10
        "wu xian dian xie hui ju jiao yu dian zi ji shu yu chuang xin shi jian",
11
        "shu xue jian mo xie hui duo ci bei ping wei you xiu she tuan",
12
        "zen me kan jiu shi wei le zhe dian cu cai bao de zhe dun jiao zi"
13
    };
14

15
    int n;
16
    std::cin >> n;
17
    if (n >= 1 && n <= 6) {
18
        std::cout << pinyinTexts[n - 1] << std::endl;
19
    }
20

21
    return 0;
22
}

Problem H. 数对#

遍历一遍字符串（字符串记为s），开一个数组 vis 记录每一种小写字母上次出现的位置，对于每一个位置 i，遍历 $\text{j} \in [\text{'a', 'z'}]$ ，IF vis[j] > vis[i] THEN 答案++ 即可。

参考代码

1
#include <iostream>
2
#include <cstring>
3

4
using namespace std;
5

6
int vis[26];
7

8
int main() {
9
    memset(vis, -1, sizeof(vis));
10
    string s;
11
    int res = 0;
12
    cin >> s;
13
    for (int i = 0; i < s.length(); ++i) {
14
        for (int j = 0; j < 26; ++j) {
15
            if (~vis[j] && vis[j] > vis[s[i] - 'a']) res++;
16
        }
17
        vis[s[i] - 'a'] = i;
18
    }
19
    cout << res << endl;
20
    return 0;
21
}

Problem J. 木板放置#

看着无从下手~~（实际上也无从下手）~~。

这题可以用贪心做，具体做法是

对于合法的情况，做法是先把长度都设成 R，枚举每一个间距优先保证左侧的板子长度为 R，对于不满足要求的间距优先缩短右侧，如果右侧缩到 L，仍然不合法，就继续缩短左侧。
对于不合法情况，在遍历间距的时候判断间距是否小于 L 即可。

证明（数学归纳法）：

显然，n = 1 的时候满足；
假设 n = k 的时候是最优的，那么在最后面再加一个长度为 R 的木板
- 如果放得下，那一定还是最优；
- 如果放不下，缩短最后一个木板和缩短第 k 个木板是等价的。

所以这个做法是可行的。

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
const int N = 100010;
7

8
int a[N], s[N];
9

10
int main() {
11
    int n, l, r;
12
    scanf("%d%d%d", &n, &l, &r);
13
    for (int i = 1; i <= n; ++i) {
14
        scanf("%d", &a[i]);
15
        s[i] = r;
16
    }
17
    a[0] = -0x3f3f3f3f, a[n + 1] = 0x3f3f3f3f;
18
    sort(a + 1, a + n + 1);
19
    for (int i = 1; i <= n; ++i) {
20
        if (a[i] - a[i - 1] < l) {
21
            printf("-1\n");
22
            return 0;
23
        }
24
        else if ((s[i - 1] + l) <= (a[i] - a[i - 1]) * 2) s[i] = min(r, (a[i] - a[i - 1]) * 2 - s[i - 1]);
25
        else s[i] = l, s[i - 1] = (a[i] - a[i - 1]) * 2 - l;
26
    }
27
    int res = 0;
28
    for (int i = 1; i <= n; ++i) {
29
        res += s[i];
30
    }
31
    printf("%d\n", res);
32
    return 0;
33
}

Problem M. 删数#

这道题相对正常，~~比 G 简单 ♾️ 倍。~~

简单变换一下，剩下的总和为 m，等价于删除的一段的总和为 $\sum_{i = 1}^{n}{a_i} - m$ ；只需维护一个前缀和数组 s，对于每一次查询，遍历数组，对于每一个位置 i，是否存在 $j \in [0, i]$ , $s_i - s_j = s_n - m$ 即可；查询的方法有很多种，我给出的参考代码用的二分查找，也可以用 unordered_set，unordered_map 等 STL 容器维护。

参考代码

1
#include <iostream>
2
#include <algorithm>
3

4
using namespace std;
5

6
long long s[1000010];
7

8
int main() {
9
    int n, q;
10
    scanf("%d%d", &n, &q);
11
    for (int i = 1; i <= n; ++i) {
12
        scanf("%lld", &s[i]);
13
        s[i] += s[i - 1];
14
    }
15
    while (q--) {
16
        int m;
17
        scanf("%d", &m);
18
        m = s[n] - m;
19
        bool f = false;
20
        for (int i = 1; i <= n; ++i) {
21
            int l = 0, r = i;
22
            while (l < r) {
23
                int mid = l + r >> 1;
24
                if (s[mid] >= s[i] - m) r = mid;
25
                else l = mid + 1;
26
            }
27
            if (s[i] - s[l] == m) {
28
                f = true;
29
                break;
30
            }
31
        }
32
        if (f) printf("Yes\n");
33
        else printf("No\n");
34
    }
35
    return 0;
36
}

获奖感言#

观前提醒：胡言乱语，请不要信以为真！！！

我感谢 G 题的出题人，让我认识到了自己作为中国人应该有点文化素养仍有欠缺；我佩服 J 题的出题人，ta 很会坑人（我明年也一定会向 ta 学习）。小米保温杯很好用，比手环实用多了，这一定是 G 题出题人无意间给我安排好的吧。

实话说，这次校赛基本上都没对到我的强项上，计算几何，数学题，博弈，汉语拼音正好完美包括了我的弱项。给了数学语文基础好的人很大的发挥空间，对于我这种只会基本的 DP，图论，数据结构的人简直是灾难级的😭，做不动，根本做不动，最后 7 分钟的时候调拼音调得心态彻底崩了。