巅峰赛 #37 题解 | 非官方

userId_undefined
杰杰
8月全勤卷王出道萌新秩序白银勇敢小狗快乐小狗GESP5级

2026-08-18 20:40:10

发布于：香港

7阅读
0回复
0点赞

巅峰赛 #37 题解 | 非官方

本次题目猜测的总体难度如下，仅供参考：

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

T1. 午枫的幸运名单

题目大意

给一个正整数 nn 和 nn 个 字符串 SiS_i，并且给出一个 PP，判断 PP 是否在字符串中出现过，并且输出出现的位置的 ii，如果没有出现则输出 -1。

解题思路

对于每一个输入的时候，直接判断输入的字符串是否等于 PP 即可，但是如果用 solve\mathrm{solve} 的话，需要把答案记录下来，不能直接输出。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
// const int MOD = 1e9 + 7;
 
void solve() {
    int n; string p;
    cin >> n >> p;

    int ans = -1;
    for(int i = 1; i <= n; i++) {
        string x; cin >> x;
        if(p == x) {
            ans = i;
            // 不能直接输出，不然输入会乱掉
        }
    }

    cout << ans << endl;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;

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

单组测试样例时间复杂度：O(n)O(n)

T2. 宝藏密码

题目大意

给你 nn 条公式，每一条公式有一个共同解 xx，而方程为 aix+bi=cia_ix + b_i = c_i，其中 ai,bi,cia_i, b_i, c_i 的位置可以调换。

解题思路

得出 xx 所表示：

aix+bi=cia_ix + b_i = c_i

aix=ci−bia_ix = c_i-b_i

x=ci−biaix = \dfrac{c_i-b_i}{a_i}

可以把所有 ui,vi,wiu_i, v_i, w_i 可能的 ai,bi,cia_i, b_i, c_i 枚举出来。如果 ci−bimod  ai=0c_i-b_i\mod a_i=0，则可以将这个答案压入一个 vector\mathrm{vector}，然后去重。由于答案为一，所以判断是否满足 aix+bi=cia_ix+b_i=c_i 即可。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
// const int MOD = 1e9 + 7;

int a[N], b[N], c[N];
vector<int> s;

bool check(int x, int u, int v, int w) {
    if(u * x + w == v || u * x + v == w || v * x + u == w || v * x + w == u || w * x + u == v || w * x + v == u) return true;
    return false;
}

void solve1(int a, int b, int c) {
    if((c - b) % a == 0) {
        int x = (c - b) / a;
        if(x >= 0) {
            s.push_back(x);
        }
    }
}

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

    s.clear();

    for(int i = 1; i <= n; i++) {
        cin >> a[i] >> b[i] >> c[i];
    }

    solve1(a[1], b[1], c[1]);
    solve1(a[1], c[1], b[1]);
    solve1(b[1], a[1], c[1]);
    solve1(b[1], c[1], a[1]);
    solve1(c[1], a[1], b[1]);
    solve1(c[1], b[1], a[1]);

    sort(s.begin(), s.end());
    s.erase(unique(s.begin(), s.end()), s.end());

    for(auto x : s) {
        bool ok = true;
        for(int i = 1; i <= n; i++) {
            if(!check(x, a[i], b[i], c[i])) {
                ok = false;
                break;
            }
        }
        if(ok) {
            cout << x << endl;
            return ;
        } 
    }
    cout << -1 << endl;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int t; cin >> t;
    while(t--) solve();
    return 0;
}

单组测试样例时间复杂度：O(n)O(n)

T3. 午枫的宝藏

题目大意

有 nn 个人。船长可以提出一个分配方案，如果投票超过半数则成功，否则船长被杀死。所有水手聪明、贪婪、互不信任，每个人在保证自己不被杀的前提下争取最大利益。求每个人能获取的金（不包括船长），且能保证自己活下来。压缩答案为：

R=(∑i=1ni×ri)mod  (109+7)R = (\sum_{i=1}^n i \times r_i) \mod (10^9+7)

解题思路

假设现在有 11 个人（不包括船长），那么他肯定投自己一票，票数过半，所以可以给自己利益最大化。

假设现在有 22 个人（不包括船长），那船长只需要令其中一个人同意，所以会给 22 号水手 11 个金，可以令 22 号水手举手。由于如果 22 号水手不同意，11 号水手就会决定分配，而 22 号水手则一点金都拿不到，所以 22 号水手一定会同意。得出 rr 数组：

0,1,0,1,0,1,⋯0, 1, 0, 1, 0, 1, \cdots

接下来压缩答案，只有双数位的 rir_i 才会对答案有贡献，所以如果 nn 为偶数，则答案为 2+4+⋯+n2+4+\cdots+n；否则答案为 2+4+⋯+(n−1)2+4+\cdots+(n-1)，而公式则为 n×(n+2)4\dfrac{n\times (n + 2)}{4}。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
//const int MOD = 998244353;
const int MOD = 1e9 + 7;
 
void solve() {
    int n; cin >> n;

    int inv = 250000002;

    if(n % 2 == 1) n -= 1;

    cout << (n % MOD * (n + 2) % MOD) * inv % MOD << endl;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;

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

单组测试样例时间复杂度：O(1)O(1)

T4. 午枫的罗盘

题目大意

有 nn 条线，相邻两条线之间的夹角为 180∘k\dfrac{180^\circ}{k}，求有多少对垂直的线。

解题思路

首先观察题目，如果 kk 是奇数是不可能有任何垂直的线。且如果 n<k2n < \dfrac{k}{2}，则不可能有垂直的线。

和 00 垂直的第一条线为 k2\dfrac{k}{2}。设 aa 为 00 垂直的最后一条线，bb 为与 00 垂直的线的组数。则对与所有都有 (a−k2+1)×b(a - \dfrac{k}{2}+1)\times b。而还有多余的线（n−an-a）， (a+1,a+1+k)(a + 1, a + 1 + k) 的区间有 (b−1)(b-1) 条线；(a+1+k,a+1+2k)(a + 1+k,a+1+2k) 的区间有 (b−2)(b-2) 条线。则是每一组就有 (b−1)×k,(b−2)×k(b-1)\times k, (b-2)\times k，提取 kk 出来则是 k×(b−1)+(b−2)+(b−3)+(b−4)+⋯+1k\times(b-1)+(b-2)+(b-3)+(b-4)+\cdots+1，项数为 n−(a+1)k\dfrac{n-(a+1)}{k}。最后运用（首项+末项）×项数2\dfrac{（首项 + 末项）\times 项数}{2}，求出答案即可。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
// const int MOD = 1e9 + 7;
 
void solve() {
    int n, k; cin >> n >> k;

    if(k % 2 == 1) {
        cout << 0 << endl;
        return ;
    } else if(n < k / 2) {
        cout << 0 << endl;
        return ;
    }

    int a = k / 2 + (n - k / 2) % k - 1;
    int b = (n - k / 2) / k + 1;

    int res = (a - k / 2 + 1) * b;

    int cnt = max(0LL, (n - (a + 1)) / k);
    res += (((b - 1) + (b - cnt)) * cnt / 2) * k;

    cout << res << endl;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;

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

单组测试样例时间复杂度：O(1)O(1)

T5. 午枫的航海日志

题目大意

有 nn 个数，有多少组数对 (p,q)(p,q)，使得序列存在 p,0,p,qp,0,p,q。

解题思路

考虑这个问题可以先问一些问题：

  • 对于每一个 pp，应该选哪一个 00？当然是离 pp 最近的那个 00，可以最大化后面 qq 的个数。
  • 对于每一个 00，应该选哪一个 pp？当然是离 00 最近的那个 pp，可以最大化后面 qq 的个数。

我们可以用一个 suff\mathrm{suff} 数组，表示从当前位置到序列末尾有多少个不同数字个数，而且要记录下来每一个数字出现的位置。我们可以用 lower_bound 来查找后面的下标，再处理一下特殊情况就可以了。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 1000010;
const int MOD = 998244353;
// const int MOD = 1e9 + 7;
 
int a[N], s[N];
map<int, int> mp, vis, vis1;
vector<int> v, ve[N], cnt;

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

    mp.clear();
    vis.clear();
    v.clear();
    cnt.clear();
    vis1.clear();

    for(int i = 0; i <= N; i++) ve[i].clear();

    for(int i = 1; i <= n; i++) {
        cin >> a[i];
        if(a[i] == 0) v.push_back(i);

        ve[a[i]].push_back(i);

        if(vis.count(a[i]) == 0) cnt.push_back(a[i]);
        vis[a[i]]++;
    }

    s[n] = 0;
    for(int i = n - 1; i >= 1; i--) {
        if(mp.count(a[i + 1])) s[i] = s[i + 1];
        else if(a[i + 1] > 0) s[i] = s[i + 1] + 1;
        else s[i] = s[i + 1];

        mp[a[i + 1]]++;
    }

    int res = 0;
    for(int i = 0; i < cnt.size(); i++) {
        int num = cnt[i];
        if(num == 0) continue;

        int d = lower_bound(v.begin(), v.end(), ve[num][0]) - v.begin();
        if(d == v.size()) continue;

        int num1 = lower_bound(ve[num].begin(), ve[num].end(), v[d]) - ve[num].begin();
        if(num1 == ve[num].size()) continue;

        res += s[ve[num][num1]];
    }

    cout << res << endl;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;

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

单组测试样例时间复杂度：O(N×nlog⁡n)O(N \times n \log n)。

T6. 午枫的密码本

题目大意

给定一个字符串 SS，将其拼接 kk 次得出 S′S'，求 S′S' 的 ASCII\mathrm{ASCII} 值的最长上升子序列的长度。

解题思路

首先看到 kk 的最大值为 1010010^{100}，所以显然不能直接暴力拼接，考虑优化。假设字符串 SS 为 zyxwvutsrqponmlkjihgfedcba，kk 为 1010010^{100}，结果的值为 2626。由此得知，答案最大为 2626，因为是严格上升子序列，而英文字母只有 2626 个。所以 SS 拼接 2626 次就可以了。

怎么判断 kk 是否大于 2626 呢？kk 是字符串，无法直接判断。我们可以先看 kk 的长度。如果大于 22 则一定是拼接 2626 次。如果小于，直接换成 int 判断就行了。

最后，使用 dp\mathrm{dp} 求最长上升子序列即可。

参考代码

#include <bits/stdc++.h>
#define int long long
#define PII pair<int, int>
#define fi first
#define se second
using namespace std;
const int N = 200010;
const int MOD = 998244353;
// const int MOD = 1e9 + 7;
 
void solve() {
    string s, k;
    cin >> s >> k;
    int l = 0;

    if(k.size() > 2) l = 26;
    else if(stoi(k) > 26) l = 26;
    else l = stoi(k);
    
    string d = s;
    
    for(int i = 1; i < l; i++) {
		s += d;
    }

    s = ' ' + s;
    
    int dp[N];
    int a[N];

    for(int i = 0; i <= s.size() + 1; i++) {
        dp[i] = a[i] = 0;
    }
	
    for(int i = 1; i <= s.size(); i++) {
        dp[i] = 1;
        a[i] = s[i] - 'a';
        for(int j = 1; j < i; j++) {
            if(a[j] < a[i]) {
                dp[i] = max(dp[i], dp[j] + 1);
            }
        }
    }
    
    cout << *max_element(dp + 1, dp + s.size() + 1) << endl;
}
 
signed main() {
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    int T = 1;
    cin >> T;

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

时间复杂度：O(m2)O(m^2)，其中 mm 为拼接后字符串的长度。

userId_undefined
去预览
0/2000
暂无数据

这里空空如也

热门讨论