526互联

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

发布时间 2023-04-03 20:37:00作者: bible_w

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

L1-1小乐乐是否被叫家长

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

const double eps=1e-8;
typedef long long ll;
int a,b,c;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b>>c;
    double s=1.0*(a+b+c)/3;
    if(s>=60)cout<<"NO";
    else cout<<"YES";
    return 0;
}
View Code

 

 

 L1-2你要乘坐的飞碟在这里
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
string a,b;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b;
    ll x=1,y=1;
    for(int i=0;i<a.size();++i){
        ll s=a[i]-'A'+1;
        x=x*s;
    }
    for(int i=0;i<b.size();++i){
        ll s=b[i]-'A'+1;
        y=y*s;
    }
    if(x%47==y%47)cout<<"GO";
    else cout<<"STAY";
    return 0;
}
`_`

 

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

const double eps=1e-8;
typedef long long ll;
int a,b,c;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>a>>b>>c;
    int s=a*0.2+b*0.3+c*0.5;
    cout<<s;
    return 0;
}
( ´▽｀)

 

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

const double eps=1e-8;
typedef long long ll;
int prime[N],idx,a[N];
bool st[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    for(int i=2;i<=1e3;++i){
        if(!st[i])prime[idx++]=i;
        for(int j=0;prime[j]*i<=1e3;++j){
            st[prime[j]*i]=true;
            if(i%prime[j]==0)break;
        }
    }
    st[1]=true;
    for(int i=1;i<=1e3;++i){
        a[i]+=a[i-1];
        if(!st[i])a[i]++;
    }
    int t,n;
    cin>>t;
    while(t--){
        cin>>n;
        cout<<a[n]<<'\n';
    }
    return 0;
}
View Code

 

 L1-5便便传送门(一)
思路：两种可能，x到y，x到a到b到y
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+5,M=1e3+5,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(a>b)swap(a,b);
    if(x>y)swap(x,y);
    int ans=b-a;
    ans=min(ans,abs(a-x)+abs(y-b));
    cout<<ans;
    return 0;
}
View Code

 

L1-6有序序列插入一个数
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=2e5+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int n,a[60];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=0;i<=n;++i)cin>>a[i];
    sort(a,a+n+1);
    for(int i=0;i<=n;++i)cout<<a[i]<<' ';
    return 0;
}
View Code

 


L1-7货物收集
思路：将怪物武力值从小到大维护，bfs求收集总和，维护当前所需的最大时间，当收集总和大于等于W时结束
#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,w[N],W;
vector<PII>g[N];
bool st[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>W;
    for(int i=2;i<=n;++i)cin>>w[i];
    int u,v,ww;
    for(int i=1;i<n;++i){
        cin>>u>>v>>ww;
        g[u].push_back({ww,v});
        g[v].push_back({ww,u});
    }
    int ans=0,sum=0;
    priority_queue<PII,vector<PII>,greater<PII> >q;
    q.push({0,1});
    while(q.size()){
        auto t=q.top();q.pop();
        ans=max(ans,t.first);
        sum+=w[t.second];
        if(sum>=W)break;
        st[t.second]=true;
        for(auto x:g[t.second]){
            if(!st[x.second]){
                q.push({x.first,x.second});
            }
        }
    }
    cout<<ans;
    return 0;
}
View Code

 


L1-8道路铺设
思路：将凹陷值看作一条曲线，每个山峰都需要额外的操作来填补，填补方法：当曲线递增时，操作数为（a[i]-a[i-1]）
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define endl '\n'
const int N=1e5+10;
int a[N];
int main(){
    ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);
    int n;cin>>n;
    for(int i=1;i<=n;i++)cin>>a[i];
    ll sum=0;
    sum+=a[1];
    for(int i=2;i<=n;i++){
        if(a[i]<=a[i-1])continue;
        sum+=a[i]-a[i-1];
    }
    cout<<sum;
    return 0;
}
View Code

 


L2-1货币系统
思路：dp求每种组成的币值的组成个数，大于1则说明有其他多种币能够组成它
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=25000+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int t,n,a[105];
int f[N];

int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        memset(f,false,sizeof f);
        int ma=0;
        for(int i=1;i<=n;++i){
            cin>>a[i];ma=max(ma,a[i]);
        }
        f[0]=1;
        for(int i=1;i<=n;++i){
            for(int j=0;j<=ma;++j){
                if(j>=a[i])f[j]+=f[j-a[i]];
            }
        }
        int ans=n;
        for(int i=1;i<=n;++i)if(f[a[i]]>1)ans--;
        cout<<ans<<'\n';
    }
    return 0;
}
View Code

 

L2-2***
思路：s2加到每一个位置后的差值最小
#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;
ll n,m,p1,s1,s2;
ll a[N];
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    int x;
    for(int i=1;i<=n;++i)cin>>a[i];
    cin>>m>>p1>>s1>>s2;
    a[p1]+=s1;
    ll b1=0,b2=0;
    for(int i=1;i<=n;++i){
        if(i<m)b1+=(m-i)*a[i];
        if(i>m)b2+=(i-m)*a[i];
    }
    ll d=abs(b1-b2),id=m;
    for(int i=1;i<=n;++i){
        if(i<m){
            ll s=(m-i)*s2+b1;
            if(abs(s-b2)<d){
                d=abs(s-b2);id=i;
            }
        }
        else if(i>m){
            ll s=(i-m)*s2+b2;
            if(abs(b1-s)<d){
                d=abs(b1-s);id=i;
            }
        }
    }
    cout<<id;
    return 0;
}
View Code

 


L2-3旅行
思路：将所有点连接的节点从小到大排序；1.当n=m-1时，dfs所有可能的排列，求最小。2.当n等于m时，有一个环，删除一条边即为第一种情况
#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int>PII;
const int N=5e3+5,M=1e3+5,INF=0x3f3f3f3f,Mod=1e6;

const double eps=1e-8;
typedef long long ll;
int n,m,len,de_a,de_b;
bool st[N];
int ans[N],tmp[N];
vector<int>ve[N];
PII g[N];
void dfs(int now){
    tmp[len++]=now;
    st[now]=true;
    for(auto go:ve[now]){
        if(!st[go]&&!((now==de_a&&go==de_b)||now==de_b&&go==de_a))
            dfs(go);
    }
    return ;
}
void check(){
    if(len!=n)return ;
    for(int i=0;i<n;++i){
        if(ans[i]!=tmp[i]){
            if(ans[i]<tmp[i])return;
            break;
        }
    }
    for(int i=0;i<n;++i)ans[i]=tmp[i];
}
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n>>m;
    int a,b;
    for(int i=0;i<m;++i){
        cin>>a>>b;
        ve[a].push_back(b);
        ve[b].push_back(a);
        g[i]={a,b};
    }
    memset(ans,0x3f,sizeof ans);
    for(int i=1;i<=n;++i)sort(ve[i].begin(),ve[i].end());
    if(n==m){
        for(int i=0;i<m;++i){
            len=0;
            memset(st,false,sizeof st);
            de_a=g[i].first,de_b=g[i].second;
            dfs(1);
            check();
        }
    }
    else{
        de_a=de_b=-1;
        dfs(1);
        check();
    }
    for(int i=0;i<n;++i)cout<<ans[i]<<' ';
    return 0;
}
View Code