Skip to main content

2021GPLT团体天梯赛

如果是简单题的话，会记录一些stl的写法，我觉得在这个比赛里面，会用stl是非常巨大的优势。

大部分思路来自俊杰_Charles | 2021GPLT 团体程序设计天梯赛 个人题解

L1-3 强迫症 (10 分)​

将“年年月月”或“年年年年月月”格式的字符串格式化为“年年年年-月月”

提示

string类型有一个substr方法，用于截取字串

stoi用于将字符串转化为数字

#include <bits/stdc++.h>

using namespace std;

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

    return 0;
}

L1-6 吉老师的回归 (15 分)​

给定 nn 个字符串，输出第 m+1m+1 个不含 "qiandao" 或 "easy" 子串的字符串，若满足条件的字符串不超过 mm 个则输出 "Wo AK le"。

提示

getline(cin, str) 函数用于读入一行字符串

str.find("target") == string::npos 代表字符串变量 str 中，没有字串为 target 的字符串。string::npos 是一个静态常量

我是真的很好奇，为什么比赛的时候有4分拿不到，迷迷糊糊的

#include <bits/stdc++.h>

using namespace std;

int n, m;
vector<string> v;

int main (){
    cin >> n >> m;
    string s;
    getline(cin, s); // 捕获没用的\n
    for (int i = 1; i <= n; ++ i) {
        string str;
        getline(cin, str);
        if (str.find("qiandao") == string::npos && str.find("easy") == string::npos) {
            // 说明它是一道难题
            v.push_back(str);
        }
    }
    
    // 如果难题做完了
    if (v.size() <= m) cout << "Wo AK le";
    // 输出正在做的题
    else cout << v[m];
    
    return 0;
}

L1-7 天梯赛的善良 (20 分)​

给定 nn 个数，求最大的数及其个数，以及最小的数及其个数。

提示

运用map容器

前向迭代器：m.begin()，指向头部的迭代器

反向迭代器：m.rbegin()，指向尾部的迭代器

#include<bits/stdc++.h>

using namespace std;

const int N = 20010;

map<int, int> m;

int n;
int max_index, min_index;

int main (){
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
        int x;
        cin >> x;
        m[x] ++;
    }
    
    cout << m.begin()->first << " " <<m.begin()->second << endl;
    cout << m.rbegin()->first << " " << m.rbegin()->second <<endl;
    
    return 0;
}

L1-8 乘法口诀数列 (20 分)​

给定的两个 11 位数字 a1a_1 和 a2a_2，生成一个数列 {an}\{a_n\}，规则为从 a1a_1 开始顺次进行，每次将当前数字与后面一个数字相乘，将结果贴在数列末尾。如果结果不是 11 位数，则其每一位都应成为数列的一项。

提示

string str = to_string(x)用于将变量x变成字符串的形式

#include <bits/stdc++.h>

using namespace std;

vector<int> v;

int a, b, n;
int ind = 1;

int main (){
    cin >> a >> b >> n;
    v.push_back(a);
    v.push_back(b);
    while (v.size() < n + 1) {
        int x = v[ind], y = v[ind - 1];
        int z = x * y;
        string s = to_string(z);
        for (char c : s) {
            v.push_back(c - '0');
        }
        ind ++;
    }
    for (int i = 0; i < n; ++ i) cout << v[i] << ( i == n - 1 ? "" : " ");
    
    return 0;
}

L2-1 包装机 (25 分)​

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

提示

c++中的string可以用类似栈的操作。例如back() push_back()

string 翻转 reverse(str.begin(), str.end())

#include <bits/stdc++.h>

using namespace std;

int n, m, s;
string able[110];
string line, res;

int main (){
    cin >> n >> m >> s;
    for (int i = 1; i <= n; ++ i) {
        cin >> able[i];
        // 翻转之后，方便从尾部取出元素
        reverse(able[i].begin(), able[i].end());
    }
    
    while (true) {
        int o;
        cin >> o;
        if (o == -1) break;
        // 抓
        if (o == 0) {
            // 流水线空了
            if (line.size() == 0) continue;
            res.push_back(line.back());
            line.pop_back();
        } else {
            // 轨道空了
            if (able[o].size() == 0) continue;
            // 流水线满了，强行取出
            if (line.size() == s) {
                res.push_back(line.back());
                line.pop_back();
            }
            line.push_back(able[o].back());
            able[o].pop_back();
        }
    }
    cout << res;
    
    return 0;
}

L2-2 病毒溯源 (25 分)​

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

提示

使用vector存储邻接表，由于需要最小序列，在输入每一行后需要排序。sort(e.begin(), e.end())

必须记忆化搜索，否则会超时

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

int n, k, x;

vector<int> e[N];
int nex[N]; // 记录当取得最大值时，i的下一个指向谁
int dist[N]; // 记录从i开始取得的最长链的长度

int dfs(int now) {
    if (dist[now] != 0) return dist[now];
    int res = 1;
    for (int i = 0; i < e[now].size(); ++ i) {
        int to = e[now][i]; //能去的下一个点
        int wait = dfs(to) + 1;
        if (res < wait) {
            res = wait;
            nex[now] = to;
        }
    }
    dist[now] = res;
    return res;
}

int main (){
    cin >> n;
    for (int i = 0; i < n; ++ i) {
        cin >> k;
        for (int j = 0; j < k; ++ j) {
            cin >> x;
            e[i].push_back(x);
        }
        // 给边排个序
        sort(e[i].begin(), e[i].end());
    }
    
    // 当nex为-1时，达到链的末尾
    memset(nex, -1, sizeof nex);
    
    // 找最第一个最长链
    int m = -1;
    for (int i = 0; i < n; ++ i) {
        if (m == -1 || dfs(m) < dfs(i)) {
            m = i;
        }
    }
    cout << dfs(m) << endl;
    while (m != -1) {
        cout << m << (nex[m] == -1 ? "" : " ");
        m = nex[m];
    }

    
    return 0;
}

L2-3 清点代码库 (25 分)​

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

提示

map里面可以存vector，例如map<vector<int>, int> cnt

然后再丢到一个vector里排序，vector<pair<int, vector<int>>>

排序的时候可以先取负，这样sort的时候就是降序了

#include <bits/stdc++.h>

using namespace std;

const int N = 10010;

// 统计每个vector的个数
map<vector<int>, int> cnt;
map<vector<int>, int>::iterator it;

// map无法排序
// 配合 vector 和 pair 可以排了
vector<pair<int, vector<int>>> res;

int n, m, x;

int main (){
    cin >> n >> m;
    for (int i = 0; i < n; ++ i) {
        vector<int> v;
        for (int j = 0; j < m; ++ j) {
            cin >> x;
            v.push_back(x);
        }
        cnt[v] ++;
    }
    for (it = cnt.begin(); it != cnt.end(); it++) {
        res.push_back({-it->second, it->first});
    }
    sort(res.begin(), res.end());

    cout << res.size() << endl;
    for (int i = 0; i < res.size() ; ++ i) {
        cout << -res[i].first;
        vector<int> output = res[i].second;
        for (int j = 0; j < output.size(); ++ j) {
            cout << " " << output[j];
        }
        cout << endl;
    }
    
    return 0;
}

L2-4 哲哲打游戏 (25 分)​

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

提示

比前面的题都简单，就一个邻接表，真不知道比赛的时候为什么不写这道题

#include <bits/stdc++.h>

using namespace std;

const int N = 100010;

vector<int> e[N]; // 邻接表
int sav[N]; // 存档点
int n, m, t, x, o, p, now = 1;

int main (){
    cin >> n >> m;
    for (int i = 1; i <= n; ++ i) {
        cin >> t;
        for (int j = 1; j <= t ; ++ j) {
            cin >> x;
            e[i].push_back(x);
        }
    }
    
    while (m --) {
        cin >> o >> p;
        // 走
        if (o == 0) {
            now = e[now][p-1];
        }
        // 存档
        if (o == 1) {
            sav[p] = now;
            cout << now << endl;
        }
        // 读取存档
        if (o == 2) {
            now = sav[p];
        }
    }
    cout << now;
    return 0;
}

L3-2 还原文件 (30 分)​

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

提示

将高度转换成字符串，然后通过find方法找到匹配的下标，然后给它排个序

但是这样只能拿到26分，因为可以有多个字串存在，然而find函数只返回第一次匹配的下标

#include <bits/stdc++.h>

using namespace std;

int n, m;
string source;
vector<pair<int, int>> res;

int main() {
    cin >> n;
    for (int i = 0; i < n; ++ i) {
        int x;
        cin >> x;
        source.push_back(x);
    }
    cin >> m;
    for (int i = 1; i <= m; ++ i) {
        int t;
        cin >> t;
        string target;
        while(t --) {
            int x;
            cin >> x;
            target.push_back(x);
        }
        res.push_back({source.find(target), i});
    }
    sort(res.begin(), res.end());
    for (int i = 0; i < res.size(); ++ i) {
        cout << res[i].second << (i + 1 == res.size() ? "" : " ");
    }
    
    return 0;
}