Codeforces Round #604解题报告

突然想更博呗

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

A: Beautiful String

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#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
判一下左右就行 写得复杂了一点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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 铜剩下 判是否符合要求

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#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);
}