【GPLT】 2021CCCC天梯赛题解

妍来那样美好

已于 2023-02-03 16:16:58 修改

阅读量340

点赞数

分类专栏： PAT C++ 文章标签：算法 c++ 图论数据结构

于 2022-12-15 18:39:08 首次发布

本文链接：https://blog.csdn.net/qq_29353083/article/details/128333796

版权

C++ 同时被 2 个专栏收录

10 篇文章 0 订阅

订阅专栏

PAT

2 篇文章 0 订阅

订阅专栏

更好的阅读体验：GPLT 2021CCCC天梯赛题解

L1-人与神

解题思路
直接输出To iterate is human, to recurse divine.即可

#include <iostream>

using namespace std;

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

L1-两小时学完C语言

解题思路
已看的字数: $k\cdot{m}$ .
总字数: $N$ .
答案（剩余字数）: $N-k\cdot{m}$ .

#include <iostream>

using namespace std;

const int N=100010;

int n,k,m;

int main()
{
    cin>>n>>k>>m;
    cout<<n-k*m<<endl;
    return 0;
}

L1-强迫症

解题思路
字符串处理问题，s.substr(i,j) 表示从字符串s的第i位开始往后截取j位的新字符串
分别处理4位和6位的情况即可，详细见代码

#include <iostream>

using namespace std;

int main()
{
    string s; cin>>s;
    if(s.size()==4) {
        int t=stoi(s.substr(0,2));
        if(t<22) t=20;
        else t=19;
        cout<<to_string(t)+s.substr(0,2)+'-'+s.substr(2)<<endl;
    } else {
        cout<<s.substr(0,4)+'-'+s.substr(4)<<endl;
    }

    return 0;
}

L1-降价提醒机器人

解题思路
输出所有小于m的值，格式化输出，保留一位小数

#include <iostream>

using namespace std;

int n;
double m;

int main()
{
    cin>>n>>m;
    while(n--)
    {
        double x; cin>>x;
        if(x<m) printf("On Sale! %.1f\n", x);
    }

    return 0;
}

L1-大笨钟的心情

解题思路
哈希每一个时刻的心情指数，判断 Yes/No 输出

#include <iostream>

using namespace std;

const int N=110;

int st[N];

int main()
{
    for(int i=0;i<24;i++) cin>>st[i];
    int k; 
    while(cin>>k, k>=0 && k<=23)
    {
        cout<<st[k]<<(st[k]>50?" Yes":" No")<<endl;    
    }
    
    return 0;
}

L1-吉老师的回归

解题思路
判断每一个题目中有无"easy"和"qiandao"，无则累加次数，最后判断输出
s.find(t)表示在字符串s中查找字符串t，常量 string::npos 表示没有查找到

#include <iostream>

using namespace std;

const int N=50;

int n, m;

int main()
{
    cin>>n>>m;
    getchar();
    int k=0;
    for(int i=1;i<=n;i++)
    {
        string s; getline(cin, s);
        if(s.find("qiandao")==string::npos && s.find("easy")==string::npos) { //两个都不存在
            k++;
            if(k>m) {
                cout<<s<<endl;
                break;
            }
        }
    }

    if(k<=m) cout<<"Wo AK le"<<endl;

    return 0;
}

L1-天梯赛的善良

解题思路
用两个变量存一个最大值和最小值，再循环一遍计算答案

#include <iostream>

using namespace std;

const int N=20010;

int n, a[N];

int main()
{
    cin>>n;
    int minv=1e9, maxv=0;
    for(int i=1;i<=n;i++) 
    {
        scanf("%d", &a[i]);
        minv=min(minv, a[i]);
        maxv=max(maxv, a[i]);
    }

    int res1=0, res2=0;
    for(int i=1;i<=n;i++) 
    {
        if(a[i]==minv) res1++;
        if(a[i]==maxv) res2++;
    }

    cout<<minv<<' '<<res1<<endl;
    cout<<maxv<<' '<<res2<<endl;

    return 0;
}

L1-乘法口诀序列

解题思路
动态处理，每次乘积最大是81，两位数
一直处理到序列长度达到n为止

#include <bits/stdc++.h>

using namespace std;

int n;

int main()
{
    int a1, a2; cin>>a1>>a2>>n;
    vector<int> res({a1, a2});
    for(int i=0;res.size()<n;i++)
    {
        int m=res[i]*res[i+1];
        if(m>=10) res.push_back(m/10);
        res.push_back(m%10);
    }

    cout<<res[0];
    for(int i=1;i<n;i++) cout<<' '<<res[i];

    return 0;
}

L2-包装机

解题思路
模拟，注意一些细节处理

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=110;

int n,m,S;
string orbit[N];
stack<int> basket;
string res;

int main()
{
    cin>>n>>m>>S;
    for(int i=1;i<=n;i++) 
    {
        cin>>orbit[i];
        reverse(all(orbit[i]));
    }
    int x;
    while(cin>>x, x!=-1)
    {
        if(x==0 && basket.size()>0) 
        {
            res.push_back(basket.top());
            basket.pop();
        }
        if(orbit[x].size()>0)
        {
            if(basket.size()==S) 
            {
                res.push_back(basket.top());
                basket.pop();
            }
            basket.push(orbit[x].back());
            orbit[x].pop_back();
        }
    }

    cout<<res<<endl;

    return 0;
}

L2-病毒朔源

解题思路
首先分析题目，每种病毒只能由一种病毒变异而来，所以是树结构。然后dfs遍历一遍。要从根节点出发（入度为0的点: d[root]=0），长度相同要注意字典序最小。

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=10010,M=1000010;

int h[N], e[M], ne[M], idx;
int n, d[N];
int nex[N];

void add(int a, int b)
{
    e[idx]=b, ne[idx]=h[a], h[a]=idx++;
}

int dfs(int u)
{
    int res=0, val=-1;
    for(int i=h[u];~i;i=ne[i])
    {
        int j=e[i];
        int t=dfs(j);
        if(t>res || (t==res && j<val)) nex[u]=j, res=t, val=j; 
    }

    return res+1;
}


int main()
{
    cin>>n;
    memset(h, -1, sizeof h);
    memset(nex, -1, sizeof nex);

    for(int i=0;i<n;i++)
    {
        int num; scanf("%d", &num);
        while(num--)
        {
            int x; scanf("%d", &x);
            add(i, x);
            d[x]++;
        }
    }

    int root=-1;
    for(int i=0;i<n;i++) 
        if(d[i]==0) 
        {
            root=i;
            break;
        }

    dfs(root);
    vector<int> res({root});
    while(nex[root]!=-1)
    {
        res.push_back(nex[root]);
        root=nex[root];
    }

    cout<<res.size()<<'\n'<<res[0];
    for(int i=1;i<res.size();i++) cout<<' '<<res[i];

    return 0;
}

L2-清点代码库

解题思路
做法1：可以用map做，会比较好写，key值是每一个序列，用vector存储，默认按vector里每一个项的值来排序。value是出现的次数。最后排序一遍输出。
做法2：unnordered_map + 自定义排序规则也可以做。

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=1000000007,P=18869,N=10010,M=110;

int n, m;
map<vector<int>, int > mp;
vector<pair<int, vector<int>> > ans;

int main()
{
    cin>>n>>m;
    rep(i,1,n)
    {
        vector<int> t;
        rep(j,1,m) 
        {
            int x; scanf("%d", &x);
            t.push_back(x);
        }
        mp[t]++;
    }

    for(auto val: mp) ans.push_back({-val.y, val.x});

    sort(all(ans));
    cout<<ans.size()<<endl;
    for(int i=0;i<ans.size();i++)
    {
        printf("%d", -ans[i].x);
        for(auto x: ans[i].y) printf(" %d", x);
        puts("");
    }

    return 0;
}

L2-哲哲打游戏

解题思路
也是一道模拟题

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=100010,M=2*N;

int n, m;
vector<int> plot[N];
int arch[N];

int main()
{
    cin>>n>>m;
    rep(i,1,n)
    {
        int K; scanf("%d",&K);
        while(K--) {
            int x; scanf("%d", &x);
            plot[i].push_back(x);
        }
    }

    int location=1;
    while(m--)
    {
        int op,k;
        scanf("%d%d", &op,&k);
        if(op==0) location=plot[location][k-1];
        else if(op==1){
            printf("%d\n", location);
            arch[k]=location;
        } else location=arch[k];
    }

    cout<<location<<endl;

    return 0;
}

L3-森森旅游

解题思路
图论题
做法1：分别存一个起点和终点到所有点的距离，用dist1和dist2来表示，用dijkstra处理。
因为要在某一个点全部换成旅游金，所以以这个中途点为单位（换成旅游金）求一遍起点到终点的费用，放进堆中，方便求最小值。每一个中途点计算起点到终点的费用为： $d i s t 1 [i] + (d i s t 2 [i] + a [i] - 1) / a [i]$ ，加a[i]-1是上取整。
最后处理每一个汇率变化即可。由于每一次汇率变化都放进堆里，所以可能存在之前的汇率没有删除，因此取堆顶的时候要特判每一个数据，如果计算出来的费用与当前汇率计算出来的不一样，就是旧数据。

做法2：用pair将费用和节点捆绑处理，再用set去重，这样可以删除原先的汇率，用set内置的find函数查找删除。

#include <bits/stdc++.h>
#define x first
#define y second
#define all(x) x.begin(),x.end()
#define rep(i, l, r) for (int i = l; i <= r; i++)
#define nep(i, r, l) for (int i = r; i >= l; i--)
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef pair<int,int> PII;
typedef pair<LL,int> PLI;
const int INF=0x3f3f3f3f, MOD=1000000007,P=131,N=100010,M=4*N;
const LL LNF=0x3f3f3f3f3f3f3f3f;

int h1[N], h2[N], e[M], ne[M], w[M], idx;
LL dist1[N], dist2[N];
bool st[N];
int n, m, q;
int a[N];
priority_queue<PLI, vector<PLI>, greater<PLI>> heap;

void add(int a, int b, int c, int d)
{
    e[idx]=b, w[idx]=c, ne[idx]=h1[a], h1[a]=idx++;
    e[idx]=a, w[idx]=d, ne[idx]=h2[b], h2[b]=idx++;
}

void dijkstra(LL dist[], int s, int h[])
{
    memset(st, 0, sizeof st);
    memset(dist, 0x3f, sizeof dist1);
    priority_queue<PLI, vector<PLI>, greater<PLI>> q;
    q.push({0, s});
    dist[s]=0;
    while(q.size())
    {
        PLI t=q.top(); q.pop();
        if(st[t.y]) continue;
        st[t.y]=true;
        
        for(int i=h[t.y];~i;i=ne[i])
        {
            int j=e[i];
            if(st[j]) continue;
            dist[j]=min(dist[j], dist[t.y]+w[i]);
            q.push({dist[j], j});
        }
    }
}

int main()
{
	cin>>n>>m>>q;
	memset(h1, -1, sizeof h1);
	memset(h2, -1, sizeof h2);
	while(m--)
	{
	    int a, b, c, d; scanf("%d%d%d%d", &a, &b, &c, &d);
	    add(a, b, c, d);
	}
	
	dijkstra(dist1, 1, h1);
	dijkstra(dist2, n, h2);
	
	rep(i,1,n) 
	{
	    scanf("%d", &a[i]);
	    if(dist1[i]!=LNF && dist2[i]!=LNF) 
	        heap.push({dist1[i]+(dist2[i]+a[i]-1)/a[i], i});
	}
	
	while(q--)
	{
	    int x, aa; scanf("%d%d", &x, &aa);
	    a[x]=aa;
	    if(dist1[x]!=LNF && dist2[x]!=LNF) heap.push({dist1[x]+(dist2[x]+aa-1)/aa, x});
	    while(true)
	    {
	        PLI t=heap.top();
	        if((dist2[t.y]+a[t.y]-1)/a[t.y]+dist1[t.y] != t.x){ //汇率更改了
	            heap.pop();
	            continue;
	        }
	        printf("%lld\n", t.x);
	        break;
	    }
	}
	
	return 0;
}

L3-还原文件

解题思路
暴搜，虽说是暴搜，但是别太暴力，每一组序列哈希成一个值，这样不会TLE。
，每一次搜索判断哈希值是否匹配即可。

#include <bits/stdc++.h>
#define rep(i, l, r) for (int i = l; i <= r; i++)
using namespace std;
typedef unsigned long long ULL;
const int INF=0x3f3f3f3f,MOD=1000000007,P=131,N=100010,M=110;

ULL hup[N], p[N], hdown[M];
int width[M];
int n, m, h[N];
int ans[M];
bool st[M];

ULL get_hcode(int l, int r)
{
    return hup[r]-hup[l-1]*p[r-l+1];
}

bool dfs(int u, int s)
{
    if(s==n) return true;
    for(int i=1;i<=m;i++)
    {
        int e=s+width[i]-1;
        if(st[i]) continue;
        if(e<=n && hdown[i]==get_hcode(s, e)) {
            st[i]=true;
            ans[u]=i;
            if(dfs(u+1, e)) return true;
            st[i]=false;
        }
    }
    
    return false;
}

int main()
{
	cin>>n;
	p[0]=1;
	rep(i,1,n) 
	{
	    scanf("%d", &h[i]);
	    p[i]=p[i-1]*P;
	    hup[i]=hup[i-1]*P+h[i];
	}
	cin>>m;
	rep(i,1,m){
	    scanf("%d", &width[i]);
	    rep(j,1,width[i]) {
	        int x; scanf("%d", &x);
	        hdown[i]=hdown[i]*P+x;
	    }
	}
	
	dfs(1, 1);
	
	printf("%d", ans[1]);
	rep(i,2,m) printf(" %d", ans[i]);
	
	return 0;
}