526互联

Educational Codeforces Round 76 (Rated for Div. 2)

发布时间 2023-07-28 19:18:56作者: bible_w

Educational Codeforces Round 76 (Rated for Div. 2)

A - Two Rival Students

思路：最多可加x个距离，且最后的距离不能超过n-1

#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=50+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,x,a,b;cin>>n>>x>>a>>b;
    int ans=abs(a-b);
    ans+=x;
    ans=min(n-1,ans);
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

B - Magic Stick

思路：x>=y时可以通过操作二完成；x<y时，当x>3时，x可以通过多次操作不断增加，直到大于y；只需要特判下x=1、2、3的情况

#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=50+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 x,y;cin>>x>>y;
    if(x>=y){
        cout<<"YES\n";return ;
    }
    if(x%2)x--;
    if((x/2*3-1)>x||((x/2*3)==y))cout<<"YES\n";
    else cout<<"NO\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

C - Dominated Subarray

思路：更新每个点的位置，每次记录每个点与上一个该点的距离，取最小

/*#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")*/
#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};
vector<int>ve(N);
void solve(){
    int n;cin>>n;
    vector<int>st(n+1,0);
    for(int i=1;i<=n;++i)cin>>ve[i];

    int ans=-1;
    for(int i=1;i<=n;++i){
        if(st[ve[i]]){
            if(ans==-1)ans=i-st[ve[i]]+1;
            else ans=min(ans,i-st[ve[i]]+1);
        }
        st[ve[i]]=i;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

D - Yet Another Monster Killing Problem

思路：记录每种忍耐的最大power，依次枚举一天能杀死的最大怪兽数

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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};

vector<int>cnt(N);
vector<int>a(N);
void solve(){
    int n;cin>>n;
    for(int i=1;i<=n;++i){
        cin>>a[i];cnt[i]=0;
    }
    cnt[0]=0;
    int m;cin>>m;
    for(int i=1,p,s;i<=m;++i){
        cin>>p>>s;
        cnt[s]=max(cnt[s],p);
    }
    for(int i=n-1;i>=1;--i)cnt[i]=max(cnt[i+1],cnt[i]);
    int ans=0,now=1;
    while(now<=n){
        ans++;
        int ma=0,t=now;
        while(1){
            ma=max(ma,a[t]);
            if(cnt[t-now+1]<ma)break;
            t++;
        }
        if(now==t){cout<<"-1\n";return ;}
        now=t;
    }
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

E - The Contest

思路：

dp1：cnt[i][j]表示1~i摆放的情况，且i放在j堆的最小移动数量，（j=1、2、3）

由于三堆的序列要有序，i一定是摆在i-1的后面；再记录下1~n原来所在堆

那么cnt[i][1]=cnt[i-1][1]+1；

　　cnt[i][2]=min（cnt[i-1][1]，cnt[i-1][2]）+1；

　　cnt[i][3]=min（cnt[i-1][1]，cnt[i-1][2]，cnt[i-1][3]）+1；

减去i原来所在堆的情况；

dp2：要使三堆有序，先将一堆里数排好序，对多个数进行操作后序列一定是有序的，那么找出原序列中不变的数即可知道变的数，不变的数越多，变的数越少，即找最长上升子序列；

最长上升子序列：dp的思想，dp[i]表示以a[i]为结尾的最长上升子序列的长度，dp[i]=dp[1~（i-1）]max+1，n2的复杂度

优化下，按最长上升子序列的长度划分，记录每个长度的上升子序列最后一个数的最小值（像138，长度为1的子序列有1、3、8，找长度为2的时，8可以接在3后，也一定可以接在1后），并且随着长度增大，末尾的数也增大，因此可以二分找出可以接着的最大长度

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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};

int dp[N][4];
int st[N];
void solve(){
    int k[3],n=0;
    for(int i=0;i<3;++i)cin>>k[i],n+=k[i];
    for(int i=0;i<3;++i){
        for(int j=0,x;j<k[i];++j){
            cin>>x;
            st[x]=i+1;
        }
    }
    dp[1][1]=dp[1][2]=dp[1][3]=1;
    int t=st[1];
    dp[1][t]--;
    for(int i=2;i<=n;++i){
        int t1=dp[i-1][1],t2=dp[i-1][2],t3=dp[i-1][3];
        t=st[i];
        dp[i][1]=t1+1;
        dp[i][2]=min(t1,t2)+1;
        dp[i][3]=min(t1,min(t2,t3))+1;
        dp[i][t]--;
    }
    cout<<min(dp[n][1],min(dp[n][2],dp[n][3]));
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
dp1
#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#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 k[3],n=0;
    for(int i=0;i<3;++i)cin>>k[i],n+=k[i];
    vector<int>ve(n);
    for(int i=0;i<n;++i)cin>>ve[i];
    sort(ve.begin(),ve.begin()+k[0]);
    sort(ve.begin()+k[0],ve.begin()+k[0]+k[1]);
    sort(ve.begin()+k[0]+k[1],ve.begin()+k[0]+k[1]+k[2]);
    int len=0;
    vector<int>q(n+2,0);
    q[0]=-INF;
    for(int i=0;i<n;++i){
        int l=0,r=len,ans;
        while(l<=r){
            int mid=l+r>>1;
            if(q[mid]<ve[i])ans=mid,l=mid+1;
            else r=mid-1;
        }
        len=max(len,ans+1);
        q[ans+1]=ve[i];
    }
    cout<<n-len;
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    //cin>>T;
    while(T--){
        solve();
    }
    return 0;
}
dp2