首页 > 其他分享 >Educational Codeforces Round 76 (Rated for Div. 2)

Educational Codeforces Round 76 (Rated for Div. 2)

时间：2023-07-28 19:22:43浏览次数：42  
标签：GCC Rated const int Educational Codeforces pragma optimize functions

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

 

标签：GCC,Rated,const,int,Educational,Codeforces,pragma,optimize,functions
From： https://www.cnblogs.com/bible-/p/17588727.html

相关文章

  • Educational Codeforces Round 152 A~D
    A#include<bits/stdc++.h>#defineendl'\n'#defineiosios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr)usingnamespacestd;typedefpair<int,int>PII;constintN=2e5+10;constintMOD=1e9+7;intT;vo......
  • Codeforces Round 888 (Div. 3) 题解
    考场上\(7\)题做出来\(4\)题，最后几分钟才把D题调出来，但还是吃了不少罚时A.EscalatorConversations\(O(n)\)枚举即可，对于每个人计算需要的间隔台阶数是否在\((0,m)\)以内以及相差高度是否是\(k\)的倍数B.ParitySort显然，偶数和奇数是不可能产生交换操作的，而偶数......
  • Educational Codeforces Round 1
    EducationalCodeforcesRound1A.TrickySumintfac[N],p2[N];voidinit(){fac[0]=1;p2[0]=1;for(inti=1;i<=33;i++){fac[i]=fac[i-1]*2;p2[i]=p2[i-1]+fac[i];}}voidsolve(){intn=read();intsum=(1+n)*n/2;co......
  • CodeForces 1268E Happy Cactus
    洛谷传送门AtCoder传送门考虑一些简单的情况，比如树。设\(f_u\)为当前\(u\)能通过边权递增的路径到达的点数（包括它自己）。为了让两个点对在边权递增路径的边权最小的那条边被统计，我们倒序枚举边。当枚举到\((u,v)\)时，我们有\(f_u=f_v=f_u+f_v\)。这是因为\(u\)......
  • Codeforces Round 888 (Div. 3)记录
    A.EscalatorConversations#include<cstdio>#include<algorithm>#include<cmath>#include<vector>#include<string.h>#include<set>#include<string>#include<map>#include<iostream>#include<queue>......
  • @GeneratedValue 和 @GenericGenerator注解----自定义主键生成策略
    @GeneratedValue注解存在的意义主要就是为一个实体生成一个唯一标识的主键 https://blog.csdn.net/sswqzx/article/details/84337921https://blog.csdn.net/u011781521/article/details/72210980......
  • Codeforces Round 618 (Div. 2)
    CodeforcesRound618(Div.2)https://codeforces.com/contest/1300A.Non-zero要求和，积都不为0，则先把全部0操作一次，然后再check和是否为0，是的话再对任意数操作一次即可。#include<bits/stdc++.h>usingnamespacestd;constintN=105;intn,x,s,ans;voidsolve......
  • Codeforces Round 888 (Div. 3) A-F
    A.EscalatorConversations题意：有一个扶梯，有n个人要站扶梯，这个扶梯有m个位置，第i个位置的高度为i*k，Vlad高H，第i个人高h[i]，当且仅当两个人所处的位置高度加上自身身高刚好相同时才能谈话，问能和Vlad谈话的有多少人。Solution直接计算即可voidsolve(){ intn,m,k,H;cin>>n>>m>>......
  • Codeforces Round 888 (Div. 3) - D
    目录D.PrefixPermutationSumsCodeforcesRound888(Div.3)赛后摘记D.PrefixPermutationSums题意判断给定的长为n-1数组，是否为某个1~n的序列的前缀和数组漏了一个数形成的数组思路就是判断能否变回去，毫无感情的判断机器法一：统计给定前缀和数组的差分数组得......
  • Codeforces Round 888 (Div. 3)
    A.EscalatorConversations#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongvoidsolve(){intn,m,k,H;cin>>n>>m>>k>>H;vector<int>h(n);intres=0;for(inth,......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99