西南民族大学春季 2023 训练赛 5-526互联

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

自动编程

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

const double eps=1e-8;
typedef long long ll;
int n;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    cout<<"print("<<n<<")";
    return 0;
}

View Code

太神奇了

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e4+5,M=1e3+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;
    cout<<m+n-1;
    return 0;
}

View Code

洛希极限

思路：列公式

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

const double eps=1e-8;
typedef long long ll;
double a,c;
int b;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b>>c;
    double l=a;
    if(b==0)l*=2.455;
    else l*=1.26;
    cout<<fixed<<setprecision(2)<<l;
    if(c<l)cout<<" T_T";
    else cout<<" ^_^";
    return 0;
}

View Code

吃鱼还是吃肉

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

const double eps=1e-8;
typedef long long ll;
int n,op,h,w;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    while(n--){
        cin>>op>>h>>w;
        if(op==1){
            if(h>130)cout<<"ni li hai!";
            else if(h==130)cout<<"wan mei!";
            else cout<<"duo chi yu!";
            cout<<' ';
            if(w>27)cout<<"shao chi rou!";
            else if(w==27)cout<<"wan mei!";
            else cout<<"duo chi rou!";
            cout<<'\n';
        }
        else{
            if(h>129)cout<<"ni li hai!";
            else if(h==129)cout<<"wan mei!";
            else cout<<"duo chi yu!";
            cout<<' ';
            if(w>25)cout<<"shao chi rou!";
            else if(w==25)cout<<"wan mei!";
            else cout<<"duo chi rou!";
            cout<<'\n';
        }
    }
    return 0;
}

View Code

不变初心数

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=1e4+5,M=1e3+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;
    while(n--){
        cin>>m;
        int s=m,x=0;
        bool ok=true;
        while(s){
            x+=s%10;
            s/=10;
        }
        int y;
        for(int i=2;i<=9;++i){
            s=m*i;
            y=0;
            while(s){
                y+=s%10;
                s/=10;
            }
            if(y!=x){
                ok=false;
                break;
            }
        }
        if(ok)cout<<x<<'\n';
        else cout<<"NO\n";
    }
    return 0;
}

View Code

字母串

思路：注意大小写和边界

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

const double eps=1e-8;
typedef long long ll;
int n;
string s;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    while(n--){
        cin>>s;
        bool ok=true;
        for(int i=0;i<s.size()-1;++i){
            if(abs(s[i]-s[i+1])==32||(s[i]<=90&&s[i+1]-s[i]==1&&s[i+1]<=90)||(s[i]>90&&s[i]-s[i+1]==1&&s[i+1]>=97))
                continue;
            ok=false;
        }
        if(ok)cout<<"Y\n";
        else cout<<"N\n";
    }
    return 0;
}

View Code

矩阵列平移

思路：从第一行前插入数

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

const double eps=1e-8;
typedef long long ll;
int n,k,x;
vector<int>ve[105];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k>>x;
    int y;

    for(int i=1;i<=n;++i){
        for(int j=1;j<=n;++j){
            cin>>y;
            ve[j].push_back(y);
        }
    }
    int idx=1;
    for(int i=2;i<=n;i+=2){
        for(int j=1;j<=idx;++j){
            ve[i].insert(ve[i].begin(),x);
        }
        idx++;
        if(idx>k)idx=1;
    }
    for(int i=0;i<n;++i){
        int s=0;
        for(int j=1;j<=n;++j){
            s+=ve[j][i];
        }
        cout<<s;
        if(i!=n-1)cout<<' ';
    }
    return 0;
}

View Code

均是素数

思路：线性筛出1e6+1e3内的素数

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

const double eps=1e-8;
typedef long long ll;
bool st[N];
int m,n,primes[N],use[1005],uidx,idx,jie;
void P(){
    st[1]=true;
    for(int i=2;i<=jie;++i){
        if(!st[i]){
            primes[idx++]=i;
            if(i>=m&&i<=n)use[uidx++]=i;
        }
        for(int j=0;primes[j]*i<=jie;++j){
            st[primes[j]*i]=true;
            if(i%primes[j]==0)break;
        }
    }
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>m>>n;
    ll res=0;
    jie=n*n+n+5;
    P();
    for(int i=0;i<uidx;++i){
        for(int j=i+1;j<uidx;++j){
            for(int k=j+1;k<uidx;++k){
                int p=use[i],q=use[j],r=use[k];
                if(!st[p*q+r]&&!st[q*r+p]&&!st[r*p+q])res++;
            }
        }
    }
    cout<<res;
    return 0;
}

View Code

盲盒包装流水线

思路：坐标对号

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

const double eps=1e-8;
typedef long long ll;
int a[N],n,s,b[N];
bool st[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>s;
    int x;
    for(int i=1;i<=n;++i){
        cin>>x;
        st[x]=true;
        a[x]=i;
    }
    int t=0;
    for(int i=1;i<=n/s;++i){
        for(int j=1;j<=s;++j){
            cin>>x;
            b[t*s+s-j+1]=x;
        }
        t++;
    }
    int k;
    cin>>k;
    while(k--){
        cin>>x;
        if(!st[x])cout<<"Wrong Number\n";
        else{
            cout<<b[a[x]]<<'\n';
        }
    }
    return 0;
}

View Code

点赞狂魔

思路：求每个人的标签种类及平均值，比较一下

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

const double eps=1e-8;
typedef long long ll;
int n,k;
struct E{
    string na;
    int sum;
    double aver;
}g[105];
unordered_map<int,int>mp;
bool cmp(E a,E b){
    if(a.sum!=b.sum)return a.sum>b.sum;
    return a.aver<b.aver;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;++i){
        cin>>g[i].na;
        cin>>k;
        mp.clear();
        int x,ma=0;
        for(int j=0;j<k;++j){
            cin>>x;
            mp[x]++;
            ma=max(ma,mp[x]);
        }
        g[i].sum=mp.size();
        g[i].aver=k*1.0/mp.size();
    }
    sort(g,g+n,cmp);
    for(int i=0;i<3&&i<n;++i){
        cout<<g[i].na;
        if(i<2&&i<n-1)cout<<' ';
    }
    if(n<3){
        for(int i=1;i<=3-n;++i)
        cout<<" -";
    }
    return 0;
}

View Code

浪漫侧影

思路：后中序求出树，从根节点遍历树，L先遍历左子树再右子树，R先遍历右子树再左子树

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

const double eps=1e-8;
typedef long long ll;
int n,post[25],in[25];
typedef struct TreeNode{
    int date;
    TreeNode *left,*right;
}*Tree;
Tree postandin(int pl,int pr,int il,int ir){
    Tree root = new struct TreeNode;
    root->date = post[pr];
    root->left=root->right=NULL;
    int p = il;
    while (in[p] != post[pr])p++;
    int num = p - il;
    if (p != il)root->left = postandin(pl, pl + num - 1, il, p - 1);
    if (p != ir)root->right = postandin(pl + num, pr - 1, p + 1, ir);
    return root;
}
int L[25],R[25],idx;
void LL(Tree root,int p){
    if(p==idx)L[idx++]=root->date;
    if(root->left)LL(root->left,p+1);
    if(root->right)LL(root->right,p+1);
}
void RR(Tree root,int p){
    if(p==idx)R[idx++]=root->date;
    if(root->right)RR(root->right,p+1);
    if(root->left)RR(root->left,p+1);
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<n;++i)cin>>in[i];
    for(int i=0;i<n;++i)cin>>post[i];
    Tree tree=postandin(0,n-1,0,n-1);
    RR(tree,0);
    cout<<"R: ";
    for(int i=0;i<idx;++i){
        cout<<R[i];
        if(i!=idx-1)cout<<' ';
    }
    idx=0;
    LL(tree,0);cout<<"\n";
    cout<<"L: ";
    for(int i=0;i<idx;++i){
        cout<<L[i];
        if(i!=idx-1)cout<<' ';
    }
    return 0;
}

View Code

哲哲打游戏

思路：模拟下三种情况

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

const double eps=1e-8;
typedef long long ll;
vector<int>ve[N];
int a[105],n,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=0;i<n;++i){
        int k,x;
        cin>>k;
        ve[i+1].push_back(i+1);
        while(k--){
            cin>>x;
            ve[i+1].push_back(x);
        }
    }
    int op,p,st=1;
    vector<int>ans;
    for(int i=0;i<m;++i){
        cin>>op>>p;
        if(op==0){
            st=ve[st][p];
        }
        else if(op==1){
            a[p]=st;
            ans.push_back(st);
        }
        else{
            st=a[p];
        }
    }
    for(auto x:ans)cout<<x<<'\n';
    cout<<st;
    return 0;
}

View Code

直捣黄龙

思路：1.dijkstra，求最短路过程中维护其他属性 2.dijkstra+dfs，求出最短路径，dfs求最佳的路径

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

const double eps=1e-8;
typedef long long ll;
string st,en;
bool vis[N];
int n,k,w[N],path[N],num[N],cnt[N],ki[N],dis[N];
unordered_map<string,int>si;
unordered_map<int,string>is;
vector<PII>ve[N];
void dij(){
    memset(dis,0x3f,sizeof dis);
    priority_queue<PII,vector<PII>,greater<PII> >q;
    dis[0]=0, path[0]=-1, num[0]=1, cnt[0]=1, ki[0]=0;
    q.push({dis[0],0});
    while(q.size()){
        auto t=q.top();q.pop();
        int u=t.second;
        if(vis[u])continue;
        vis[u]=true;
        for(auto x:ve[u]){
            int v=x.first,ww=x.second;
            if(vis[v])continue;
            if(dis[v]>dis[u]+ww){
                dis[v]=dis[u]+ww;
                path[v]=u;
                num[v]=num[u];
                cnt[v]=cnt[u]+1;
                ki[v]= ki[u] + w[v];
                q.push({dis[v],v});
            }
            else if(dis[v]==dis[u]+ww){
                num[v]+=num[u];
                if(cnt[v]<cnt[u]+1){
                    cnt[v]=cnt[u]+1;
                    path[v]=u;
                    ki[v]= ki[u] + w[v];
                }
                else if(cnt[v]==cnt[u]+1){
                    if(ki[v] < ki[u] + w[v]){
                        ki[v]= ki[u] + w[v];
                        path[v]=u;
                    }
                }
            }
        }
    }
    stack<int>sk;
    int t=si[en];
    while(t!=-1){
        sk.push(t);
        t=path[t];
    }
    while(sk.size()){
        cout<<is[sk.top()];
        sk.pop();
        if(sk.size())cout<<"->";
    }
    cout<<"\n";
    t=si[en];
    cout << num[t] << ' ' << dis[t] << ' ' << ki[t];
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>n>>k>>st>>en;
    si[st]=0;
    is[0]=st;
    string s,ss;
    int x;
    for(int i=1;i<n;++i){
        cin>>s>>w[i];
        si[s]=i;
        is[i]=s;
    }
    for(int i=0;i<k;++i){
        cin>>s>>ss>>x;
        int a=si[s],b=si[ss];
        ve[a].push_back({b,x});
        ve[b].push_back({a,x});
    }
    dij();
    return 0;
}

View Code 1

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

const double eps=1e-8;
typedef long long ll;
string st,en;
bool vis[N];
int n,k,w[N],dis[N],sum,ren;
unordered_map<string,int>si;
unordered_map<int,string>is;
vector<PII>ve[N];
vector<string>path;
void dfs(int x,int d,int rens,vector<string>tp){
    if(is[x]==en&&d==dis[si[en]]){
        sum++;
        if(path.size()<tp.size()){
            path=tp;
            ren=rens;
        }
        else if(path.size()==tp.size()){
            if(ren<rens){
                ren=rens;
                path=tp;
            }
        }
        return ;
    }
    for(auto u:ve[x]){
        if(!vis[u.first]&&d+u.second<=dis[si[en]]){
            tp.push_back(is[u.first]);
            vis[u.first]=true;
            dfs(u.first,d+u.second,rens+w[u.first],tp);
            vis[u.first]=false;
            tp.pop_back();
        }
    }
}
void dij(){
    memset(dis,0x3f,sizeof dis);
    priority_queue<PII,vector<PII>,greater<PII> >q;
    dis[0]=0;
    q.push({dis[0],0});
    while(q.size()){
        auto t=q.top();q.pop();
        int u=t.second;
        if(vis[u])continue;
        vis[u]=true;
        for(auto x:ve[u]){
            if(!vis[x.first]){
                if(dis[x.first]>dis[u]+x.second){
                    dis[x.first]=dis[u]+x.second;
                    q.push({dis[x.first],x.first});
                }
            }
        }
    }

}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

    cin>>n>>k>>st>>en;
    si[st]=0;
    is[0]=st;
    string s,ss;
    int x;
    for(int i=1;i<n;++i){
        cin>>s>>w[i];
        si[s]=i;
        is[i]=s;
    }
    for(int i=0;i<k;++i){
        cin>>s>>ss>>x;
        int a=si[s],b=si[ss];
        ve[a].push_back({b,x});
        ve[b].push_back({a,x});
    }
    dij();
    path.push_back(st);
    memset(vis,false,sizeof vis);
    dfs(0,0,0,path);
    for(int i=0;i<path.size();++i){
        cout<<path[i];
        if(i!=path.size()-1)cout<<"->";
        else cout<<"\n";
    }
    cout<<sum<<' '<<dis[si[en]]<<' '<<ren;
    return 0;
}

View Code 2

拼题A打卡奖励

思路：dp求金币数需要的最少时间

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

const double eps=1e-8;
typedef long long ll;
int n,m,f[M],w[N],v[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int s=0;
    for(int i=1;i<=n;++i)cin>>v[i];
    for(int i=1;i<=n;++i){
        cin>>w[i];
        s+=w[i];
    }
    memset(f,0x3f,sizeof f);
    f[0]=0;
    for(int i=1;i<=n;++i)
        for(int j=s;j>=w[i];--j){
            f[j]=min(f[j],f[j-w[i]]+v[i]);
        }
    for(int i=s;i>=0;--i)
        if(f[i]<=m){
            cout<<i;
            break;
        }
    return 0;
}

View Code

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

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