SMU 2024 spring 天梯赛1

SMU 2024 spring 天梯赛1

7-1种钻石

查看代码

void solve() {
    int n,v;
    cin>>n>>v;
    cout<<n/v;
}

7-21-1 输出金字塔图案

查看代码

 void solve() {
    cout<<"   *\n"
          "  ***\n"
          " *****\n"
          "*******";
}

7-3强迫症

查看代码

 void solve() {
    string s;
    cin>>s;
    if(s.size()==6){
        s.insert(s.begin()+4,'-');
        cout<<s;
    }else{
        string l=s.substr(0,2);
        int a= stoi(l);
        if(a<22){
            s="20"+s;
        }else s="19"+s;
        s.insert(s.begin()+4,'-');
        cout<<s;
    }
}

7-4小孩子才做选择，大人全都要

题目有点抽象…

查看代码

 void solve() {
    int a,b;
    cin>>a>>b;
    int ma=max({a, b,0ll});
    int c=max(0ll,a+b);
    cout<<ma<<' '<<c<<'\n';
    if(a<0&&b<0)cout<<"-_-";
    else if(a<0||b<0)cout<<"T_T";
    else cout<<"^_^";
}

7-5胎压监测

查看代码

 void solve() {
    vector<PII>ve(4);
    int low,d;
    for(int i=0;i<4;++i)cin>>ve[i].first,ve[i].second=i+1;
    cin>>low>>d;
    int p,cnt=0;
    sort(ve.begin(),ve.end());
    for(int i=0;i<3;++i){
        if(ve[3].first-ve[i].first>d||ve[i].first<low)cnt++,p=ve[i].second;
    }
    if(ve[3].first<low)cnt++,p=ve[3].second;
    if(cnt==0)cout<<"Normal";
    else if(cnt==1)cout<<"Warning: please check #"<<p<<"!";
    else cout<<"Warning: please check all the tires!";
}

7-6吉老师的回归

查看代码

 void solve() {
    int n,m;
    cin>>n>>m;
    vector<string>ve(n);
    int idx=0;
    string ans="Wo AK le";
    bool ok=true;
    ::getchar();
    for(int i=0;i<n;++i){
        getline(cin,ve[i]);
        if(ve[i].find("qiandao")==-1&&ve[i].find("easy")==-1)++idx;
        if(idx==m+1&&ok){
            ans=ve[i];
            ok=false;
        }
    }
    cout<<ans;
}

7-7静静的推荐

思路：一个名单内PTA分数严格递增，若分数相同需到达面试分数线，对于有多个分数相同的人中，到达面试分数线的人可以任意的加进名单里，而没到达面试分数的人一个名单只能有一个，统计下每个分数已用的名单，若有没到达面试分数打的人，判断下是否还剩下名单

查看代码

 bool cmp(PII a,PII b){
    if(a.first!=b.first)return a.first>b.first;
    return a.second>b.second;
}
void solve() {
    int n,k,s;
    cin>>n>>k>>s;
    vector<int>cnt(300);
    vector<PII>f(n);
    for(int i=0;i<n;++i)cin>>f[i].first>>f[i].second;
    sort(f.begin(),f.end(),cmp);
    int ans=0;
    for(int i=0;i<n;++i){
        if(f[i].first<175)break;

        if(f[i].second>=s)ans++;
        else if(cnt[f[i].first]+1<=k){
            ans++,cnt[f[i].first]++;
        }
    }
    cout<<ans;
}

7-8机工士姆斯塔迪奥

思路：每一行每一列的个数已定，找出有多少行以及多少列，但是还存在重复覆盖的格子，每一行与每一列都会有一个重复覆盖的格子，行数乘列数即为总重复覆盖数

查看代码

 void solve() {
    int n,m,q;
    cin>>n>>m>>q;
    set<int>x,y;
    while(q--){
        int a,b;
        cin>>a>>b;
        if(a==0)x.insert(b);
        else y.insert(b);
    }
    int xx=x.size(),yy=y.size();
    int c=xx*m+yy*n-xx*yy;
    cout<<n*m-c;
}

7-9彩虹瓶

思路：模拟啦，想清楚过程就比较好写

查看代码

 void solve() {
    int n,m,k;
    cin>>n>>m>>k;
    while(k--){
        vector<int>ve(n),st(n);
        for(int i=0;i<n;++i)cin>>ve[i];
        stack<int>s;
        int idx=0,now=0;
        bool ok=true;
        while(now<n){
            while(!s.empty()&&s.top()==now+1&&now+1<=n){
                now++,s.pop();
            }
            if(now==n)break;
            while(idx<n&&ve[idx]!=now+1){
                if(s.size()==m){
                    ok=false;
                    break;
                }else{
                    s.push(ve[idx++]);
                }
            }
            if(!ok)break;
            if(idx<n&&ve[idx]==now+1){
                now++,idx++;
            }else{
                ok=false;
                break;
            }
        }
        if(ok)cout<<"YES\n";
        else cout<<"NO\n";
    }
}

7-10简单计算器

思路：题目已经告诉怎么做啦，写就对了

查看代码

 void solve() {
    int n;
    cin>>n;
    stack<int>s1;
    stack<char>s2;
    for(int i=0;i<n;++i){
        int x;
        cin>>x;
        s1.push(x);
    }
    for(int i=1;i<n;++i){
        char x;
        cin>>x;
        s2.push(x);
    }
    while(s1.size()>1){
        int n1=s1.top();s1.pop();
        int n2=s1.top();s1.pop();
        char op=s2.top();s2.pop();
        if(op=='+')s1.push(n2+n1);
        else if(op=='-')s1.push(n2-n1);
        else if(op=='*')s1.push(n2*n1);
        else if(op=='/'){
            if(n1==0){
                cout<<"ERROR: "<<n2<<"/"<<n1;
                return ;
            }
            else s1.push(n2/n1);
        }
    }
    cout<<s1.top();
}

7-11龙龙送外卖

思路：手动画画图，发现就是连接所有送餐点的最小连通块，由于最后一点送完不用跑回外卖店，来回总路径再减去最长的一条送餐路线

—-错了几发，找不到哪错，果然又是题读漏了（外卖店以为就是1

查看代码

 #include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=1e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-12;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};

int n,m,p;
vector<int>g;
vector<int>d;
int all=0,ma=0,len;
void dfs(int u){
    if(d[u]!=-1||u==p)return ;
    if(d[g[u]]==-1){
        dfs(g[u]);
    }
    len++;
    d[u]=d[g[u]]+1;
    return ;
}
void solve() {

    cin>>n>>m;
    d=g=vector<int>(n+1,-1);
//    d[1]=0;
    for(int i=1;i<=n;++i){
        cin>>g[i];
        if(g[i]==-1)p=i;
    }
    d[p]=0;
    for(int i=0;i<m;++i){
        int x;
        cin>>x;
        len=0;
        dfs(x);
        ma=max(ma,d[x]);
        all+=len*2;
//        cout<<all<<'\n';
        cout<<all-ma<<"\n";
//        cout<<d[x]<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
//    cin>>t;
//    init();
    while(t--){
        solve();
    }
    return 0;
}

7-12智能护理中心统计

思路：暴力

统计所有管理节点的老人个数，T就将老人修改到目标管理节点即可。Q就跑dfs求子树的老人个数

查看代码

 #include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=3e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int MAXN=1e8+5;
const double eps=1e-12;
const int dx[4]={-1,1,0,0};
const int dy[4]={0,0,-1,1};

vector<int>old,up;
vector<vector<int>>down;
vector<int>have;
int n,m,idx=1;
map<string,int>mp;
void updown(int u,int d){
    have[u]+=d;
//    if(up[u]!=-1){
//        updown(up[u],d);
//    }
}
int downn(int u){
    int ans=have[u];
    for(auto v:down[u]){
        if(up[v]==u){
            ans+=downn(v);
        }
    }
    return ans;
}
void solve() {
    cin>>n>>m;
    old=vector<int>(n+1,-1);
    up=vector<int>(N+1,-1);
    down=vector<vector<int>>(N+1);
    have=vector<int>(N+1,0);
    for(int i=0;i<m;++i){
        string a,b;
        cin>>a>>b;
        if(mp.count(b)==0)mp[b]=idx++;
        int fa=mp[b];
        if(a[0]>='0'&&a[0]<='9'){
            int aa=stoi(a);
            old[aa]=fa;
            have[fa]++;
        }else{
            if(mp.count(a)==0)mp[a]=idx++;
            int son=mp[a];
            down[fa].push_back(son);
            up[son]=fa;
        }
    }
    char op;
//    int x=mp["XAHP"];
//    cout<<have[x]<<'\n';
    cin>>op;
    while(op!='E'){
        if(op=='Q'){
            string b;
            cin>>b;
            if(mp.count(b)==0){
                mp[b]=idx++;
            }
            int ans=downn(mp[b]);
            cout<<ans<<'\n';
        }else if(op=='T'){
            int a;
            string b;
            cin>>a>>b;
            if(old[a]==-1){
                if(mp.count(b)==0)mp[b]=idx++;
                old[a]=mp[b];
                have[mp[b]]++;
            }else{
                if(mp.count(b)==0)mp[b]=idx++;
                int fa=old[a];
//                updown(fa,-1);
                have[fa]--;
                old[a]=mp[b];
                have[mp[b]]++;
//                updown(mp[b],1);
            }
        }
        cin>>op;
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
//    cin>>t;
//    init();
    while(t--){
        solve();
    }
    return 0;
}

7-13计算图

7-14教科书般的亵渎

7-15超能力者大赛