Codeforces Round #604解题报告

wenzhuan

发布于 2022-08-15 12:32:34

2050

发布于 2022-08-15 12:32:34

文章被收录于专栏：你会烧尽还是结冰

突然想更博呗

rk553 rating+35 一边打一边看学弟改的稿子233 有点小炸下辈子再也不倒开了.jpg

A: Beautiful String

题目链接题意：希望构造一个邻位不相同的只有abc的字符串给定一个带有’?’的串 ‘?’可以任意替换为abc 问能不能构造出符合要求的串一开始被卡了一下

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define sc(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e5 + 5;
char s[maxn];
int solve(){
    scs(s); int len=strlen(s);
    if(s[0]=='?'&&s[1]!='a') s[0]='a';
    else if(s[0]=='?') s[0]='b';
    if(s[len-1]=='?'&&s[len-2]!='a') s[len-1]='a';
    else if(s[len-1]=='?') s[len-1]='b';
    rep(i,1,len-1) if(s[i]=='?'){
        if(s[i-1]=='a'){
            if(s[i+1]!='b') s[i]='b';
            else s[i]='c';
        }
        else{
            if(s[i+1]!='a') s[i]='a';
            else if(s[i-1]=='b') s[i]='c';
            else s[i]='b';
        }
    }
    rep(i,1,len) if(s[i-1]==s[i]) return puts("-1");
    pf("%s\n",s); return 0;
}
int main(){
    int _; sc(_); while(_--) solve();
}

B: Beautiful Numbers

题目链接题意：给定n和初始序列问在1到n中的i有哪些满足在初始序列中存在区间长度为i且区间内只有1-i的数真好写啊我为什么不先写B 判一下左右就行写得复杂了一点

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define sc(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
int a[maxn],ans[maxn];
pii p[maxn];
int solve(){
    int n,pos; sc(n); rep(i,1,n+1){
        sc(a[i]); p[i].first=a[i]; p[i].second=i;
    } sort(p+1,p+n+1); ans[1]=1;
    int l=1e9,r=0; rep(i,1,n+1){
        l=min(l,p[i].second);
        r=max(r,p[i].second);
        if(r-l>=i) ans[i]=0;
        else if(r-l<i) ans[i]=1;
        else ans[i]=0;
    }
    rep(i,1,n+1) pf("%d",ans[i]);
    pf("\n");
}
int main(){
    int _; sc(_); while(_--) solve();
}

C: Beautiful Regional Contest

题目链接题意：分金银铜牌规则是获得金牌的人题数严格大于得银牌的银牌的严格大于铜牌的金牌数严格小于银牌数和铜牌数三个牌子的总和不多于总人数的一半给定人数和过题数希望牌子尽量多输出方案贪心金牌只取最多过题数的人数银牌取到比金牌多就break 铜剩下判是否符合要求

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 1e6 + 5;
int a[maxn],vis[maxn];
int main(){
    int _; sc(_); while(_--){
        int n,a0; sc(n); sc(a0);
        rep(i,0,a0+1) vis[i]=0; a[1]=a0; vis[a0]++;
        rep(i,2,n+1) sc(a[i]),vis[a[i]]++;
        int mid=n/2;
        if(a[mid]==a[mid+1]){
            while(a[mid]==a[mid+1]) mid--;
        }
        int aa,b=0,c=0; aa=vis[a0];
        dep(i,a0-1,0) if(vis[i]){
            b+=vis[i]; if(b>aa) break;
        }
        if(b<=aa||aa+b>=mid){
            pf("0 0 0\n"); continue;
        } c=mid-aa-b;
        if(c<=aa){
            pf("0 0 0\n"); continue;
        }
        pf("%d %d %d\n",aa,b,c);
    }
}

D: Beautiful Sequence

题目链接题意：给abcd四个数代表有a个0 b个1 c个2 d个3 问能不能构成相邻位差值绝对值为1的序列本来以为是细节题思维还是不够缜密很多请况没考虑到233 看了dls代码写的是按题意模拟真好看啊 wxhtxdytxdy

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scs(x) scanf("%s", x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
int a[5],b[5];
vector<int>vv; 
int main(){
    rep(i,0,4) sc(a[i]);
    rep(i,0,4){
        rep(j,0,4) b[j]=a[j];
        if(!b[i]) continue; int x=i; 
        vv.clear(); while(1){
            vv.push_back(x); b[x]--;
            if(x&&b[x-1]) x--;
            else if(x!=3&&b[x+1]) x++;
            else break;
        }
        if(!b[0]&&!b[1]&&!b[2]&&!b[3]){
            pf("YES\n");
            rep(i,0,vv.size()) pf("%d ",vv[i]);
            return pf("\n"),0;
        }
    } return pf("NO\n"),0;
}

E: Beautiful Mirrors

题目链接文字先咕了好困随缘更

#include<bits/stdc++.h>
#define pf printf
#define sc(x) scanf("%d", &x)
#define scl(x) scanf("%lld", &x)
#define mst(a,x) memset(a, x, sizeof(a))
#define rep(i,s,e) for(int i=s; i<e; ++i)
#define dep(i,e,s) for(int i=e; i>=s; --i)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn = 2e5 + 5;
const int mod = 998244353;
ll qpow(ll a,ll b){
    ll ans=1; while(b){
        if(b&1) ans=ans*a%mod;
        b>>=1; a=a*a%mod;
    } return ans;
}
ll a[maxn],q1[maxn],q2[maxn];
int main(){
    int n; sc(n); rep(i,0,n) scl(a[i]);
    ll t=qpow(100,mod-2); q1[n]=q2[n]=0;
    dep(i,n-1,0){
        q1[i]=a[i]*t%mod*q1[i+1]%mod;
        q1[i]++; q1[i]%=mod;
        q2[i]=a[i]*t%mod*q2[i+1]%mod;
        q2[i]+=t*(100-a[i])%mod; q2[i]%=mod;
    }
    ll ans=q1[0]*qpow((1-q2[0]+mod)%mod,mod-2)%mod;
    pf("%lld\n",ans);
}

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

break