NOTE
比赛链接：Unofficial Mirror 2026 CCPC National Invitational (Nanchang) and The 3rd Jiangxi Provincial Programming Contest

D - 电梯#

关键词：思维，数学

题目要求：每部电梯必须停在第 $1$ 层和第 $n$ 层；对于任意两层 $x,y$ ，需要存在一部电梯，使得 $x,y$ 是这部电梯的相邻停靠层，也就是可以直达。输出时需要给出最少电梯数，并构造每部电梯的停靠序列，且总停靠层数不能超过 $2 \times 10^6$ 。

思路#

考虑如何转化问题，假设现在有 $n$ 层楼，如果一部电梯停靠 $1,3,5,n$ ，那么它可以直达的楼层对是 $(1,3),(3,5),(5,n)$ ，也就是说一部电梯的停靠方案，本质上是把整段楼层分割成若干区间。例如 $1, 3, 5, 8$ 对应区间 $[1, 3], [3, 5], [5, 8]$ 。

所以题目变成：用最少的区间划分方案，覆盖所有楼层对 $(x, y)$ 。

G - 可能是字符串签到题#

关键词：贪心，前缀和

思路#

询问某个区间内出现次数最多的子串的个数，实际上由于长度为 $1$ 的子串也是合法子串，且任何长度大于 $1$ 的子串，出现次数都不可能超过它首字符的出现次数，所以求的就是某个区间内出现次数最多的字母的数量，使用前缀和预处理，每次询问枚举 $26$ 个字母，更新答案即可。

证明：假设在 $s[l,r]$ 中，某个子串 $T$ 出现了 $k$ 次。

例如：
$T = \texttt{ab}$
如果 $\texttt{ab}$ 出现了 $k$ 次，那么每一次 $\texttt{ab}$ 的出现位置上，开头字符 $\texttt{a}$ 也一定出现了一次。

所以：
$\operatorname{cnt}(\texttt{ab}) \le \operatorname{cnt}(\texttt{a})$
更一般地，假设子串 $T$ 的第一个字符是 $c$ ，那么：
$\operatorname{cnt}(T) \le \operatorname{cnt}(c)$

Code#

1
// Problem: CF GYM 106554 G
2
// Contest: Codeforces - [Unofficial Mirror] 2026 CCPC National Invitational (Nanchang) and The 3rd Jiangxi Provincial
3
// Programming Contest URL: https://codeforces.com/gym/106554/problem/G
4
// Time: 2026-05-28 22:22:17
5
#include <bits/stdc++.h>
6
using namespace std;
7

8
// clang-format off
9
#define endl '\n'
10
#define all(x) (x).begin(), (x).end()
11
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
12
// clang-format on
13

14
using ll = long long;
15
using ull = unsigned long long;
16
using pii = pair<int, int>;
17
using pdd = pair<double, double>;
18
using pll = pair<long long, long long>;
19
using i128 = __int128;
20

21
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
22
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
23
const int inf = 0x3f3f3f3f;
24
const int N = 1e6 + 10;
25

26
int cnt[N][26];
27

28
void solve()
29
{
30
    int n, q;
31
    cin >> n >> q;
32

33
    string s;
34
    cin >> s;
35

36
    s = " " + s;
37

38
    for (int i = 1; i <= n; i++)
39
    {
40
        for (int j = 0; j < 26; j++)
41
            cnt[i][j] = cnt[i - 1][j];
42
        cnt[i][s[i] - 'a']++;
43
    }
44

45
    while (q--)
46
    {
47
        int l, r;
48
        cin >> l >> r;
49

50
        int res = 0;
51
        for (int i = 0; i < 26; i++)
52
            res = max(res, cnt[r][i] - cnt[l - 1][i]);
53
        cout << res << endl;
54
    }
55
}
56

57
int main()
58
{
59
    fastio();
60

61
    int T = 1;
62
    // cin >> T;
63

64
    while (T--)
65
        solve();
66

67
    return 0;
68
}

L - 三人成角#

关键词：思维

思路#

题目是：在 $N$ 个等距圆周点中选 $3$ 个点，问有多少种选法构成直角三角形；且选法只看最终选中的 $3$ 把椅子，不区分人坐哪一把。

注意到直径所对的圆周角为 $90$ 度，分奇偶考虑。

当 $n$ 为偶数的时候，每个点都有一个正对点，对于每一条直径，第三个点从剩下的 $n-2$ 个点中任选，答案为 $\frac {n(n-2)}{2}$ 。

而奇数点时，圆周上不存在正对着的两把椅子，答案为 $0$ 。

Code#

1
// Problem: CF GYM 106554 L
2
// Contest: Codeforces - [Unofficial Mirror] 2026 CCPC National Invitational (Nanchang) and The 3rd Jiangxi Provincial
3
// Programming Contest URL: https://codeforces.com/gym/106554/problem/L Time: 2026-05-29 18:44:32
4
#include <bits/stdc++.h>
5
using namespace std;
6

7
// clang-format off
8
#define endl '\n'
9
#define all(x) (x).begin(), (x).end()
10
#define fastio() ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
11
// clang-format on
12

13
using ll = long long;
14
using ull = unsigned long long;
15
using pii = pair<int, int>;
16
using pdd = pair<double, double>;
17
using pll = pair<long long, long long>;
18
using i128 = __int128;
19

20
const int dx[] = {-1, 0, 1, 0, -1, 1, 1, -1};
21
const int dy[] = {0, 1, 0, -1, 1, 1, -1, -1};
22
const int inf = 0x3f3f3f3f;
23
const int N = 0;
24

25
void solve()
26
{
27
    ll n;
28
    cin >> n;
29

30
    ll res = (n % 2 == 1 ? 0 : n * (n - 2) / 2);
31
    cout << res << endl;
32
}
33

34
int main()
35
{
36
    fastio();
37

38
    int T = 1;
39
    cin >> T;
40

41
    while (T--)
42
        solve();
43

44
    return 0;
45
}