目录
2021GPLT 团体程序设计天梯赛 个人题解
俊杰Charles
编辑于 2021年04月27日 13:38
收录于文集
共8篇

比赛地址：https://gplt.patest.cn/

题目链接：https://pintia.cn/problem-sets/994805046380707840/

难度：L1<L2<L3

赛中过题情况

由于B站专栏的代码块功能有 bug，如果代码块不能正常显示，请通过代码链接查看代码。

L1-1 人与神

题意：输出“To iterate is human, to recurse divine.”。

代码链接：https://paste.ubuntu.com/p/JHD5XQcjcw/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

int main()
{
    cout<<"To iterate is human, to recurse divine.";
    return 0;
}
复制成功

L1-2 两小时学完C语言

题意：共 n 个字，每分钟看 m 个字，看了 k 分钟，还剩多少字没看。保证 mk%5Cle%20n。

题解：n-mk

代码链接：https://paste.ubuntu.com/p/NtBPBPsrBj/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

long long n,m,k;

int main()
{
    cin>>n>>m>>k;
    cout<<n-m*k;
    return 0;
}
复制成功

L1-3 强迫症

题意：将“年年月月”或“年年年年月月”格式的字符串格式化为“年年年年-月月”。

代码链接：https://paste.ubuntu.com/p/MGB9vWmJF4/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

string s;

int main()
{
    cin>>s;
    if (s.size()==6)
    {
        cout<<s.substr(0,4)<<"-"<<s.substr(4,2);
    }
    else
    {
        int year=stoi(s.substr(0,2));
        if (year<22) year+=2000;
        else year+=1900;
        cout<<year<<"-"<<s.substr(2,2);
    }
    return 0;
}
复制成功

L1-4 降价提醒机器人

题意：当玩具的当前价格比他设定的价格便宜时发出提醒。

代码链接：https://paste.ubuntu.com/p/Sy4scJkcdc/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

int n;
double m,x;

int main()
{
    scanf("%d%lf",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%lf",&x);
        if (x<m) printf("On Sale! %.1lf\n",x);
    }
    return 0;
}
复制成功

L1-5 大笨钟的心情

题意：给定大笨钟在一天 24 小时中每个小时的心情指数，对于若干次询问，每次询问某一时间大笨钟的心情指数，并判断是否大于 50。

代码链接：https://paste.ubuntu.com/p/YBdNgwXvF8/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

int a[30],x;

int main()
{
    for (int i=0;i<24;i++)
    {
        cin>>a[i];
    }
    while (1)
    {
        cin>>x;
        if (x<0 || x>23) break;
        cout<<a[x]<<(a[x]>50?" Yes\n":" No\n");
    }
    return 0;
}
复制成功

L1-6 吉老师的回归

题意：给定 n 个字符串，输出第 m%2B1 个不含 "qiandao&#​34; 或 "easy&#​34; 子串的字符串，若满足条件的字符串不超过 m 个则输出 "Wo AK le&#​34;。

题解：getline 与 find 函数的运用。

代码链接：https://paste.ubuntu.com/p/GWnmrV664n/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

int n,m;
string str;
vector<string>ans;

int main()
{
    cin>>n>>m;
    getline(cin,str);
    for (int i=1;i<=n;i++)
    {
        getline(cin,str);
        if (str.find("qiandao")==string::npos && str.find("easy")==string::npos)
        {
            ans.push_back(str);
        }
    }
    if (m>=(int)ans.size()) cout<<"Wo AK le";
    else cout<<ans[m];
    return 0;
}
复制成功

L1-7 天梯赛的善良

题意：给定 n 个数，求最大的数及其个数，以及最小的数及其个数。

题解：map 容器的运用。

代码链接：https://paste.ubuntu.com/p/d5q7XSxsmx/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

int n,x;
map<int,int>cnt;

int main()
{
    cin>>n;
    for (int i=1;i<=n;i++)
    {
        cin>>x;
        cnt[x]++;
    }
    auto it=cnt.begin();
    cout<<it->first<<' '<<it->second<<'\n';
    auto rit=cnt.rbegin();
    cout<<rit->first<<' '<<rit->second<<'\n';
    return 0;
}
复制成功

L1-8 乘法口诀数列

题意：给定的两个 1 位数字 a_1 和 a_2，生成一个数列 %5C%7Ba_n%5C%7D，规则为从 a_1 开始顺次进行，每次将当前数字与后面一个数字相乘，将结果贴在数列末尾。如果结果不是 1 位数，则其每一位都应成为数列的一项。

代码链接：https://paste.ubuntu.com/p/Y45nMyyDNd/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

int n,a,b;
vector<int>ans;

int main()
{
    cin>>a>>b>>n;
    ans.push_back(a);
    ans.push_back(b);
    int pos=2;
    while ((int)ans.size()<n)
    {
        int x=ans[pos-2],y=ans[pos-1];
        int z=x*y;
        string s=to_string(z);
        for (char c:s)
        {
            ans.push_back(c-'0');
        }
        pos++;
    }
    ans.resize(n);
    for (int i=0;i<n;i++)
    {
        cout<<ans[i]<<(i==n-1?'\n':' ');
    }
    return 0;
}
复制成功

L2-9 包装机

题意：有 n 条轨道，各轨道初始有 m 件物品，还有一个最大容量为 s 的栈。给定若干操作，若操作号为 0，表示从栈顶取出一件物品放在流水线上；否则将对应编号轨道的首个物品推入栈中，若栈满，则先从栈顶取出一件物品放在流水线上，再将轨道上的物品推入栈中。若每次操作对应轨道或栈为空，则忽略该次操作。

代码链接：https://paste.ubuntu.com/p/bh68svWT36/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

int n,m,s,o;
string q[110],st,ans;

int main()
{
    cin>>n>>m>>s;
    for (int i=1;i<=n;i++)
    {
        cin>>q[i];
        reverse(q[i].begin(),q[i].end());
    }
    while (1)
    {
        cin>>o;
        if (o==-1) break;
        if (o==0)
        {
            if (st.empty()) continue;
            ans.push_back(st.back());
            st.pop_back();
        }
        else
        {
            if (q[o].empty()) continue;
            if ((int)st.size()>=s)
            {
                ans.push_back(st.back());
                st.pop_back();
            }
            st.push_back(q[o].back());
            q[o].pop_back();
        }
    }
    cout<<ans;
    return 0;
}
复制成功

L2-10 病毒溯源

题意：给定一个有向无环图，求出图上最长链。

题解：记忆化搜索。注意没有说必须从 0 开始。

代码链接：https://paste.ubuntu.com/p/Pby77dVpqm/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

const int N=10010;

int n,m,x;
vector<int>e[N];
int dp[N],nxt[N];

int dfs(int u)
{
    if (dp[u]!=-1) return dp[u];
    int maxd=1;
    for (int v:e[u])
    {
        if (dfs(v)+1>maxd)
        {
            maxd=dfs(v)+1;
            nxt[u]=v;
        }
        else if (dfs(v)+1==maxd && v<nxt[u])
        {
            nxt[u]=v;
        }
    }
    return dp[u]=maxd;
}

int main()
{
    scanf("%d",&n);
    for (int i=0;i<n;i++)
    {
        scanf("%d",&m);
        for (int j=1;j<=m;j++)
        {
            scanf("%d",&x);
            e[i].push_back(x);
        }
    }
    memset(dp,-1,sizeof(dp));
    memset(nxt,-1,sizeof(nxt));
    int u=-1;
    for (int i=0;i<n;i++)
    {
        if (u==-1 || dfs(i)>dfs(u))
        {
            u=i;
        }
    }
    printf("%d\n",dfs(u));
    while (u!=-1)
    {
        printf("%d",u);
        putchar(nxt[u]==-1?'\n':' ');
        u=nxt[u];
    }
    return 0;
}
复制成功

L2-11 清点代码库

题意：有 n 个代码，每个代码的输出有 m 个数。统计有多少种不同的输出，以及各种输出的个数。输出时按个数从大到小排序，若个数相同则按字典序。

题解：注意 vector 是可以直接排序的，与 string 一样都是按字典序，因此直接使用 map 容器统计个数，最后 sort 一下就好了。

代码链接：https://paste.ubuntu.com/p/g5QfCw52jY/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

int n,m,x;
map<vector<int>,int> cnt;
vector<pair<int,vector<int>>> ans;

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        vector<int>v;
        for (int j=1;j<=m;j++)
        {
            scanf("%d",&x);
            v.push_back(x);
        }
        cnt[v]++;
    }
    for (auto t:cnt)
    {
        ans.push_back({-t.second,t.first});
    }
    sort(ans.begin(),ans.end());
    printf("%d\n",(int)ans.size());
    for (auto t:ans)
    {
        printf("%d",-t.first);
        for (int i:t.second)
        {
            printf(" %d",i);
        }
        putchar('\n');
    }
    return 0;
}
复制成功

L2-12 哲哲打游戏

题意：给定一张有向图与若干次操作，操作 0 x 表示走当前位置的第 x 条出边，操作 1 x 表示将当前位置存档在第 x 个档位，操作 2 x 表示从第 x 个档位读取位置，求每次存档时的位置以及最终位置。

代码链接：https://paste.ubuntu.com/p/Bkm3GFpHBs/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

const int N=100010;

int n,m,k,x,o;
vector<int>e[N];
int sav[110];

int main()
{
    scanf("%d%d",&n,&m);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&k);
        for (int j=1;j<=k;j++)
        {
            scanf("%d",&x);
            e[i].push_back(x);
        }
    }
    int pos=1;
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d",&o,&x);
        if (o==0)
        {
            pos=e[pos][x-1];
        }
        else if (o==1)
        {
            sav[x]=pos;
            printf("%d\n",pos);
        }
        else
        {
            pos=sav[x];
        }
    }
    printf("%d\n",pos);
    return 0;
}
复制成功

L3-13 森森旅游

题意：给定一张有向图，每条边的花费为 c 元现金或 d 元旅游金。第 i 个城市的汇率为 a_i，表示在第 i 个城市可以用 1 元现金换取 a_i 元旅游金。现要从起点 1 走到终点 n，要求开始时都使用现金，然后在某个城市将所有现金全部换为旅游金，然后剩下的部分都使用旅游金。有 q 次询问，每次询问会将某个城市的汇率 a_i 改为 a_i%26%2339%3B，对每次询问求最少需准备多少现金。

题解：先跑两次最短路，分别求出起点到各点最少花费多少现金，以及各点到终点最少花费多少旅游金。令起点到点 i 最少花费 x 元现金，点 i 到终点最少花费 y 元旅游金，则在点 i 将所有现金全部换为旅游金时最少准备现金 x%2B%5Clceil%5Cfrac%7By%7D%7Ba_i%7D%5Crceil 元，对各点求出结果取最小值即可。对于修改操作，由于仅修改 a_i，不影响最短路，因此每次修改只有对应位置的答案会发生变化，用一个 multiset 维护最小值即可。计算答案时要注意判断该位置是否可达。

代码链接：https://paste.ubuntu.com/p/GBzwqtNgf8/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

const int N=100010;

int n,m,q,x,y;
long long c,d;
vector<pair<int,long long>> e[N],re[N];
long long a[N];
long long dis[N],rdis[N];
long long ans[N];
multiset<long long>s;

void dij(int st,long long *dis,vector<pair<int,long long>> *e)
{
    priority_queue<pair<long long,int>,vector<pair<long long,int>>,greater<>> q;
    memset(dis,-1,sizeof(a));
    dis[st]=0;
    q.push({0,st});
    while (!q.empty())
    {
        auto du=q.top(); q.pop();
        long long d=du.first;
        int u=du.second;
        if (d>dis[u]) continue;
        for (auto vw:e[u])
        {
            int v=vw.first;
            long long w=vw.second; 
            if (dis[v]==-1 || d+w<dis[v])
            {
                dis[v]=d+w;
                q.push({dis[v],v});
            }
        }
    }
}

int main()
{
    scanf("%d%d%d",&n,&m,&q);
    for (int i=1;i<=m;i++)
    {
        scanf("%d%d%lld%lld",&x,&y,&c,&d);
        e[x].push_back({y,c});
        re[y].push_back({x,d});
    }
    for (int i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    dij(1,dis,e);
    dij(n,rdis,re);
    for (int i=1;i<=n;i++)
    {
        if (dis[i]!=-1 && rdis[i]!=-1)
        {
            ans[i]=dis[i]+(rdis[i]+a[i]-1)/a[i];
            s.insert(ans[i]);
        }
    }
    while (q--)
    {
        scanf("%d%lld",&x,&d);
        a[x]=d;
        if (dis[x]!=-1 && rdis[x]!=-1)
        {
            s.erase(s.find(ans[x]));
            ans[x]=dis[x]+(rdis[x]+a[x]-1)/a[x];
            s.insert(ans[x]);
        }
        printf("%lld\n",*s.begin());
    }
    return 0;
}
复制成功

L3-14 还原文件

题意：将一个串拆成若干子串，问如何将这些子串拼回原串，保证解唯一。

题解：将每个子串在原串中进行匹配，每个匹配用一个有向边表示，边权为对应子串的编号以防重复。最终在得到的有向图上找到一条从起点到终点所有边的编号互不相同的链即可。本题数据较弱，字符串匹配使用暴力方法即可，最终求答案直接 dfs 搜索。

代码链接：https://paste.ubuntu.com/p/Q6zXZN5NPh/

代码块
C++
自动换行
复制代码
#include <bits/stdc++.h> //code by cjj490168650
using namespace std;

const int N=100010;

int n,m,k,a[N],h[N];
vector<pair<int,int>> e[N];
vector<int>ans;
bool vis[N],ok=false;

bool cmp(int p,int k)
{
    for (int i=1;i<=k;i++)
    {
        if (a[p+i-1]!=h[i]) return false;
    }
    return true;
}

void dfs(int u)
{
    if (u==n)
    {
        ok=true;
        return;
    }
    for (auto vw:e[u])
    {
        int v=vw.first,w=vw.second;
        if (vis[w]) continue;
        ans.push_back(w);
        vis[w]=true;
        dfs(v);
        if (ok) return;
        ans.pop_back();
        vis[w]=false;
    }
}

int main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for (int i=1;i<=m;i++)
    {
        scanf("%d",&k);
        for (int j=1;j<=k;j++)
        {
            scanf("%d",&h[j]);
        }
        for (int j=1;j<=n-k+1;j++)
        {
            if (cmp(j,k))
            {
                e[j].push_back({j+k-1,i});
            }
        }
    }
    dfs(1);
    for (int i=0;i<m;i++)
    {
        printf("%d",ans[i]);
        putchar(i==m-1?'\n':' ');
    }
    return 0;
}
复制成功

L3-15 可怜的简单题

输出 1 即可骗到 1 分。

这场比赛我个人最大的感受是，如果能熟练运用 stl 的话，做前两档难度的题目速度会非常快，可以留更多时间给第三档的题目。比赛开始时服务器还是出问题了，希望主办方之后能有所改善。这次的题目质量比起上次的来说确实有进步，希望比赛能越办越好吧。

算法竞赛交流群：1043272289

天梯赛 ACM CCCC 算法竞赛 GPLT
本文为我原创，未经授权禁止转载
cv11044423