526互联

西南民族大学 春季 2023 训练赛 6-补题

发布时间 2023-04-13 10:03:17作者: bible_w

西南民族大学 春季 2023 训练赛 6-补题

 今天我要赢

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

string s="2022-04-23";
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cout<<"I'm gonna win! Today!\n";
    cout<<s;
    return 0;
}
View Code

 

种钻石

#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 a,b;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    cout<<a/b;
    return 0;
}
View Code

 

谁能进图书馆

思路：判断每种情况

#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 a,b,x,y;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b>>x>>y;
    if(x<a&&y<a){
        cout<<x<<"-N "<<y<<"-N\n";
        cout<<"zhang da zai lai ba";
        return 0;
    }
    if(x>=a&&y>=a){
        cout<<x<<"-Y "<<y<<"-Y\n";
        cout<<"huan ying ru guan";
        return 0;
    }
    if((x<a&&y>=b)||(y<a&&x>=b)){
        int aa,bb;
        if(x<a)aa=1,bb=2;
        else aa=2,bb=1;
        cout<<x<<"-Y "<<y<<"-Y\n";
        cout<<"qing "<<bb<<" zhao gu hao "<<aa;
        return 0;
    }
    int aa;
    if(x>a){aa=1;cout<<x<<"-Y "<<y<<"-N\n";
    }
    else {
        aa=2;cout<<x<<"-N "<<y<<"-Y\n";
    }
    cout<<aa<<": huan ying ru guan";

    return 0;
}
View Code

 

拯救外星人

#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 a,b;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    int res=1;
    for(int i=2;i<=a+b;++i)res*=i;
    cout<<res;
    return 0;
}
View Code

 

试试手气

#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 a[6];
int k;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(int i=0;i<6;++i)cin>>a[i];
    cin>>k;
    k=6-k+1;
    for(int i=0;i<6;++i){
        if(a[i]>=k)cout<<k-1;
        else cout<<k;
        if(i!=5)cout<<' ';
    }
    return 0;
}
View Code

 

斯德哥尔摩火车上的题

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

string a,b,x,y;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    x=y="";
    cin>>a>>b;
    for(int i=1;i<a.size();++i){
        if(a[i]%2==a[i-1]%2)x+=max(a[i],a[i-1]);
    }
    for(int i=1;i<b.size();++i){
        if(b[i]%2==b[i-1]%2)y+=max(b[i],b[i-1]);
    }
    if(x==y)cout<<x;
    else cout<<x<<'\n'<<y;
    return 0;
}
View Code

 

 机工士姆斯塔迪奥

思路：二维差分和

#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,q;
void add(vector<vector<int>>&ve,int x1,int y1,int x2,int y2,int c){
    ve[x1][y1]+=c,ve[x2+1][y1]-=c,ve[x1][y2+1]-=c,ve[x2+1][y2+1]+=c;
}

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>q;
    vector<vector<int>>ve(n+5,vector<int>(m+5,0));
    int op,x;
    while(q--){
        cin>>op>>x;
        if(op==0){
            add(ve,x,1,x,m,1);
        }
        else{
            add(ve,1,x,n,x,1);
        }
    }
    int res=0;
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            ve[i][j]+=(ve[i-1][j]+ve[i][j-1]-ve[i-1][j-1]);
            if(ve[i][j]==0)res++;
        }
    cout<<res;
    return 0;
}
View Code

 

静静的推荐

思路：过175分且pat成绩到达分数线的一定可以选入，将剩余的过175分的人数记录，统计人数，若某个分段的人数大于k，加k即可

#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,k,s,res;
int aa[300];

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>k>>s;
    int a,b;
    for(int i=0;i<n;++i){
        cin>>a>>b;
        if(a>=175){
            if(b>=s)res++;
            else aa[a]++;
        }
    }
    for(int i=175;i<=290;++i){
        if(aa[i]<=k)res+=aa[i];
        else res+=k;
    }
    cout<<res;

    return 0;
}
View Code

 

插松枝

思路：stack模拟

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

stack<int>stk;
int n,m,k,a[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m>>k;
    for(int i=0;i<n;++i)cin>>a[i];
    int j=0,i=0,x;
    vector<int>ans;
    while(1){
        x=100;
        while(!stk.empty()){
            if(j>=k)break;
            if(stk.top()<=x){
                ans.push_back(stk.top());x=stk.top();
                stk.pop();j++;
            }else break;
        }
        if(j<k){
            while(j<k&&i<n){
                int u=a[i++];
                if(u<=x){
                    ans.push_back(u);x=u;j++;
                }
                else if(stk.size()<m)stk.push(u);
                else{
                    i--;break;
                }
            }
        }
        for(int u=0;u<ans.size();++u){
            cout<<ans[u];
            if(u!=ans.size()-1)cout<<' ';
        }
        if(i<n||!stk.empty())cout<<'\n';
        else break;
        j=0;ans.clear();
    }
    return 0;
}
View Code

 

老板的作息表

思路：直接转化为秒排，或者直接排也行

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

const double eps=1e-8;
typedef long long ll;
int n;
struct E{
    int a,b,c;
};
vector<pair<E,E>>ve;
bool cmp(pair<E,E>a,pair<E,E>b){
    E x=a.first,y=b.first;
    if(x.a==y.a){
        if(x.b==y.b)return x.c<y.c;
        return x.b<y.b;
    }
    return x.a<y.a;
}
bool cmpp(E a,E b){
    if(a.a==b.a){
        if(a.b==b.b)return a.c>b.c;
        return a.b>b.b;
    }
    return a.a>b.a;
}
void ppp(int x){
    if(x==0)cout<<"00";
    else if(x<10)cout<<"0"<<x;
    else cout<<x;
}
void pp(E a,E b){
    ppp(a.a);cout<<":";
    ppp(a.b);cout<<":";
    ppp(a.c);cout<<" - ";
    ppp(b.a);cout<<":";
    ppp(b.b);cout<<":";
    ppp(b.c);
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    char d;
    for(int i=0;i<n;++i){
        int a,b,c,aa,bb,cc;
        cin>>a>>d>>b>>d>>c>>d>>aa>>d>>bb>>d>>cc;
        ve.push_back({{a,b,c},{aa,bb,cc}});
    }
    sort(ve.begin(),ve.end(),cmp);

    E h={0,0,0},rr={23,59,59};
    vector<pair<E,E>>ans;
    for(int i=0;i<n;++i){
        E x=ve[i].first,y=ve[i].second;
        if(cmpp(x,h))ans.push_back({h,x});
        h=y;
    }
    if(h.a!=rr.a||h.b!=rr.b||h.c!=rr.c)ans.push_back({h,rr});
    for(int i=0;i<ans.size();++i){
        pp(ans[i].first,ans[i].second);
        if(i!=ans.size()-1)cout<<"\n";
    }
    return 0;
}
View Code

 

龙龙送外卖

思路：并查集维护当前需要经过的个数和每个点到根节点（外卖站）的距离，由于最后一次不用返回起点，最短路程为：(fa[sta]+1)*(-2)-maxdis

#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;
int n,m,g[N],sta=-1,fa[N],dis[N],ma;
int find(int x){
    if(fa[x]<0)return x;
    return fa[x]=find(fa[x]);
}
void dfs(int x){
    if(find(x)==sta)return ;
    dfs(g[x]);
    dis[x]=dis[g[x]]+1;ma=max(ma,dis[x]);
    fa[sta]+=fa[x],fa[x]=sta;
    return ;
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i){
        cin>>g[i];
        if(g[i]==-1)sta=i;
    }
    int x;
    memset(fa,-1,sizeof fa);
    while(m--){
        cin>>x;
        if(find(x)!=sta)dfs(x);
        cout<<-2*(fa[sta]+1)-ma<<'\n';
    }
    return 0;
}
View Code

 

大众情人

思路：floyed求最短距离，分别统计男女生的“大众情人”

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

const double eps=1e-8;
typedef long long ll;
int n,d[N][N];
char sex[N];
vector<int>f,m;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    memset(d,0x3f,sizeof d);
    for(int i=1;i<=n;++i){
        cin>>sex[i];
        if(sex[i]=='F')f.push_back(i);
        else m.push_back(i);
        int k,x,w;
        char c;
        cin>>k;
        while(k--){
            cin>>x>>c>>w;
            d[i][x]=min(d[i][x],w);
        }
    }
    for(int k=1;k<=n;++k){
        for(int i=1;i<=n;++i){
            if(i==k||d[i][k]==INF)continue;
            for(int j=1;j<=n;++j)
            {
                if(i==j||k==j||d[k][j]==INF)continue;
                d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
            }
        }
    }
    vector<int>F,M;
    for(int i=1;i<=n;++i){
        int v=-1;
        if(sex[i]=='F'){
            for(auto j:m){
                v=max(v,d[j][i]);
            }
            if(F.empty())F.resize(2),F[0]=v,F[1]=i;
            else if(F[0]==v)F.push_back(i);
            else if(F[0]>v)F.resize(2),F[0]=v,F[1]=i;
        }
        else{
            for(auto j:f){
                v=max(v,d[j][i]);
            }
            if(M.empty())M.resize(2),M[0]=v,M[1]=i;
            else if(M[0]==v)M.push_back(i);
            else if(M[0]>v)M.resize(2),M[0]=v,M[1]=i;
        }
    }
    for(int i=1;i<F.size();++i){
        cout<<F[i];
        if(i!=F.size()-1)cout<<' ';
    }cout<<'\n';
    for(int i=1;i<M.size();++i){
        cout<<M[i];
        if(i!=M.size()-1)cout<<' ';
    }
    return 0;
}
View Code