526互联

西南民族大学 春季 2023 训练赛 8

发布时间 2023-04-18 22:09:48作者: bible_w

西南民族大学 春季 2023 训练赛 8

吃火锅

思路：每行只算一个（*^*）

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int all,p,a;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    
    string b="chi1 huo3 guo1";
    while(1){
        string s;
        getline(cin,s);
        if(s==".")break;
        all++;
        int t;
        t=s.find(b);
        if(t!=-1){
            if(a==0)p=all;
            a++;
        }
    }
    cout<<all<<'\n';
    if(a==0)cout<<"-_-#";
    else cout<<p<<' '<<a;
    return 0;
}
View Code

 

前世档案

思路：

1.左子树 （*2），右子树 （*2+1），减去2^n即为结论数 

2.记录当前节点的叶子节点数为k，若是'y'，ans不变，若是'n'，ans加上k/2 (看图即可理解)

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int n,m;

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int k=pow(2,n);
    for(int i=0;i<m;++i){
        int zi=k;
        string s;
        cin>>s;
        int ans=1;
        for(int j=0;j<s.size();++j){
            if(s[j]=='n')ans+=zi/2;
            zi/=2;
        }
        cout<<ans<<'\n';
    }
    return 0;
}
View Code 1
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int n,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int k=pow(2,n);
    for(int i=0;i<m;++i){
        int a=1;
        string s;
        cin>>s;
        for(int j=0;j<s.size();++j){
            a*=2;
            if(s[j]=='n')a+=1;
        }
        cout<<a-k+1<<'\n';
    }
    return 0;
}
View Code 2

 

口罩发放

思路：模拟...

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
const int N=2e2+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int D,P;
unordered_map<string,int>pre,st;
struct E{
    string na,id,t;
    int p;
    bool operator<(const E&e)const{
        if(t!=e.t)
            return t<e.t;
        return p<e.p;
    }
};
struct EE{
    string na,id;
};
vector<EE>ans1,ans2;
bool check(string s){
    for(int i=0;i<s.size();++i){
        if(s[i]<'0'||s[i]>'9')return false;
    }
    return true;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>D>>P;
    for(int i=1,T,S;i<=D;++i){
        cin>>T>>S;
        vector<E>ve;
        for(int j=0;j<T;++j){
            string s1,s2,t;
            int op;
            cin>>s1>>s2>>op>>t;
            E a={s1,s2,t,j};
            if(s2.size()==18&&check(s2)){
                ve.push_back(a);
                if(op==1&&!st[s1]){
                    ans2.push_back({s1,s2});
                    st[s1]=1;
                }
            }
        }
        sort(ve.begin(),ve.end());
        for(int j=0;j<ve.size();++j){
            if(i>pre[ve[j].na]&&S){
                ans1.push_back({ve[j].na,ve[j].id});
                pre[ve[j].na]=i+P;S--;
            }
        }
    }
    for(auto t:ans1){
        cout<<t.na<<' '<<t.id<<'\n';
    }
    for(auto t:ans2){
        cout<<t.na<<' '<<t.id<<'\n';
    }
    return 0;
}
View Code

 

完全二叉树的层序遍历

思路：dfs根据后序遍历的顺序对应出层序的顺序

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>PLI;
const int N=1e5+5,M=1e6+5,Mod=1e6;
const int INF=0x3f3f3f3f3f3f3f3f;

const double eps=1e-8;

int n;
vector<int>post,a,b;
void dfs(int u){
    if(u*2<=n)dfs(u*2);
    if(u*2+1<=n)dfs(u*2+1);
    a.push_back(u);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    post=vector<int>(n);
    b=vector<int>(n+1);
    for(int i=0;i<n;++i)cin>>post[i];
    dfs(1);
    for(int i=0;i<n;++i){
        b[a[i]]=post[i];
    }
    for(int i=1;i<=n;++i){
        cout<<b[i];
        if(i!=n)cout<<" ";
    }
    return 0;
}
View Code

 

那就别担心了

思路：dfs求所有点到终点的路径条数，若有节点已遍历但无路径数则NO

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,int>PLI;
const int N=5e2+5,M=1e6+5,Mod=1e6;
const int INF=0x3f3f3f3f;

const double eps=1e-8;

int n,m,path[N];
vector<int>ve[N];
bool vis[N];
int dfs(int x){
    vis[x]=true;
    if(path[x])return path[x];
    for(auto v:ve[x]){
        path[x]+=dfs(v);
    }
    return path[x];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0,a,b;i<m;++i){
        cin>>a>>b;
        ve[a].push_back(b);
    }
    int x,y;
    cin>>x>>y;
    path[y]=1;
    int cnt=dfs(x);
    bool ok=true;
    for(int i=1;i<=n;++i){
        if(vis[i]&&!path[i]){
            ok=false;break;
        }
    }
    cout<<cnt<<' ';
    if(ok)cout<<"Yes";
    else cout<<"No";
    return 0;
}
View Code