非官方题解 | 巅峰赛#37题解除去T5

userId_undefined
sczans.(3/4退站)
出道萌新7月全勤卷王时空双修者贪心·贪心尝试者

2026-08-30 14:21:56

发布于：天津

4623阅读
0回复
0点赞

反馈BUG的帖子

巅峰赛#37题解（没有T5因为不会）

注意：1.这个不是官方题解！2.思路可能不是最优！

1.午枫的幸运名单（实际上并不难。）

思路：

对于每组数据：

  • 输入 n 和 p；
  • 设置标记变量；
  • 输入 n 个字符串，如果和 p 相等直接输出 i（循环变量，从1开始）并标记=1；
  • 输入完了，没有匹配到，即标记变量=0，就输出-1。

我的代码：

#include<iostream>
#include<string>
using namespace std;
int main(){
    int t;
    cin>>t;
    while(t--){
        int num;cin>>num;
        string ren;cin>>ren;
        bool flag=0;
        for(int i=1;i<=num;i++){
            string tp;cin>>tp;
            if(tp==ren){
                    cout<<i<<endl;
                    flag=1;
            }
        }
        if(!flag){
            cout<<-1<<endl;
        }
    }
return 0;
}

2.宝藏密码

思路：

合法解指的是非负的整数解(即 x∈Nx∈N )。

  • 如果只有1个方程，那么直接遍历6种排列求解。因为题目保证只有一个合法解。
  • 如果有多个方程：
  1. 遍历第一个方程的6种情况
  2. 第一个方程如果出现了合法解，那么再去验证其他方程（每个方程须要验证6种排列），看看是不是通解
  3. 如果不是通解，那么再重解第一个方程。
  4. 最后通解就是最终答案

我的代码：

#include<iostream>
using namespace std;
typedef long long _;
struct funk{//一个方程有6种情况
    _ a[7];
    _ b[7];
    _ c[7];
     
}fangcheng[100002];
bool z(long long a,long long b,long long c){//解是非负整数并且合法
    if(a!=0)return (c-b)%a==0&&(c-b)/a>=0;
    return 0;
}
int main(){
    _ t;cin>>t;
    while(t--){
        _ n;cin>>n;
        for(int i=1;i<=n;i++){
            _ a,b,c;
            cin>>a>>b>>c;
            fangcheng[i].a[1]=a;fangcheng[i].a[2]=a;//傻子式生成6种排列（如果比赛了真不会可以这么做）
            fangcheng[i].a[3]=b;fangcheng[i].a[4]=b;
            fangcheng[i].a[5]=c;fangcheng[i].a[6]=c;
            fangcheng[i].b[1]=b;fangcheng[i].b[2]=c;
            fangcheng[i].b[3]=a;fangcheng[i].b[4]=c;
            fangcheng[i].b[5]=a;fangcheng[i].b[6]=b;
            fangcheng[i].c[1]=c;fangcheng[i].c[2]=b;
            fangcheng[i].c[3]=c;fangcheng[i].c[4]=a;
            fangcheng[i].c[5]=b;fangcheng[i].c[6]=a;
        }
        _ ans=0;
        if(n==1){
            for(int j=1;j<=6;j++){
                _ a=fangcheng[1].a[j];
                _ b=fangcheng[1].b[j];
                _ c=fangcheng[1].c[j];
                if(z(a,b,c)){
                    ans=(c-b)/a;
                    break;
                }
            }
        }
        else if(n>1){
            for(int q=1;q<=6;q++){//先解第一个方程
                _ a=fangcheng[1].a[q];
                _ b=fangcheng[1].b[q];
                _ c=fangcheng[1].c[q];
                if(z(a,b,c)){//出现合法解
                    _ jietmp=(c-b)/a;
                    for(int i=2;i<=n;i++){//解其他方程
                        bool v=0;
                        for(int j=1;j<=6;j++){
                            _ aa=fangcheng[i].a[j];
                            _ bb=fangcheng[i].b[j];
                            _ cc=fangcheng[i].c[j];
                            if(z(aa,bb,cc)&&(cc-bb)/aa==jietmp){
                                ans=(cc-bb)/aa;
                                v=1;
                                break;   
                            }
                        }
                        if(!v){//没找到通解，退出，解第一个方程的其他解
                            break;
                        }
                    }
                }
            }
        }
        cout<<ans<<endl;
    }
    return 0;
}

3.午枫的宝藏

思路：

这道题就一个公式。（不会用LaTex......）

n取模2=0→ans=n∗(n+2)/4;n取模2=0→ans=n*(n+2)/4;
else→ans=(n+1)∗(n−1)/4;else→ans=(n+1)*(n-1)/4;

那么是怎么推导出来的呢？

  • 当n为偶数：争取n/2名水手支持，选择编号为偶数的水手每人分1金币。答案为n(n+2)/4（等差数列）。
  • 当n为奇数：争取(n-1)/2名水手支持，选择编号为偶数的水手每人分1金币。答案(n+1)*(n-1)/4。（等差数列）

代码就2个公式自己写。

4.午枫的罗盘

思路

（只给出一个公式，具体怎么出的......举了几个例子，一个一个数，发现总和是几个0 加上 等差数列 加上 几个floor((num−1.5∗k)/k)floor((num-1.5*k)/k)+2，然后用奥数知识推导的公式。导出来后，一晚上没睡着。）

注意看题

只要满足i<j就行，这是容易出错的。如果刻度转了大于一圈可以和底下一圈的刻度形成直角，同理\color{red}{只要满足 i<j 就行，这是容易出错的。如果刻度转了大于一圈可以和底下一圈的刻度形成直角，同理}
如果刻度转了大于2圈可以和底下2圈的刻度都形成直角\color{red}{如果刻度转了大于2圈可以和底下2圈的刻度都形成直角}

同时，看到T好大，当时 xkl，但也说明我们的时间复杂度必须压到O(1)O(1)！然后想到推导公式
首先想，k是奇数可能出现直角吗。
答案肯定是不能。学过旋转（小学入门，9年级进阶）的都知道这件事情

——题外话部分开始

当时我用了好几张纸，出了这个公式（你们要信我我导了一晚上推导出了这个雷霆公式）：

long long n=floor((num-1.5*k)/k)+2;
long long ans=k*n*(n-1)/2+n*num-k*n*n+0.5*k*n+n;

但是，估计可能也许大概 溢出了，95pts.（别笑我）

             细节版本10↓

然后依旧化简了1小时，又双叒[我找不到chuo]用了好几张纸，出了这个公式

——题外话部分结束

式子：

            long long q=num/k,r=num%k;
            if(2*r<k) ans=q*(k*q+2*r+2)/2;
            else ans=(q+1)*(k*(q-1)+2*r+2)/2;
            cout<<ans<<endl;
            continue;

然后100pts；

我的代码

#include<iostream>
#include<cmath>
using namespace std;
int main(){
    int t;cin>>t;
    while(t--){
        int num,k;
        cin>>num>>k;
        num--;//因为我的公式，从0开始算的，所以要-1(当时我没减，错了，老师了)
        if(k%2==0){ //偶数能凑！
            long long q=num/k,r=num%k,ans=0;
            if(2*r<k) ans=q*(k*q+2*r+2)/2;
            else ans=(q+1)*(k*(q-1)+2*r+2)/2;
            cout<<ans<<endl;
            continue;
        }
        cout<<0<<endl;//奇数的话是不可能凑得直角
    }
    return 0;
}

5.我不会做，所以看官方题解。

6.午枫的密码本

个人感觉出简单了

思路：

不要看到 k≤10100k≤10^{100} 就吓*了。

想这样一个问题：当 k 大于或等于 [不同字符数] 时会发生什么。（想通了你就会做这道题了）
答案是 LIS 就等于 [不同字符数] 。为什么呢？因为对于每个重复出现的字符串可以选择任意一个字符，我们就可以

  • 第一轮，选择ASCLL最小的字符；
  • 第二轮，选择ASCLL第二小的字符；
    ......
  • 第 [不同字符数] 轮，选择ASCLL最大的字符。

这样，k 大于或等于 [不同字符数] 时，答案是 [不同字符数] 。

那么如果k不大怎么办，直接用O(nlogn)O(nlogn)的LIS方式求解！（应该都背下来了）
为什么不会超时？因为：最多不同字符只有不到 100 个，而字符串长度小于 100.

我的代码：（留了很多优化空间）

#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
string dif(string a){                            //算不同字符数量，用桶，注意返回值是string以便比较大小
    int tong[129];
    for(int i=0;i<129;i++)tong[i]=0;
    for(int i=0;i<a.size();i++)tong[a[i]]++;
    int ans=0;
    for(int i=0;i<129;i++)if(tong[i])ans++;
    string anss=to_string(ans);
    return anss;
}
int lis(string a){                     //正常LIS
    char t[20005];int l=0;
    for(int i=1;i<=a.size();++i){
        char*p=lower_bound(t,t+l,a[i]);
        if(p==t+l)t[l++]=a[i];
        else*p=a[i];
    }
    return l;
}
bool daxiao(string a,string b){     //比大小，但是不能直接比较因为直接比较比的是 字典序。这个害得我多错一次（bushi）
    if(a.size()!=b.size())return a.size()>b.size();
    return a>=b;
}
signed main(){
    int t;
    cin>>t;
    while(t--){
        string a,k;
        cin>>a>>k;
        string ab=' '+a;
        //处理k大的情况
        string butongzifugeshu=dif(a);
        if(daxiao(k,butongzifugeshu)){
            cout<<butongzifugeshu<<endl;
            continue;
        }
        //转成数字此时k小于100，原因见思路;
        int kt=0;
        for(int i=0;i<k.size();i++){
            kt+=int(k[i]-48);
            if(i!=k.size()-1)kt*=10;
        }
        //算S'
        for(int i=1;i<kt;i++)ab+=a;
        cout<<lis(ab)<<endl;
    }
}

又及：
是不是出简单了让我一小 * 孩第一次参加比赛得500多分
浅浅预测一下难度（bushi）：
这里把普及/提高-拆成了普及 和 普及+/提高-

题目 难度 我的得分
1 普及−\color{orange}\boxed{普及-} 100\color{green}{100}
2 普及\color{yellow}\boxed{普及} 100\color{green}{100}
3 普及+/提高−\color{green}\boxed{普及+/提高-} 100\color{green}{100}
4 普及\color{yellow}\boxed{普及} 100\color{green}{100}
5 提高\color{cyan}\boxed{提高} 10\color{red}{10}
6 普及+/提高−\color{green}\boxed{普及+/提高-} 100\color{green}{100}
总分、排名 510\color{green}{510} 50\color{green}{50}

这题解只要我在任何地方以任何形式用AI我就*全家

userId_undefined
去预览
0/2000

全部评论 320

热门讨论