首页 > 其他分享 >Codeforces Round 834 (Div. 3)

Codeforces Round 834 (Div. 3)

时间:2023-10-11 12:02:12浏览次数:47  
标签:typedef ve 834 int double Codeforces long Div define

Codeforces Round 834 (Div. 3)

 A - Yes-Yes?

思路:判断每种情况即可

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e6+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    string s;cin>>s;
    char p;
    for(int i=0;i<s.size();++i){
        if(i==0){
            p=s[i];
            if(s[i]!='Y'&&s[i]!='e'&&s[i]!='s'){
                cout<<"NO\n";return ;
            }
            continue;
        }
        if(p=='Y'&&s[i]!='e'){
            cout<<"NO\n";return ;
        }if(p=='e'&&s[i]!='s'){
            cout<<"NO\n";return ;
        }if(p=='s'&&s[i]!='Y'){
            cout<<"NO\n";return ;
        }
        p=s[i];
    }
    cout<<"YES\n";
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

B - Lost Permutation

思路:将排序填满,看是否用完m

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=2e6+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;

void solve() {
    int m,s;cin>>m>>s;
    vector<int>ve(1000);
    int ma=0;
    for(int i=0;i<m;++i){
        int x;cin>>x;
        ve[x]=1;ma=max(ma,x);
    }
    for(int i=1;s>0;++i){
        if(ve[i])continue;
        s-=i;
        ve[i]=1;ma=max(ma,i);
    }
    if(s==0){
        for(int i=1;i<=ma;++i)
            if(!ve[i]){
                cout<<"NO\n";return ;
            }
        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;
//    init();
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

C - Thermostat

思路:分情况讨论,1.1次:a→b 

         2.2次:a→l→b或a→r→b(a<b),a>b同理

         3.3次:a→r→l→b(a<b),a>b同理

         4.0次:a=b

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
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 double eps=1e-6;

void solve() {
    int l,r,x,a,b;
    cin>>l>>r>>x>>a>>b;
    if(a==b){
        cout<<"0\n";return ;
    }
    if(abs(a-b)>=x){
        cout<<"1\n";return ;
    }
    if(abs(l-a)<x&&abs(r-a)<x){
        cout<<"-1\n";return ;
    }
    if(abs(l-b)<x&&abs(r-b)<x){
        cout<<"-1\n";return ;
    }
    if(a<b){
        if(abs(l-a)>=x)cout<<2<<'\n';
        else if(abs(r-b)>=x)cout<<2<<'\n';
        else cout<<3<<'\n';
    }else{
        if(abs(r-a)>=x)cout<<"2\n";
        else if(abs(l-b)>=x)cout<<"2\n";
        else cout<<3<<'\n';
    }
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

D - Make It Round

思路:n=k*2a*5b,让a和b的数目先相同,再同时都增加,直到不能加为止,再乘上2~9中满足小于等于m的数

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int n,m;cin>>n>>m;
    int cnt2=0,cnt5=0,nn=n;
    while(nn&&nn%2==0){
        cnt2++;nn/=2;
    }
    while(nn&&nn%5==0){
        cnt5++;nn/=5;
    }
    int ad=1;
    while(cnt2<cnt5){
        if(ad*2>m)break;
        ad*=2;cnt2++;
    }
    while(cnt2>cnt5){
        if(ad*5>m)break;
        ad*=5;cnt5++;
    }
    while(ad*10<=m){
        ad*=10;
    }
//    cout<<ad<<' ';
    cout<<m/ad*n*ad<<'\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 Humanoid

思路:当前h越大,使用药水后的h一定更大;所以先吸收能吸收的人,直到不能吸收后再用药水,由于药水只有三个,枚举每一种情况取最大值即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
typedef pair<int,int>PII;
typedef pair<string,int>PSI;
typedef pair<string,string>PSS;
const int N=5e5+5,INF=0x3f3f3f3f,Mod=1e9+7,mod=998244353;
const double eps=1e-6;


void solve(){
    int n,h;cin>>n>>h;
    vector<int>f={2,2,3,2,2};
    vector<int>ve(n);
    for(int i=0;i<n;++i)cin>>ve[i];
    sort(ve.begin(),ve.end());
    int ans=0;
    auto get=[n,h,ve,f](int x){
        int cnt=0,hh=h,r=x;
        for(int i=0;i<n;++i){
            if(hh>ve[i])hh+=ve[i]/2,cnt++;
            else{
                if(r-x>=3)break;
                hh*=f[r++];
                i--;
            }
        }
        return cnt;
    };
    for(int i=0;i<3;++i){
        ans=max(ans,get(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

 

F - All Possible Digits

思路:每次操作加一,不用进位就能完成的情况:没写的最小的数大于最后一位;

需要进位:没写的最小的数小于最后一位;需要模拟出进一次位的过程,之后再找到没写的最大的数即是最后要操作到的数

由于最多有100位,那么写了的数初始最多有100个,暴力找没写的极值数即可

#include<bits/stdc++.h>
using namespace std;
#define int long long
//#define int __int128
#define double long double
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 double eps=1e-6;

void solve() {
    int n,p;cin>>n>>p;
    vector<int>ve(n+5);
    set<int>se;
    int ans=0;
    for(int i=n-1;i>=0;--i)cin>>ve[i],se.insert(ve[i]);
    if(se.size()==p){
        cout<<"0\n";return ;
    }
    int tr=-1,tl=-1;
    for(int i=p-1;i>=0;--i){
        if(!se.count(i)){
            tr=i;break;
        }
    }
    for(int i=0;i<p;++i){
        if(!se.count(i)){
            tl=i;break;
        }
    }
    if(tl>ve[0]){
        cout<<tr-ve[0]<<'\n';return ;
    }
    ans+=p-1-ve[0];
    //ve[0]=0;
    se.insert(0);
    ve[1]++;ans++;
    if(n==1)n++;
    for(int i=1;i<n;++i){
        if(ve[i]>=p){
            ve[i]-=p,se.insert(ve[i]),ve[i+1]++;
            if(i==n-1)se.insert(ve[n]);
        }
        else{
            se.insert(ve[i]);
            break;
        }
    }
    tr=0;
    for(int i=ve[0];i>=0;--i){
        if(!se.count(i)){
            tr=i;break;
        }
    }
    ans+=tr;
    cout<<ans<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

G - Restore the Permutation

思路:要满足字典序最小,且偶数位的数已确定,正着找小于该数的数会考虑很多情况,可以倒着找,对于一个偶数位的数,找到小于它的最大的数为最优的情况,若存在多个偶数位,靠后的先选,用优先队列维护

#include<bits/stdc++.h>
using namespace std;
//#define int long long
//#define int __int128
#define double long double
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 double eps=1e-6;
int n;
void solve() {
    cin>>n;
    vector<int>ve(n+1),pos(n+1);
    for(int i=2;i<=n;i+=2){
        cin>>ve[i];pos[ve[i]]=i;
    }
    priority_queue<int>q;
    for(int i=n;i>=1;--i){
        if(pos[i])q.push(pos[i]);
        else{
            if(q.empty()){
                cout<<"-1\n";return ;
            }
            ve[q.top()-1]=i;q.pop();
        }
    }
    for(int i=1;i<=n;++i)cout<<ve[i]<<' ';cout<<'\n';
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    int T=1;
    cin>>T;
//    init();
    while(T--){
        solve();
    }
    return 0;
}
View Code

 

标签:typedef,ve,834,int,double,Codeforces,long,Div,define
From: https://www.cnblogs.com/bible-/p/17756656.html

相关文章

  • pytorch nn.KLDivLoss()损失计算
    参考:https://blog.csdn.net/L888666Q/article/details/126346022?utm_medium=distribute.pc_relevant.none-task-blog-2~default~baidujs_baidulandingword~default-1-126346022-blog-128974654.235^v38^pc_relevant_default_base&spm=1001.2101.3001.4242.2&utm_relev......
  • Educational Codeforces Round 156 A-D
    A.SumofThree思路1:1.把数拆成1,2,n-32.如果(n-3)%3==0,那么拆成1,4,n-5,可证明n-3如果可被3整除,那么再左移两位一定除不尽思路2:1.如果n是奇数,那么可取一个数为2,其他两数为相邻数,如果两数其中一位被整除,那么两者往外走2.如果n为偶,那么可取一个数为1,同理上点击查看代码#inclu......
  • Educational Codeforces Round 156 (Rated for Div. 2)
    Preface沉迷Galgame不打CF懒狗闪总出列!这场在大物课上口胡了前四个题,回去写了也都很顺,然后E题本来做不来的,看了眼昨天校队群里的消息就会做了F题什么东西直接弃A.SumofThree当\(n\bmod3\ne0\)时,用\((1,2,z)\)来凑;否则当\(n\bmod3=0\)时,用\((1,4,z)\)来凑#include<cst......
  • Codeforces Round 706 (Div. 2) A. Split it!
    给一个长度为\(n\)的字符串\(s\)。给定一个正整数\(k\)。询问\(s\)能否等于\(a_1+a_2+\cdots+a_k+a_{k+1}+R(a_k)+R(a_{k-1})+\cdots+R(a_{1})\)。其中\(a_i\)代表一个非空字符串,\(R(a_i)\)代表\(a_i\)的\(reverse\)。由于\(a_{k+1}\)......
  • Codeforces Round 707 (Div. 2, based on Moscow Open Olympiad in Informatics) B. N
    按以下\(n\)次操作制作蛋糕。叠上第\(i\)块面包,然后浇上\(a_i\)单位的奶油。可以使当前往下\(a_i\)块面包沾上奶油。输出空格隔开的\(n\)个数,第\(i\)个的\(0/1\)代表第\(i\)块面包是否沾有奶油。比较显然的思路可以进行差分修改。view1#include<bits/std......
  • Codeforces Round 834 (Div. 3)
    A.Yes-Yes?#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongusingpii=pair<int,int>;usingvi=vector<int>;conststringT="Yes";voidsolve(){strings;cin>>s;inti=-1;......
  • Codeforces Round 902 Div 1 (CF 1876)
    A.HelmetsinNightLight按花费sort一下,\(b<p\)就让他用\(b\)的花费告诉别人,剩下的人一开始用\(p\)的花费告诉即可。B.EffectsofAntiPimples发现一个数会被所有它的因数贡献,\(O(n\sqrt{n})\)随便算一算,式子略。C.AutosynthesisSolution1想到了建图但没有完......
  • Educational Codeforces Round 156 (Rated for Div. 2)
    EducationalCodeforcesRound156(RatedforDiv.2)A.SumofThree解题思路:如果\(n\leq6或n=9\),无解。若\(n\%3==0,t=\lfloor\frac{3}{n}\rfloor\):若\(t=0\)构造\(1,4,n-5\)否则,构造\(t-3,t,t+3\)若\(n\%3==1:构造1,2,n-3\)若\(n......
  • Codeforces Round 902 (Div. 2, based on COMPFEST 15 - Final Round)
    目录写在前面ABCDE写在最后写在前面比赛地址:https://codeforces.com/contest/1877。呜呜铃果唱歌太好听了、、、我宣布是第二喜欢的声线,第三喜欢是东北切蒲英,第一喜欢绝赞招募中。这下不得不成为数码推了、、、A答案为\(-\suma_i\)。懒得写代数式子推了,赛时看完题直接......
  • Educational Codeforces Round 152 (Div. 2) D. Array Painting(双指针)
    EducationalCodeforcesRound152(Div.2)D.ArrayPainting//思路:双指针找连续正数段//若段中出现2,则更新两头的0的情况,若为涂色则改为true//若无2,则优先更新左侧0,若左0已经为true,则更新右侧0//数组开头结尾特判#defineintlonglong#defineldlongdoubleusingnam......