526互联

Codeforces Round 888 (Div. 3)

发布时间 2023-07-26 10:35:15作者: bible_w

Codeforces Round 888 (Div. 3)

A - Escalator Conversations

思路：求出每个人与Vlad的身高差d，若的能被k整除，且d/k<m则YES

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;

void solve(){
    int n,m,k,H;
    cin>>n>>m>>k>>H;
    int ans=0;
    for(int i=0,x;i<n;++i){
        cin>>x;
        x=abs(x-H);
        if(x%k==0&&x/k<m&&x!=0){
            ans++;//cout<<i<<' ';
        }
    }//cout<<'\n';
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

B - Parity Sort

思路：将数组排序后与原数组比较，判断每个位置的奇偶是否一样

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};


void solve(){
    int n;cin>>n;
    vector<int>ve(n),b;
    for(int i=0;i<n;++i)cin>>ve[i];
    b=ve;
    sort(b.begin(),b.end());
    bool ok=true;
    for(int i=0;i<n;++i){
        if(ve[i]%2!=b[i]%2){
            ok=false;break;
        }
    }
    if(ok)cout<<"YES\n";
    else cout<<"NO\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

C - Tiles Comeback

题意：问是否存在某种路径，该路径包含第一个和最后一个颜色，且路径上有任意段，每段数量为k，且每段上的颜色相同

思路：找出包含第一个颜色，且长度为k的段的右边界；找出包含最后一个颜色，且长度为k的段的左边界；若右边界<=左边界则YES；

特判所有颜色相同的情况，一定YES

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
vector<int>ve(N);
void solve(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>ve[i];
    if(k==1){
        cout<<"YES\n";return;
    }
    int l=1,r=n,c=0;
    while(c!=k){
        if(l==n+1){
            l=n+2;
            break;
        }
        if(ve[l++]==ve[1])c++;
    }
    l--;
    c=0;
    while(c!=k){
        if(r==0){
            r=-1;
            break;
        }
        if(ve[r--]==ve[n])c++;
    }
    r++;
    //cout<<l<<' '<<r<<'\n';
    if(l<=r||(l<=n&&r>=1&&ve[1]==ve[n]))cout<<"YES\n";
    else cout<<"NO\n";
    return ;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

D - Prefix Permutation Sums

思路：由于数组b是1~n的不重复序列，若缺少的不是an，那么前缀和a[n-1]一定等于Sn（ Sn=n*（n+1）/2 ），否则就在a末尾添加一个Sn，可直接转变回原前缀和序列；

若前缀和a[n-1]等于Sn：

由前缀和的差可以求出每个b[i]，但由于缺少了一个前缀ai，可能存在s=bi，bi为两种情况的一种：1.bi>n　　2.bi出现两次　

有且只能存在一个情况，若存在多个则NO；

对于1或2情况，求出差分b在1~n中缺少的数的和，判断是否等于s，等于则YES

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7;
const double eps=1e-6;
vector<int>ve(N);
void solve(){
    int n;cin>>n;
    for(int i=1;i<n;++i)cin>>ve[i];
    int s=n*(n+1)/2;
    if(ve[n-1]>s){
        cout<<"NO\n";return ;
    }
    int m=n-1;
    if(ve[n-1]!=s)ve[n]=s,m++;
    set<int>se;
    int e1=-1;
    for(int i=1;i<=m;++i){
        int a=ve[i]-ve[i-1];
        if(a<=n){
            if(se.count(a)==0)se.insert(a);
            else if(e1==-1){
                e1=a;
            }else{
                cout<<"NO\n";return ;
            }
        }else if(e1==-1){
            e1=a;
        }else{
            cout<<"NO\n";return ;
        }
    }
    if(e1!=-1){
        int ss=0;
        for(int i=1;i<=n;++i){
            if(se.count(i)==0)ss+=i;
        }
        if(ss==e1)cout<<"YES\n";
        else cout<<"NO\n";
    }else cout<<"YES\n";
    return ;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int t=1;
    //init();
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
View Code

 

E - Nastya and Potions

题意：每种药的获取途径有：买、其他药制作，需要使获取每种药的花费最小

思路：dfs搜索获取该药的途径

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
typedef pair<int,int>PII;

typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const int inf=0x3f3f3f3f3f3f;
const double eps=1e-6;
const int dx[4]={-1,0,1,0};
const int dy[4]={0,1,0,-1};

set<int>se;
vector<int>ve(N),f[N],ans(N),mi(N);
int dfs(int u){
    if(se.count(u))return 0;
    if(f[u].size()==0)return ve[u];
    if(mi[u]!=-u)return mi[u];
    int s=0;
    for(auto v:f[u]){
        s+=dfs(v);
    }
    if(s==0)se.insert(u);
    mi[u]=min(s,ve[u]);
    return mi[u];
}
void solve(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;++i)cin>>ve[i],mi[i]=-i;
    se.clear();
    for(int i=1,x;i<=k;++i){
        cin>>x;
        se.insert(x);
    }
    for(int i=1,m;i<=n;++i){
        cin>>m;
        f[i].clear();
        for(int j=1,x;j<=m;++j){
            cin>>x;f[i].push_back(x);
        }
    }
    for(int i=1;i<=n;++i){
        ans[i]=dfs(i);cout<<ans[i]<<' ';
    }cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //init();
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

F - Lisa and the Martians