官方题解 | 巅峰赛#37

NoonMaple

2026-08-18 10:10:36

发布于：浙江

43阅读

0回复

0点赞

巅峰赛37题解

本次题目的总体难度如下，各位选手可以借此评估一下自身的技术水平

题目编号	题目标题	难度
T1	午枫的幸运名单	普及/提高-
T2	宝藏密码	普及/提高-
T3	午枫的宝藏	普及/提高-
T4	午枫的罗盘	普及/提高-
T5	午枫的航海日志	普及+/提高
T6	午枫的密码本	普及+/提高

T1 午枫的幸运名单

题意简述

给定一份长度为 $n$ 的名单以及午枫的名字 $P$ 。

依次查看名单中的名字，如果找到与 $P$ 相同的名字，则输出其所在位置（排名）；如果遍历完整个名单仍未找到，则输出 -1。

解题思路

直接模拟查找即可。

读入午枫的名字后，依次读取名单中的每个名字，判断是否与目标名字相同。由于名单中的名字互不相同，因此最多只会匹配一次。

记录匹配到的位置，最后输出对应排名；若始终未匹配到，则输出 -1。

时间复杂度为 O(n)。

参考代码

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

void solve() {
   int n;
   string target;
   cin >> n >> target;

   int answer = -1;

   for (int i = 1; i <= n; i++) {
       string name;
       cin >> name;

       if (name == target) {
           answer = i;
       }
   }

   cout << answer << '\n';
}

int main() {
   ios::sync_with_stdio(false);
   cin.tie(nullptr);

   int T;
   cin >> T;

   while (T--) {
       solve();
   }

   return 0;
}

T2 宝藏密码

题意简述

给定 $n$ 条形如 $a_i x + b_i = c_i$ 的方程，但 $a_i, b_i, c_i$ 与输入的三个数 $u_i, v_i, w_i$ 对应关系未知（共有 $6$ 种可能的排列）。已知存在唯一的非负整数 $x$ 同时满足所有方程（在合适的排列下），求这个 $x$ 。

解题思路

由于每个方程只有 $6$ 种可能的排列方式，我们可以枚举第一条方程的所有排列，对每种排列解出 $x$ （若该排列对应方程 $a x + b = c$ 有整数解且 $x \ge 0$ ），然后验证这个 $x$ 是否满足其余所有方程（每条方程存在一种排列使得等式成立）。由于解唯一，最多验证 $6$ 次即可找到答案。复杂度 $O(6n)$ 。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<tuple<long long, long long, long long>> eq(n);
        for (int i = 0; i < n; i++) {
            long long u, v, w;
            cin >> u >> v >> w;
            eq[i] = {u, v, w};
        }
        
        auto [u0, v0, w0] = eq[0];
        
        auto check = [&](long long x) -> bool {
            for (auto [u, v, w] : eq) {
                if (u * x + v == w) continue;
                if (u * x + w == v) continue;
                if (v * x + u == w) continue;
                if (v * x + w == u) continue;
                if (w * x + u == v) continue;
                if (w * x + v == u) continue;
                return false;
            }
            return true;
        };
        
        long long ans = -1;
        
        if ((w0 - v0) % u0 == 0) {
            long long x = (w0 - v0) / u0;
            if (x >= 0 && check(x)) ans = x;
        }
        if ((v0 - w0) % u0 == 0) {
            long long x = (v0 - w0) / u0;
            if (x >= 0 && check(x)) ans = x;
        }
        if ((w0 - u0) % v0 == 0) {
            long long x = (w0 - u0) / v0;
            if (x >= 0 && check(x)) ans = x;
        }
        if ((u0 - w0) % v0 == 0) {
            long long x = (u0 - w0) / v0;
            if (x >= 0 && check(x)) ans = x;
        }
        if ((u0 - v0) % w0 == 0) {
            long long x = (u0 - v0) / w0;
            if (x >= 0 && check(x)) ans = x;
        }
        if ((v0 - u0) % w0 == 0) {
            long long x = (v0 - u0) / w0;
            if (x >= 0 && check(x)) ans = x;
        }
        
        cout << ans << '\n';
    }
    return 0;
}

T3 午枫的宝藏

题意简述

有 $n$ 名水手（不包括船长），按顺位 $1$ 到 $n$ 继承。船长提出分配金币方案，全员（包括船长）投票。若半数及以上通过则执行，否则船长被处死，由第 $1$ 顺位继承人接任并重新分配，以此类推。所有水手聪明、贪婪、互不信任，每个人在保证自己不被杀的前提下争取最大利益。求船长在保证自己存活的前提下分出去的最少金币总数，并按 $R = \left( \sum_{i=1}^n i \cdot r_i \right) \bmod (10^9+7)$ 输出，其中 $r_i$ 是分配给第 $i$ 顺位继承人的金币数。

解题思路

从少到多递推。记总人数为 $n+1$ （包括船长）。当只有船长一人（ $n=0$ ）时，不需要分金币。对于 $n$ 人情况，船长需要争取半数以上票（包括自己）。由于第 $1$ 顺位继承人在下一轮会成为船长，他一定会反对当前船长的提案（因为反对后自己就能掌权）。因此船长只能拉拢后面的人。

通过归纳可以发现，最终分配方案为：第 $i$ 顺位继承人得到 $1$ 枚金币当且仅当 $i$ 为偶数，否则得到 $0$ 枚。即 $r_i = 1$ 当 $i$ 为偶数， $r_i = 0$ 当 $i$ 为奇数。因此需要计算 $\sum_{i=1}^n i \cdot [i \text{ 为偶数}] = 2 + 4 + 6 + \dots$ ，共 $\lfloor n/2 \rfloor$ 项。该和为 $\lfloor n/2 \rfloor \times (\lfloor n/2 \rfloor + 1)$ 。

参考代码

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

const int MOD = 1e9 + 7;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        long long n;
        cin >> n;
        long long m = n / 2;
        long long ans = m % MOD * ((m + 1) % MOD) % MOD;
        cout << ans << '\n';
    }
    return 0;
}

T4 午枫的罗盘

题意简述

有 $n$ 条刻度线 $l_0, l_1, \dots, l_{n-1}$ ，其中 $l_0$ 为起始线， $l_i$ 由 $l_{i-1}$ 逆时针旋转 $\frac{180^\circ}{k}$ 得到。求有多少对 $(i,j)$ （ $0 \le i < j < n$ ）使得 $l_i \perp l_j$ 。

解题思路

两条线垂直当且仅当它们的夹角为 $90^\circ$ 的奇数倍。由于每次旋转 $\frac{180^\circ}{k}$ ， $l_i$ 与 $l_0$ 的夹角为 $i \cdot \frac{180^\circ}{k}$ 。 $l_i \perp l_j$ 等价于 $|i-j| \cdot \frac{180^\circ}{k} \equiv 90^\circ \pmod{180^\circ}$ ，即 $|i-j| \equiv \frac{k}{2} \pmod{k}$ 。因此 $k$ 必须为偶数才有解，否则答案为 $0$ 。

当 $k$ 为偶数时，令 $d = k/2$ 。条件化为 $|i-j| \equiv d \pmod{k}$ 。由于 $0 \le i,j < n$ ，考虑将 $i$ 按模 $d$ 分组，每组内下标相差 $d$ 的倍数。实际上， $l_i$ 与 $l_{i+d}$ 垂直，与 $l_{i+3d}$ 也垂直，等等。统计所有满足 $i + t \cdot d < n$ 的对数即可。更简单的方法：将 $n$ 条线按模 $d$ 分成 $d$ 组，每组有 $\lfloor n/d \rfloor$ 或 $\lfloor n/d \rfloor + 1$ 条线。每组的贡献为该组内任取两条线的组合数？不对，垂直并不发生在同组内，而是发生在相隔 $d$ 的倍数且差为奇数倍 $d$ 的组之间？实际上 $l_i$ 与 $l_j$ 垂直当且仅当 $i-j$ 是 $d$ 的奇数倍。因此对于每组模 $d$ 的同余类，它们内部相邻的线差恰好是 $d$ ，但垂直要求差为 $d, 3d, 5d, \dots$ 。每个同余类内部，若按顺序排列，第 $p$ 条线与第 $p+1$ 条线垂直，与第 $p+2$ 条线差 $2d$ 不垂直，与第 $p+3$ 条线垂直，以此类推。因此每个同余类中，将线按顺序编号 $0,1,\dots, m-1$ ，则一对线 $(u,v)$ 满足 $|u-v|$ 为奇数即垂直。该同余类内的垂直对数为 $\lfloor m/2 \rfloor \times \lceil m/2 \rceil$ 。将所有同余类的贡献相加即可。

设 $a = \lfloor n/d \rfloor$ ， $b = n \bmod d$ ，则 $b$ 个组有 $a+1$ 条线， $d-b$ 个组有 $a$ 条线。答案为：

$b \cdot \left\lfloor \frac{a+1}{2} \right\rfloor \cdot \left\lceil \frac{a+1}{2} \right\rceil + (d-b) \cdot \left\lfloor \frac{a}{2} \right\rfloor \cdot \left\lceil \frac{a}{2} \right\rceil$

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        long long n, k;
        cin >> n >> k;
        if (k % 2 == 1) {
            cout << "0\n";
            continue;
        }
        long long d = k / 2;
        long long a = n / d;
        long long b = n % d;
        auto f = [](long long x) {
            return (x / 2) * ((x + 1) / 2);
        };
        long long ans = b * f(a + 1) + (d - b) * f(a);
        cout << ans << '\n';
    }
    return 0;
}

T5 午枫的航海日志

题意简述

给定长度为 $n$ 的序列 $a$ ，求有多少种不同的正整数对 $(p,q)$ ，使得序列中存在一个子序列（不连续）恰好为 $p, 0, p, q$ 。

解题思路

我们需要找到所有满足条件的 $(p,q)$ 。枚举 $p$ 和 $q$ 不可行，考虑枚举子序列中第一个 $p$ 和第二个 $p$ 的位置。设第一个 $p$ 在位置 $i$ ，第二个 $p$ 在位置 $j$ （ $i<j$ ），并且它们之间至少有一个 $0$ 。同时，在 $j$ 之后需要存在一个 $q$ （ $q \ge 1$ ）。由于 $q$ 可以是任意正整数，实际上只要 $j$ 之后存在任意一个正整数（ $>0$ ）即可，因为 $q$ 可以取那个正整数的值。但注意 $q$ 必须与 $p$ 独立，且 $(p,q)$ 只计一次。

更直接的做法：对于每个 $p$ ，考虑它出现的所有位置。我们需要两个 $p$ 的位置中间有 $0$ ，且第二个 $p$ 之后有正整数。如果存在这样的两个 $p$ ，那么所有出现在第二个 $p$ 之后的正整数都可以作为 $q$ 。因此对每个 $p$ ，贡献的 $q$ 的数量等于第二个 $p$ 之后的不同正整数的个数。为了去重，我们应当对每个 $p$ 统计它能产生的 $q$ 的集合，最后累加不同 $(p,q)$ 的数量。

由于 $a_i \le 10^6$ ，可以枚举 $p$ 。对于每个 $p$ ，找到第一个 $0$ 位于两个 $p$ 之间的可行方案。设 $p$ 的出现位置为 $pos_1, pos_2, \dots$ 。如果存在 $pos_t$ 和 $pos_{t+1}$ 使得 $pos_{t+1} > pos_t$ 且区间 $(pos_t, pos_{t+1})$ 内包含至少一个 $0$ ，那么 $pos_{t+1}$ 之后的所有正整数都可以作为 $q$ 。因此我们只需要记录每个 $p$ 的“最早”满足条件的第二个 $p$ 的位置，然后统计该位置之后的不同正整数个数。可以用后缀预处理每个位置之后的不同正整数的数量（注意只统计正整数，不包括 $0$ ）。最后对每个 $p$ 累加即可。

参考代码

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

const int N = 1e6 + 5;
int a[N], suf[N];
bool vis[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        for (int i = 1; i <= n; i++) {
            cin >> a[i];
        }
        
        vector<int> pos[N];
        for (int i = 1; i <= n; i++) {
            if (a[i] > 0) pos[a[i]].push_back(i);
        }
        
        // 后缀中不同正整数的数量
        int cnt = 0;
        memset(vis, 0, sizeof(vis));
        for (int i = n; i >= 1; i--) {
            if (a[i] > 0 && !vis[a[i]]) {
                vis[a[i]] = true;
                cnt++;
            }
            suf[i] = cnt;
        }
        
        long long ans = 0;
        for (int p = 1; p <= 1000000; p++) {
            if (pos[p].size() < 2) continue;
            int best = n + 1;
            for (int t = 0; t < (int)pos[p].size() - 1; t++) {
                int i = pos[p][t], j = pos[p][t + 1];
                // 检查 i 和 j 之间是否有 0
                bool ok = false;
                for (int k = i + 1; k < j; k++) {
                    if (a[k] == 0) {
                        ok = true;
                        break;
                    }
                }
                if (ok) {
                    best = min(best, j);
                }
            }
            if (best <= n) {
                ans += suf[best + 1];
            }
        }
        cout << ans << '\n';
    }
    return 0;
}

T6 午枫的密码本

题意简述

给定字符串 $S$ 和一个极大的整数 $k$ ，将 $S$ 重复拼接 $k$ 次得到 $S'$ ，求 $S'$ 的最长严格递增子序列（LIS）的长度。

解题思路

当 $k\ge |\Sigma|$ （即 $k\ge 26$ ）时，可以从不同重复中分别取每个字母，从而得到所有不同字母，答案为 $S$ 中不同字母的种类数。
当 $k<26$ 时，暴力构造 $S'=S$ 重复 $k$ 次，长度不超过 $2600$ ，直接 DP 求 LIS 即可。
由于 $k$ 以字符串形式给出，若其长度 $>2$ 或数值 $\ge 26$ 则按第一种情况处理，否则转整数后暴力。

参考代码

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        string s, ks;
        cin >> s >> ks;
        
        set<char> st(s.begin(), s.end());
        int m = st.size();
        
        if (ks.size() > 2 || (ks.size() == 2 && (ks[0] > '2' || (ks[0] == '2' && ks[1] > '5')))) {
            cout << m << '\n';
            continue;
        }
        
        int k = stoi(ks);
        string t;
        for (int i = 0; i < k; i++) t += s;
        
        int n = t.size();
        vector<int> dp(n, 1);
        int ans = 1;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (t[j] < t[i]) {
                    dp[i] = max(dp[i], dp[j] + 1);
                }
            }
            ans = max(ans, dp[i]);
        }
        cout << ans << '\n';
    }
    return 0;
}