开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> 2019~2021近三年天梯赛L2题目练习 -> 正文阅读

[数据结构与算法]2019~2021近三年天梯赛L2题目练习

2021

L1-06 吉老师的回归（字符串）

思路

这个题并无难点，纯粹是为了复习一下字符串的相关操作。

读入一行字符串：

getline(cin,str1); //对于string类读入，前面的输入是cin>>ss;的话，str会读取上一行的结束符。

char str2[30];
cin.getline(str2,30);//读入整行数据，它使用回车键输入的换行符来确定输入结尾。第一个参数用来存储输入行的数组名称，第二个参数len是要读取的字符数。
cin.get(str2, 30);//和上面的区别在于不会读入换行符

代码

#include <bits/stdc++.h>
using namespace std;

int main() 
{
    std::ios::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;
    string str,word;
    int cnt = 0;
    getline(cin,str);
    while(n--) {
        getline(cin,str);
        stringstream ss;
        ss << str;
        bool flag = true;
        while (ss >> word)
        {
            if(word.find("qiandao")!= word.npos || word.find("easy")!= word.npos) {
                flag = false;
                break;
            }
        }
        if(cnt == m && flag) {
            cout<<str<<endl;
            return 0;
        }
        if(flag) cnt++;
    }
    cout<<"Wo AK le"<<endl;
    return 0;
}

L2-09 包装机（栈，模拟）

题目：https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652360

思路

注意审题：如果轨道已经空了，再按对应的按钮不会发生任何事；同样的，如果筐是空的，按 0 号按钮也不会发生任何事。

一个模拟题，考察stl的运用。

代码

#include <bits/stdc++.h>
using namespace std;
unordered_map<int, queue<char>> g;
stack<int> st;
vector<char> ans;

int main() 
{
    std::ios::sync_with_stdio(false);
    int n, m, s, t;
    string str;
    cin>>n>>m>>s;
    for(int i = 1; i <= n; i++) {
        cin>>str; 
        for(auto c:str)
            g[i].push(c);
    }
    while(cin>>t && t != -1){
        if(t == 0 && st.size() != 0) {
            ans.push_back(st.top());
            st.pop();
        }
        if(t == 0) continue;

        if(g[t].size() != 0) {
            char c = g[t].front();
            if(st.size() == s)  {
                ans.push_back(st.top());
                st.pop();
            }
            g[t].pop();
            st.push(c);
        }
    }
    for(auto v :ans)
        cout<<v;
    cout<<endl;
    return 0;
}

L2-10 病毒溯源（dfs，路径存储）

思路

搜索到叶子结点的时候vector可以直接比较大小

内存超限的问题搞了巨久，教训：不要在递归的时候传入vector

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 10005;
vector<int> g[maxn];
int pre[maxn];
int len = 0;

vector<int> ans,road;

void dfs(int u) {
    for(auto v : g[u]) {
        road.push_back(v);
        dfs(v);
        road.pop_back();
    }
    if(g[u].size() == 0) {
        if( road.size() > len) {
            len = road.size();
            ans = road;
        }
        if(road.size() == len) 
            ans = min(ans,road);
    }
}


int main() 
{
    std::ios::sync_with_stdio(false);
    ans.reserve(maxn);
    
    int n , k, u, head;
    cin>>n;
    for(int i= 0; i < n; i++) 
        pre[i] = -1;
    
    for(int i = 0; i< n; i++) {
        cin>>k;
        while(k--) {
            cin>>u;
            g[i].push_back(u);
            pre[u] = i;
        }
    }
    for(int i = 0; i < n; i++) {
        if(pre[i] == -1) {
            head = i;
            break;
        }
    }
    road.push_back(head);
    dfs(head);

    cout<<len<<endl;
    for(int i = 0;i< ans.size();i ++){ 
        if(i == ans.size() - 1) cout<<ans[i]<<endl;
        else cout<<ans[i]<<" ";
    }
    return 0;
}

L2-11清点代码库（STL，模拟）

思路

简单模拟题，map统计个数，sort一下输出就ok

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
typedef pair<int, vector<int> > PIV ;
const int maxn = 10050;
map<vector<int>,int> mp; //模块的个数
vector<PIV> ans;

bool cmp(PIV a, PIV b) {
    if(a.first == b.first) {
        return a.second < b.second;
    }
    return a.first > b.first;
}

int main() 
{
    std::ios::sync_with_stdio(false);
    int n,m,u;
    cin>>n>>m;
    for(int i = 0;i < n; i++ ) {
        vector<int> fu; // bug1，忘记清空
        for(int j = 0;j < m;j++) {
            cin>>u;
            fu.push_back(u);
        }
        if(mp.find(fu) == mp.end()){
            ans.push_back({0,fu});
            mp[fu] = 1;
        } else mp[fu]++;  
    }
 
    for(int i = 0;i <ans.size();i++) 
        ans[i].first = mp[ans[i].second] ;      
    sort(ans.begin(),ans.end(),cmp);
    
    cout<<ans.size()<<endl;;
    for(auto u : ans) {
        cout<<mp[u.second];
        for(auto v : u.second)
            cout<<" "<<v;
        cout<<endl;
    }

    return 0;
}

L2-12 哲哲打游戏（模拟）

题目:https://pintia.cn/problem-sets/994805046380707840/problems/1386335159927652363

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 100005;
vector<int> g[maxn];
int ma[maxn];

int main() 
{
    std::ios::sync_with_stdio(false);
    int n,m,k,op,j,u;
    cin>>n>>m;
    for(int i = 1;i <= n;i++) {
        cin>>k;
        for(int j = 0;j < k ;j++) { 
            cin>>u;
            g[i].push_back(u);
        }
    }
    int now = 1;
    while(m--) {
        cin>>op>>j;
        if(op == 0){
            now = g[now][j - 1];
        }else if(op == 1){
            ma[j] = now;
            cout<<now<<endl;
        } else {
            now = ma[j];
        }
    }
    cout<<now<<endl;
    return 0;
}

2020

L2-09 简单计算器（模拟,栈）

题目：https://pintia.cn/problem-sets/994805046380707840/problems/1336215880692482056

思路

按题意模拟即可，注意要判断栈里是否为空

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 10005;
stack<int> s1;
stack<char> s2;

int main() 
{
    std::ios::sync_with_stdio(false);
    int n, a,b;
    char op;
    cin>>n;
    for(int i = 0; i < n; i++){
        cin>>a;
        s1.push(a);
    }
    for(int i = 0;i < n - 1; i++){
        cin>>op;
        s2.push(op);
    }
    while(!s1.empty() || !s2.empty()) {
        a = s1.top();
        s1.pop();
        if(!s1.empty()){ 
            b = s1.top();
            s1.pop();
        } else {
            cout<<a<<endl;
            break;
        }
        op = s2.top();
        s2.pop();
        int c;
        if(op == '/' ){
            if( a == 0) {
                printf("ERROR: %d/0", b);
                break;
            }
            c = b/a;
        }else if(op == '*') c = b * a;
        else if (op == '-') c = b - a;
        else c = b + a;
        s1.push(c);
    }
    return 0;
}

L2-10 口罩发放（大模拟）

思路

恶心人的模拟题，注意审题！！！

合法记录的身份证号 必须是 18 位的数字

需要注意最后输出按顺序只能用数组/vector，因为哈希表映射的顺序是随机的，无法保证按顺序输出。

unordered_map和unordered_set，用迭代器输出的话，输出顺序应该是哈希表从前往后的顺序，也不可能是输入到容器中的元素的顺序。

只能拿到20分，找不到错在哪了orz

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1005;
struct people {
    string name,id,time;
    int si,cnt;

    bool operator < (const people &p) const {
        if(time == p.time) {
            return cnt < p.cnt;
        }
        return time < p.time;
    } 
};
vector<people> re;

unordered_map<string,int> lastD,vis;
unordered_map<string,people> mp;
vector<string> WarnP;

bool check(string id) {
    if(id.size() != 18) return false;
    for(auto v :id) {
        if(v < '0' || v > '9') return false; //注意题目必须是数字
    }
    return true;
}

int main() 
{
    std::ios::sync_with_stdio(false);
    int d,p,t,s;
    char ch;
    cin>>d>>p;
    for(int i = 1; i<= d; i++) {
        cin>>t>>s;
        re.clear();
        people pe;
        for(int j = 0;j < t; j++) {
            cin>>pe.name>>pe.id>>pe.si>>pe.time;
            pe.cnt = j;
            if(!check(pe.id)) continue;
            
            re.push_back(pe);
            mp[pe.id] = pe;
            
            if(pe.si == 1 && vis[pe.id] == 0) {
                WarnP.push_back(pe.id);
                vis[pe.id] = 1;
            }
        }

        sort(re.begin(), re.end());
        for(auto now :re){
            if(lastD[now.id] != 0 && i < lastD[now.id] + p + 1 )
                continue;
            lastD[now.id] = i;
            cout<<now.name<<" "<<now.id<<endl;
            s--;
            if(s == 0) break;
        }
    }
    for(auto v :WarnP) {
        cout<<mp[v].name<<" "<<mp[v].id<<endl;
    }
    
    return 0;
}

L2-11 完全二叉树的层序遍历（搜索，树的遍历）

思路

这个题目相当于已经给出了树的形状，按照二叉树的后序遍历的顺序给对应的位置赋值即可。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1005;
int hx[maxn],tr[maxn];
int cnt = 1;

void dfs(int x)
{
    if(tr[x] == 0)
        return;
    dfs(x * 2);
    dfs(x * 2 + 1);
    tr[x] = hx[cnt++];
}

int main() 
{
    std::ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i = 1; i <=n;i++) {
        cin>>hx[i];
        tr[i] = 1;
    }
    dfs(1);
    for(int i = 1;i <=n; i++) {
        if(i == n) cout<<tr[i]<<endl;
        else cout<<tr[i]<<" ";
    }
    
    return 0;
}

L2-12 网红点打卡攻略（模拟）

思路

对k个攻略一个个检验即可

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 205;
int g[maxn][maxn];
int V[maxn];
int cnt = 0;
int Mcost = INF;
int num = 0;
int main() 
{
    std::ios::sync_with_stdio(false);
    memset(g ,INF, sizeof g);
    int n,m,u,v,c,k;
    cin>>n>>m;
    while(m--) {
        cin>>u>>v>>c;
        g[u][v] = g[v][u] = c;
    }
    cin>>k;
    int N;
    for(int i = 1;i <= k; i++)
    {
        cin>>N;
        bool flag = true;
        if(n != N) flag = false;
        int cost = 0;
        unordered_set<int> vis;
        for(int j = 0;j < N; j++) {
            cin>> v;
            vis.insert(v);
            if(!flag) continue;
            V[j] = v;
            if((j == 0 && g[v][0] == INF) ||(j == N-1 && g[v][0] == INF) || ( j != 0 && g[v][V[j - 1]] == INF) )  {
                flag = false;
            }
            if(j == 0 || j == N - 1)  cost += g[v][0];
            if(j != 0) 
                cost += g[v][V[j - 1]]; //bug2,最后一点也在
        }
        if(vis.size() != N) flag = false; //bug1,，注意所有的点也要访问到
        if(!flag) continue;
        cnt++;
        if(cost < Mcost) {
            Mcost = cost;
            num = i;
        }
    }
    cout<<cnt<<endl;
    cout<<num<<" "<<Mcost<<endl;
    return 0;
}

2019

L2-029 特立独行的幸福（模拟）

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 10005;
int p[maxn] = {0};
int xf[maxn];
int a,b;

void InitPrime(int x) {
    for(int i = 2 ;i <= sqrt(x) + 5; i++) {
        for(int j = 2; j * i <= x; j++) {
            p[i * j] = 1;
        }
    }
}

int judge(int x){
    int vis[maxn] = {0};
    int next = x;
    vector<int> save;
    bool flag = false;
    while(next != 1 && vis[next] != 1) {
        x = next;
        next = 0;
        vis[x] = 1;
        while(x > 0) {
            next += (x%10) *(x%10);
            x /= 10;
        }
        save.push_back(next);
    }
    if(next != 1)  return 0;
    for(auto v : save) {
        if(v >= a && v <= b)
            xf[v] = 0;
    }
    return save.size();
}

int main() 
{
    std::ios::sync_with_stdio(false);
    cin>>a>>b;
    InitPrime(b);
    p[1] = 1;
    memset(xf ,1 ,sizeof xf);
    for(int i = a;i <= b; i++) {
        if(!xf[i]) continue;
        xf[i] = judge(i);
        if(!p[i]) 
            xf[i] *= 2;
    }
    bool flag = false;
    for(int i = a;i <= b; i++) {
        if(xf[i] != 0) {
            cout<<i<<" "<<xf[i]<<endl;
            flag = true;
        }
    }
    if(!flag) puts("SAD");
    return 0;
}

L2-030 冰岛人（大模拟）

https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858887

思路

看起来是最近公共祖先，其实是一个大模拟。

把五代以内的祖先放到一个集合里头，没有重复说明没有。

但是不知道代码哪里有问题，能过样例，然而一个点都不过了。

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 10005;
unordered_map<string,pair<string,char> > mp;
unordered_set<string> pa; //五代内祖先

int main() 
{
    int n,m;
    cin>>n;
    string Fname,Sname;
    while(n--) {
        cin>>Fname>>Sname;
        int l = Sname.size();
        if(Sname[l - 1] == 'm' || Sname[l - 1] == 'f') 
            mp[Fname] = {"", Sname[l - 1]};
        else if (Sname[l - 1] == 'n') {
            Sname = Sname.substr(0,l - 4);
            mp[Fname] = {Sname, 'm'};
        } else if (Sname[l - 1] == 'r') {
            Sname = Sname.substr(0,l - 7);
            mp[Fname] = {Sname, 'f'};
        } 
        cout<<Sname<<endl;
    }
    cin>>m;
    string f1,s1,f2,s2;
    while(m--) {
        pa.clear();
        cin>>f1>>s1>>f2>>s2;
        if(mp.count(f1) == 0 || mp.count(f2) == 0){
            cout<<"NA"<<'\n';
            continue;
        }
        if(mp[f1].second == mp[f2].second) {
            cout<<"Whatever"<<'\n';
            continue;
        }
        int cnt = 1;
        string p1 = f1,p2 = f2;
        pa.insert(f1);
        pa.insert(f2);
        bool flag = true;
        while(cnt < 4) {
            p1 = mp[p1].first;
            if(pa.count(p1) ==  0)
                pa.insert(p1);
            else {
                flag = false;
                break;
            }
           
            p2 = mp[p2].first;
            if(pa.count(p2) == 0)
                pa.insert(p2);
            else {
                flag = false;
                break;
            }
            cnt++;
        }
        if(flag) cout<<"Yes"<<"\n";
        else cout<<"No"<<'\n';
    }
    return 0;
}

L2-031 深入虎穴（dfs，树）

题目：https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858888

思路

迷宫只有一个入口，所以没有出现的就是根节点。

从根节点dfs，保存叶节点上深度最深的点的序号。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
vector<int> g[maxn];
int vis[maxn];
int H = 0,e = 0;
void dfs(int u,int h) {
    for(auto v : g[u]) {
        dfs(v, h +1 );
    }
    if(h > H){
        H = h;
        e = u;
    }
}

int main()
{
    std::ios::sync_with_stdio(false);
    int n,k,j;
    cin>>n;
    for(int i = 1; i <= n;i ++) {
        cin>>k;
        while(k--) {
            cin>>j;
            vis[j] = 1;
            g[i].push_back(j);
        }
    }
    int s;
    for(int i = 1;i <= n; i++) {
        if(vis[i] == 0){
            s = i;
            break;
        }
    }
    dfs(s, 1);
    cout<<e<<endl;
    return 0;
}

L2-032 彩虹瓶 (栈)

代码

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 1005;

int main() 
{
    std::ios::sync_with_stdio(false);
    int n,m,k;
    cin>>n>>m>>k;
    while(k--) {
        stack<int> st; //每一次栈是新的，因为这里找了一万年bug麻了
        int ne = 1;
        int vis[maxn] = {0};
        int u;
        bool flag = true;
        for(int i = 0; i <n ;i++) {
            cin>>u;
            if(!flag) continue;
            vis[u] = 1;
            if(ne == u) ne++;
            else if(!vis[ne]) {
                st.push(u);
                if(st.size() > m) {  //超出容量限制
                    flag = false;
                }
            } 
            //出现过
            while(vis[ne]) {
                if(st.top() != ne){ 
                    flag = false;
                    break;
                } else {
                    ne++;
                    st.pop();
                }
            }
            
        }
        if(flag) cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}