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 
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 
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 
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 
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 
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 
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 口罩发放（大模拟） 思路

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

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

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

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

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

代码

#include 
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 
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 
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 
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 
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 
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 
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;
}

总结

回顾一下近三年的题，L2主要是模拟，基本必定会涉及栈、stl、dfs