【2022团体程序设计天梯赛】GPLT2022，L1~L2部分（PTA，L1-081~L1-088，L2-041~L2-044）题解代码

@[toc]

概要

• L1部分：L1-081~L1-088
• L2部分：L2-041~L2-044
• L3部分：L3-031~L3-033

L1-081 今天我要赢 (5分)

//希望没人不会做……
#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"I'm gonna win! Today!\n";
    cout<<"2022-04-23";
    return 0;
}

L1-082 种钻石（5分）

//总量/速度即可，向下取整
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, v;  cin>>n>>v;
    cout<<n/v<<"\n";
    return 0;
}

L1-083 谁能进图书馆(10分)

//题面较长，理清思路后ifelse即可
#include<bits/stdc++.h>
using namespace std;
int main(){
    int x, y, a, b;  cin>>x>>y>>a>>b;
    if(a>=x && b>=x){
        cout<<a<<"-Y "<<b<<"-Y\n";
        cout<<"huan ying ru guan\n";
    }else if(a<x && b < x){
        cout<<a<<"-N "<<b<<"-N\n";
        cout<<"zhang da zai lai ba\n";
    }else{
        if(a>=x){
            if(a>=y){
                cout<<a<<"-Y "<<b<<"-Y\n";
                cout<<"qing 1 zhao gu hao 2\n";
            }else{
                cout<<a<<"-Y "<<b<<"-N\n";
                cout<<"1: huan ying ru guan\n";
            }
        }else{
            if(b>=y){
                cout<<a<<"-Y "<<b<<"-Y\n";
                cout<<"qing 2 zhao gu hao 1\n";
            }else{
                cout<<a<<"-N "<<b<<"-Y\n";
                cout<<"2: huan ying ru guan\n";
            }
        }
    }
    return 0;
}

L1-084 拯救外星人(10分)

//输出a+b的阶乘，直接枚举即可
#include<bits/stdc++.h>
using namespace std;
int main(){
    int a, b;  cin>>a>>b;
    int c = a+b, d = 1;
    for(int i = 1; i <= c; i++)d *= i;
    cout<<d<<"\n";
    return 0;
}

L1-085 试试手气（15分）

//每次摇出来不同，所以直接654往下排，所以直接-n+1，如果大于当前就再-1即可
#include<bits/stdc++.h>
using namespace std;
int a[10];
int main(){
    for(int i = 1; i <= 6; i++)cin>>a[i];
    int n;  cin>>n;
    for(int i = 1; i <= 6; i++){
        if(i!=1)cout<<" ";
        if(6-n+1 > a[i])cout<<6-n+1;
        else cout<<6-n+1-1;
    }
    return 0;
}

L1-086 斯德哥尔摩火车上的题(15分)

//代码都给了，照抄就行了
#include<bits/stdc++.h>
using namespace std;
int main(){
    string a, sa="";  cin>>a;
    for(int i = 1; i < a.size(); i++){
        if(a[i]%2==a[i-1]%2){
            sa += max(a[i], a[i-1]);
        }
    }
    string b, sb="";  cin>>b;
    for(int i = 1; i < b.size(); i++){
        if(b[i]%2==b[i-1]%2){
            sb += max(b[i], b[i-1]);
        }
    }
    if(sa==sb)cout<<sa<<"\n";
    else cout<<sa<<"\n"<<sb;
    return 0;
}

L1-087 机工士姆斯塔迪奥(20分)

//去掉第1行和第x行对答案的影响是一样的（除非x==1），所以每次n--,m--，最后乘起来即可
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, m, q;  cin>>n>>m>>q;
    set<int>se, se2;
    while(q--){
        int t, c;  cin>>t>>c;
        if(t==0 && !se.count(c))n--,se.insert(c);
        if(t==1 && !se2.count(c))m--,se2.insert(c);
    }
    cout<<n*m<<"\n";
    return 0;
}

L1-088 静静的推荐(20分)

//gplt175+pat(s)从大到小排个序1次直接推走，剩下pat不够的每个分数都再推k个人即可
#include<bits/stdc++.h>
using namespace std;
int main(){
    int n, k, s;  cin>>n>>k>>s;
    int a[300]={0}, sum = 0;
    for(int i = 1; i <= n; i++){
        int x, y;  cin>>x>>y;
        if(x>=175 && y>=s)sum++;
        if(x>=175 && y<s)a[x]++;
    }
    for(int i = 175; i <= 290; i++){
        if(a[i]==0)continue;
        if(a[i]<=k)sum += a[i];else sum += k;
    }
    cout<<sum<<"\n";
    return 0;
}

L2-041 插松枝(25分)

//队列（推送器）以及栈（小盒子）模拟
#include<bits/stdc++.h>
using namespace std;

stack<int>st;
queue<int>q;
vector<int>ans[1010];

int main(){
    int n, m, k;  cin>>n>>m>>k;
    while(n--){ int x;  cin>>x;  q.push(x); }
    int i = 0, lst = 0;
    while(q.size() || st.size()){
        lst = (ans[i].size()==0 ? 99999 : ans[i].back());
        if(st.size() && st.top()<=lst){ //先用小盒子
            ans[i].push_back(st.top());  st.pop();
        }else if(q.size() && q.front()<=lst){//再用推送器
            ans[i].push_back(q.front());  q.pop();
        }else if(st.size()<m && q.size()){//推送器放到小盒子里
            st.push(q.front());  q.pop();
        }else{
            i++;//小盒子满了，下一根
        }
        if(ans[i].size()==k)i++;
    }
    for(int j = 0; j <= i; j++){
        if(ans[j].size()==0)continue;
        for(int k = 0; k < ans[j].size(); k++){
            if(k)cout<<" ";
            cout<<ans[j][k];
        }
        cout<<"\n";
    }
    return 0;
}

L2-042 老板的作息表(25分)

//直接排序，然后输出两个不相邻区间的尾和头即可
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;

struct node{int h1, m1, s1, h2, m2, s2; }a[maxn];
bool cmp(node x, node y){
    if(x.h1 != y.h1)return x.h1<y.h1;
    if(x.m1 != y.m1)return x.m1<y.m1;
    if(x.s1 != y.s1)return x.s1<y.s1;
}

int main(){
    int n;  cin>>n;
    for(int i = 1; i <= n; i++){
        scanf("%d:%d:%d - %d:%d:%d", &a[i].h1, &a[i].m1, &a[i].s1, &a[i].h2, &a[i].m2, &a[i].s2);
    }
    a[0].h1 = 0, a[0].m1 = 0, a[0].s1 = 0;
    a[0].h2 = 0, a[0].m2 = 0, a[0].s2 = 0;
    a[n+1].h1 = 23, a[n+1].m1 = 59, a[n+1].s1 = 59;
    sort(a,a+n+2, cmp);
    for(int i = 1; i <= n+1; i++){
        if(a[i].h1==a[i-1].h2 && a[i].m1==a[i-1].m2 && a[i].s1==a[i-1].s2)continue;
        printf("%02d:%02d:%02d - %02d:%02d:%02d\n", a[i-1].h2, a[i-1].m2, a[i-1].s2, a[i].h1, a[i].m1, a[i].s1);
    }
    return 0;
}

L2-043 龙龙送外卖(25分)

//题意：一棵树上不断加点，求每次加点后访问所有点至少一次的最短距离是多少
//思路：可以贪心，外卖员最后的位置应该在距离外卖站最远的送餐地址。所以最短路程 = 需要经过的边数*2 - max(外卖站到送餐地址)
//每次搜索新增送餐点到外卖站未被标记的点（记忆化）可以实现O（n）
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int f[maxn], rt, dep[maxn];
int vis[maxn], tmp; //tmp每次累加就行
void dfs(int u ,int dis){//暴力跑一遍路程
    if(u==rt || vis[u]){
        tmp += dis;  return ;
    }
    vis[u] = 1;
    dfs(f[u], dis+2);
}
int calc(int u){//点u到rt的距离
    if(u==rt || dep[u])return dep[u];
    return dep[u] = calc(f[u])+1;
}
int main(){
    int n, m;  cin>>n>>m;
    for(int i = 1; i <= n; i++){
        int x;  cin>>x;  f[i] = x;
        if(f[i]==-1)rt=i;
    }
    int mx = 0; //维护当前最大距离
    while(m--){
        int x;  cin>>x;
        dfs(x, 0); //每次从这个点跑就行, 根直接当做普通点处理
        mx = max(mx, calc(x));
        cout<<tmp-mx<<"\n";
    }
    return 0;
}

L2-044 大众情人(25分)

//用距离感建有向图，Floyd计算全图最短路即可，不知道哪里错了，重写一遍过了
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e6+10;
const int inf = 1e9+10;
struct node{int to, d;};
int e[510][510];
int sex[510];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int n;  cin>>n;
    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            e[i][j] = inf;
    //floyed
    for(int i = 1; i <= n; i++){
        string op;  cin>>op;
        if(op=="F")sex[i] = 0; else sex[i] = 1;//男1
        int k;  cin>>k;
        for(int j = 1; j <= k; j++){
            int to, d; char ch;
            cin>>to>>ch>>d;
            e[i][to] = d;
        }
    }
    for(int k = 1; k <= n; k++){
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= n; j++){
                if(e[i][j] > e[i][k]+e[k][j]){
                    e[i][j] = e[i][k]+e[k][j];
                }
            }
        }
    }
    //solve
    vector<int>girl, boy;
    map<int,int>p;
    for(int i = 1; i <= n; i++){
        int d = -1;
        for(int j = 1; j <= n; j++){
            if(sex[j]!=sex[i]){
                d = max(d, e[j][i]);
            }
        }
        if(d != -1){
            p[i] = d;
            if(sex[i])boy.push_back(i);
            else girl.push_back(i);
        }
    }
    sort(girl.begin(), girl.end(), [&p](int x, int y){
        return p[x]==p[y]? x<y : p[x]<p[y];
    });
    sort(boy.begin(), boy.end(), [&p](int x, int y){
        return p[x]==p[y]? x<y : p[x]<p[y];
    });
    for(int i = 0; i < girl.size(); i++){
        if(p[girl[i]] == p[girl[0]]){
            if(i!=0)cout<<" ";
            cout<<girl[i];
        }else break;
    }
    cout<<"\n";
    for(int i = 0; i < boy.size(); i++){
        if(p[boy[i]] == p[boy[0]]){
            if(i!=0)cout<<" ";
            cout<<boy[i];
        }else break;
    }
    cout<<"\n";
    return 0;
}

参考资料

官网题解：https://mp.weixin.qq.com/s/gQwlVQoeJfY29jgjG4A66g