第九届GPLT团体程序设计天梯赛2024年

2024天梯赛

英雄这里出来

1726人浏览 · 2024-04-21 22:56:51

英雄这里出来 · 2024-04-21 22:56:51 发布

第九届GPLT团体程序设计天梯赛2024年

不知道故事的开始还可以忍受，不知道故事的结束及其难受。

——余华

以此篇记录我遗憾的天梯赛吧，抱歉给队友拖后腿了。

这次天梯赛时间分配很有问题，前面L1的字符串题目太搞人心态了，一直会有差一两分的题目，几组数据没通过，然后就调试了很久还是没有调试出来，浪费了很多时间，中间还掉线一次。最后做到L2的时候只有三十多分钟了，所以后面写的一塌糊涂，L2-2能写出来但是二十多分钟没调对，码力还是不够啊，L2-3写起来要快一点，可惜当时就想把L2-2做出来，结束后晚上做了两个L2的题目，都还是不难，稍微调试一下得到了23分和25分。

L1-1 编程解决一切

L1-097 编程解决一切 - 团体程序设计天梯赛-练习集 (pintia.cn)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    cout<<"Problem? The Solution: Programming.";
    return 0;
}

L1-2 再进去几个人

L1-098 再进去几个人 - 团体程序设计天梯赛-练习集 (pintia.cn)

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    cout<<b-a;
    return 0;
}

L1-3 帮助色盲

L1-099 帮助色盲 - 团体程序设计天梯赛-练习集 (pintia.cn)

有点恶心的一个题，考试的时候应该是判断漏掉了情况，没有得到满分，但是后面也没改对。

其实我们只用分两种情况即可，一个是自己可以判断（路上有行人或者灯为黄灯），还有一个就是自己不能判断，需要提示（路上没有行人且灯不为黄灯）。后面写了一遍，根据题意写代码即可，下面是AC的代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int a,b;
    cin>>a>>b;
    if(b==1)//路上有行人，可以自己判断
    {
        if(a==1)cout<<"-"<<endl<<"move";
        else if(a==0)cout<<"-"<<endl<<"stop";
        else if(a==2)cout<<"-"<<endl<<"stop";
    }
    else if(a==2)//灯为黄灯，可以自己判断
    {
        cout<<"-"<<endl<<"stop";
    }
    else {//没有行人，需要提示
        if(a==0)cout<<"biii"<<endl<<"stop";
        if(a==1)cout<<"dudu"<<endl<<"move";
    }
    return 0;
}

L1-4 四项全能

L1-100 四项全能 - 团体程序设计天梯赛-练习集 (pintia.cn)

假设每个人都会（全部-1）种技能，算出来一个数，再用总技能减去这个数得到的就是会全部技能的人，注意就是如果算出来是负数要输出0

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,m,x,sum=0;
    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>x;
        sum+=x;
    }
    cout<<(sum-n*(m-1)>0?sum-n*(m-1):0);
    return 0;
}

L1-5 别再来这么多猫娘了

L1-101 别再来这么多猫娘了！ - 团体程序设计天梯赛-练习集 (pintia.cn)

很恶心的一道字符串处理题，去年也有一道字符串处理题很多人都被卡了，看官方的分析报告就说后面比赛会着重考这种类型的题目，没想到啊，近年真的着重考了，不过还是没做对，考前也做了几个这种类型的题，还是没全对，哎。下面是考试时候的13分的代码。

#include<bits/stdc++.h>
using namespace std;
string warn[110];
int main()
{
    int n,k;
    string s;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        cin>>warn[i];
    }
    cin>>k;
    getchar();
    getline(cin,s);
    //cout<<s<<endl;
    int p,len,cnt=0;
    for(int i=0;i<n;i++)
    {
        len=warn[i].size();
        p=s.find(warn[i]);
        //cout<<p<<endl;
        while(p!=-1)
        {
            s.replace(p,len,"<censored>");//替换
            p=s.find(warn[i]);
            cnt++;
        }
    }
    if(cnt<k)cout<<s;
    else cout<<cnt<<endl<<"He Xie Ni Quan Jia!";
    return 0;
}

L1-6 兰州牛肉面

L1-102 兰州牛肉面 - 团体程序设计天梯赛-练习集 (pintia.cn)

可以开两个数组写，不用map，不过都差不多，AC代码：

#include<bits/stdc++.h>
using namespace std;
map<int,int>mp;
double num[110];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>num[i];
    }
    int a,b;
    double sum=0;
    for(;;)
    {
        cin>>a>>b;
        if(a==0)break;
        sum+=num[a]*b;
        mp[a]+=b;
    }
    for(int i=1;i<=n;i++)
    {
        cout<<mp[i]<<endl;
    }
    printf("%.2lf\n",sum);
    return 0;
}

L1-7 整数的持续性

L1-103 整数的持续性 - 团体程序设计天梯赛-练习集 (pintia.cn)

根据题意模拟即可，代码写的有点丑了

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int solve(int x)
{
    int cnt=0;
    while(x>=10)
    {
        int p=x;
        int ans=1;
        while(p)
        {
            ans=ans*(p%10);
            p/=10;
        }
        //cout<<x<<endl;
        x=ans;
        cnt++;
    }

    return cnt;
}

int main()
{
    int a,b,ans=0,cnt;
    vector<int>v;
    map<int,int>mp;
    cin>>a>>b;
    for(int i=a;i<=b;i++)
    {
        cnt=solve(i);
        ans=max(ans,cnt);
        mp[i]=cnt;
    }
    for(int i=a;i<=b;i++)
    {
        if(mp[i]==ans)v.push_back(i);
    }
    cout<<ans<<endl;
    for(int i=0;i<v.size()-1;i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<v[v.size()-1];
    return 0;
}

L1-8 九宫格

L1-104 九宫格 - 团体程序设计天梯赛-练习集 (pintia.cn)

这个代码写了两遍，第一遍写完的时候电脑掉线，没保存，只能重新写了，写第二遍的时候有一个地方忘记返回true，codeblocks应该会默认返回true，导致我在编译器上面结果时正确的，但是提交测试就是不对，写看的我怀疑人生，找了半天终于找到了漏写一个return true。

分别对行，列，块判断是否符合要求：

#include<bits/stdc++.h>
using namespace std;
int cnt[1010];
int room[10][10];
void memset1()
{
    for(int i=1;i<=9;i++)
        cnt[i]=0;
}
bool hang(int h)
{
    memset1();
    for(int i=1;i<=9;i++)
    {
        cnt[room[h][i]]++;
    }
    for(int i=1;i<=9;i++)
    {
        if(cnt[i]!=1)return false;
    }
    return true;
}
bool lie(int l)
{
    memset1();
    for(int i=1;i<=9;i++)
    {
        cnt[room[i][l]]++;
    }
    for(int i=1;i<=9;i++)
    {
        if(cnt[i]!=1)return false;
    }
    return true;
}
bool kuai(int x,int y)
{
    memset1();
    for(int i=x;i<x+3;i++)
    {
        for(int j=y;j<y+3;j++)
        {
            cnt[room[i][j]]++;
        }
    }
    for(int i=1;i<=9;i++)
    {
        if(cnt[i]!=1)return false;
    }
    return true;
}
bool solve()
{
    for(int i=1;i<=9;i++)
    {
        if(!lie(i)||!hang(i))return false;
    }
    for(int i=1;i<=7;i+=3)
    {
        for(int j=1;j<=7;j+=3)
        {
            if(!kuai(i,j))return false;
        }
    }
    return true;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        for(int i=1;i<=9;i++)
        {
            for(int j=1;j<=9;j++)
            {
                cin>>room[i][j];
            }
        }
        if(solve())cout<<1<<endl;
        else cout<<0<<endl;
    }
    return 0;
}

L2-1 鱼与熊掌

L2-049 鱼与熊掌 - 团体程序设计天梯赛-练习集 (pintia.cn)

map模拟一下然后判断就可以了，比较简单。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
map<int,int>mp[N];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int n,m,k;
    int x;
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>k;
        for(int j=1;j<=k;j++)
        {
            cin>>x;
            mp[i][x]=1;
        }
    }
    int q,a,b;
    cin>>q;
    while(q--)
    {
        cin>>a>>b;
        int cnt=0;
        for(int i=1;i<=n;i++)
        {
            if(mp[i][a]&&mp[i][b])cnt++;
        }
        cout<<cnt<<endl;
    }
    return 0;
}

L2-2 懂蛇语

L2-050 懂蛇语 - 团体程序设计天梯赛-练习集 (pintia.cn)

当晚调试但是还是有个格式错误，就没仔细看了，大概思路还是正确的。

这个题目有两点比较麻烦的地方

一句拼音组成的话提取出他的首字母映射到map上面，可能会有两个拼音之间有多个空格的情况，题目测试数据给出来了“yi dian dian”中间其实有两个空格。要注意不要把空格当成首字母存储起来。
首字母相同可能对应多句话，所以用map<string,vector>来存

上面两点都想到了，但是还有一个比较恶心的地方也是考试的时候漏看的，就是如果找不到就输出原来的句子。注意了这几个点就能写出来了。

在这里插入图片描述

#include <bits/stdc++.h>
using namespace std;
string tra(string s)
{
    string ans="";
    ans=ans+s[0];
    int len=s.length();
    for(int i=1;i<len;i++)
    {
        if(s[i-1]==' '){
            while(s[i]==' '){i++;}//处理有多个空格的情况
            ans=ans+s[i];
        }
    }
    return ans;
}
vector<string>v;
map<string,vector<string>>mp;
int main()
{
    int n;
    cin>>n;
    string s1,s2;
    getchar();
    for(int i=0;i<n;i++)
    {
        getline(cin,s1);
        v.push_back(s1);
        s2=tra(s1);
        //cout<<s2<<endl;
        //mp[s2].push_back(s1);
    }
    sort(v.begin(),v.end());
    for(int i=0;i<n;i++)
    {
         s2=tra(v[i]);
        //cout<<s2<<endl;
        mp[s2].push_back(v[i]);
    }
    int q;
    cin>>q;
    getchar();
    string s;
    while(q--)
    {
        getline(cin,s);
        //cout<<s<<endl;
        s2=tra(s);
        //cout<<s2<<endl;
        if(mp[s2].size()==0)cout<<s<<endl;
        else if(mp[s2].size()==1)cout<<mp[s2][0]<<endl;
        else{
            for(int i=0;i<mp[s2].size()-1;i++)
            {
                cout<<mp[s2][i]<<"|";
            }
            cout<<mp[s2][mp[s2].size()-1]<<endl;
        }
    }

    return 0;
}

L2-3 满树的遍历

L2-051 满树的遍历 - 团体程序设计天梯赛-练习集 (pintia.cn)

感觉二十分钟做这道题的话应该能做出来，代码和思路都要简单一点。后面写估计没用二十分钟。

最简单的图存储，用vector存边，然后对所有子节点排序，简单dfs搜索一下就是前序遍历了，还是很简单的一个题

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
vector<int>v[N];
int n;
int cnt=0;
void solve(int x)
{
    if(x!=0)
    {
        if(cnt==n)
        {
            cout<<x; 
            return ;
        }
        else cout<<x<<" ";
        //cout<<cnt<<endl;
    }
    for(int i=0;i<v[x].size();i++)
    {
        //cout<<v[x][i]<<" ";
        cnt++;
        solve(v[x][i]);
    }
}
int main()
{
    int x;
    cin>>n;
    int ans=0;
    for(int i=1;i<=n;i++)
    {
        cin>>x;
        v[x].push_back(i);//存储x节点的儿子
    }
    for(int i=1;i<=n;i++)
    {
        sort(v[i].begin(),v[i].end());
        ans=max((int)v[i].size(),ans);//求这棵树的最大的度
    }
    int flag=1;
    for(int i=1;i<=n;i++)
    {
        if(v[i].size()!=0&&v[i].size()!=ans)flag=0;//要么是叶子节点，要么儿子的个数为树最大的度ans才是满二叉树
    }
    cout<<ans<<(flag?" yes":" no")<<endl;
    solve(0);
}