Codeforces Round #575 (Div. 3)

45 阅读 0 评论 30 点赞

我是靠谱客的博主欢呼时光，最近开发中收集的这篇文章主要介绍Codeforces Round #575 (Div. 3)，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

是真的蠢啊，在AB两题签到题卡了一个小时，QAQ

A. Three Piles of Candies

签到题，其实把三个加起来除以二就可以了

# include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int main()
{
int q;
scanf("%d",&q);
while(q--){
LL a[3];
cin>>a[0]>>a[1]>>a[2];
sort(a,a+3);
cout<<a[1]+(a[2]-(a[1]-a[0]))/2<<endl;
}
return 0;
}

B - Odd Sum Segments

明白奇+奇=偶，偶+偶=偶，奇+偶=奇，奇数个奇数相加是奇数，偶数个奇数相加是偶数；先判断是有几个奇数，如果奇数的个数比k小，那么必然不可以；如果刚好等于k，那么必然可以；如果比k大，那么先搞出来k-1个奇数，然后再判断有多少个剩下的奇数，如果有奇数个那么就可以，如果没有那么就不可以

# include <bits/stdc++.h>
using namespace std;
int main()
{
int q;
scanf("%d",&q);
while(q--){
queue<int> a;
int n,k;
scanf("%d %d",&n,&k);
for(int i=1;i<=n;i++){
int x;
scanf("%d",&x);
if(x&1){
a.push(i);
//cout<<"@@@"<<i<<endl;
}
}
if(a.size()<k){
cout<<"NO"<<endl;
}else if(a.size()==k){
cout<<"YES"<<endl;
//cout<<a.size()<<"##"<<endl;
for(int i=1;i<=a.size();i++){
cout<<a.front()<<" ";
a.pop();
}
cout<<n<<endl;
}else{
queue<int> b;
for(int i=0;i<k-1;i++){
b.push(a.front());
a.pop();
}
if(a.size()&1){
cout<<"YES"<<endl;
for(int i=0;i<b.size();i++){
cout<<b.front()<<" ";
}
cout<<n<<endl;
}else{
cout<<"NO"<<endl;
}
}
}
return 0;
}

C. Robot Breakout

如果这个机器人不能向左走（即1操作位0），那么坐标的能够到达的最左端就是和以前的比较大的那个；如果这个机器人不能向右走（即3操作位0），那么坐标的能够到达的最右端就是和以前的比较小的那个；如果这个机器人不能向上走（即2操作位0），那么坐标的能够到达的最上端就是和以前的比较小的那个；如果这个机器人不能向下走（即4操作位0），那么坐标的能够到达的最下端就是和以前的比较大的那个。最后比较是否在绝对值位1e5的范围内存在这样一个坐标点，就阔以啦

# include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+100;
int x[MAXN];
int y[MAXN];
int f[MAXN][5];
int main()
{
int q;
scanf("%d",&q);
while(q--){
int n;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d %d %d %d %d %d",&x[i],&y[i],&f[i][1],&f[i][2],&f[i][3],&f[i][4]);
}
int lx=-1e5,rx=1e5,ly=-1e5,ry=1e5;
int flag=1;
for(int i=1;i<=n;i++){
if(f[i][1]==0) lx=max(lx,x[i]);
if(f[i][3]==0) rx=min(rx,x[i]);
if(f[i][4]==0) ly=max(ly,y[i]);
if(f[i][2]==0) ry=min(ry,y[i]);
if(lx>rx||ly>ry){
//cout<<"@@@"<<lx<<" "<<rx<<" "<<ly<<" "<<ry<<endl;
printf("0n");
flag=0;
break;
}
}
if(flag){
if(lx<=1e5&&rx>=(-1e5)&&ly<=1e5&&ry>=(-1e5)){
printf("1 %d %dn",lx,ly);
}else{
printf("0n");
}
}
}
return 0;
}

D1 D2 RGB Substring

D1D2就是数据范围不一样大，每一位有三种可能，R,G,B，不妨把三种都考虑一遍，然后求一下前缀和，就是到当前的位置以该种方法改变需要改变几次，然后对长度再遍历一遍每次去最小值就可以啦

# include <bits/stdc++.h>
using namespace std;
const int MAXN=2e5+100;
int pre1[MAXN];
int pre2[MAXN];
int pre3[MAXN];
int main()
{
int q;
scanf("%d",&q);
while(q--){
int n,k;
scanf("%d %d",&n,&k);
string a;
cin>>a;
for(int i=0;i<a.length();i++){
if(i%3==0){
if(a[i]!='R') pre1[i+1]=pre1[i]+1;
else pre1[i+1]=pre1[i];
if(a[i]!='G') pre2[i+1]=pre2[i]+1;
else pre2[i+1]=pre2[i];
if(a[i]!='B') pre3[i+1]=pre3[i]+1;
else pre3[i+1]=pre3[i];
}else if(i%3==1){
if(a[i]!='G') pre1[i+1]=pre1[i]+1;
else pre1[i+1]=pre1[i];
if(a[i]!='B') pre2[i+1]=pre2[i]+1;
else pre2[i+1]=pre2[i];
if(a[i]!='R') pre3[i+1]=pre3[i]+1;
else pre3[i+1]=pre3[i];
}else if(i%3==2){
if(a[i]!='B') pre1[i+1]=pre1[i]+1;
else pre1[i+1]=pre1[i];
if(a[i]!='R') pre2[i+1]=pre2[i]+1;
else pre2[i+1]=pre2[i];
if(a[i]!='G') pre3[i+1]=pre3[i]+1;
else pre3[i+1]=pre3[i];
}
}
int ans=3e5+100;
for(int i=1;i<=n;i++){
int l=i,r=i+k-1;
int cnt1,cnt2,cnt3;
cnt1=pre1[r]-pre1[l-1];
cnt2=pre2[r]-pre2[l-1];
cnt3=pre3[r]-pre3[l-1];
if(r>n) break;
else{
ans=min(ans,cnt1);
ans=min(ans,cnt2);
ans=min(ans,cnt3);
}
}
cout<<ans<<endl;
}
return 0;
}

E. Connected Component on a Chessboard

就是从第二行开始，先按照小的那个输出，然后再在1，3行补足不够的那个

# include <bits/stdc++.h>
using namespace std;
int main()
{
int q;
scanf("%d",&q);
while(q--){
int b,w;
scanf("%d %d",&b,&w);
int aa,bb,cc;
aa=min(b,w);
bb=max(b,w);
cc=aa*4-(aa-1);
if(bb>cc){
cout<<"NO"<<endl;
}else{
cout<<"YES"<<endl;
int l;
if(aa==b) l=3;
else l=2;
for(int i=l;i<l+2*aa;i++){
cout<<2<<" "<<i<<endl;
}
bb=bb-aa;
//cout<<"bb="<<bb<<endl;
if(bb){
for(int i=l;i<l+2*aa;i+=2){
cout<<1<<" "<<i<<endl;
bb--;
if(bb==0) break;
cout<<3<<" "<<i<<endl;
bb--;
if(bb==0) break;
}
if(aa==b){
if(bb) cout<<2<<" "<<2<<endl;
}else{
if(bb) cout<<2<<" "<<1<<endl;
}
}
}
}
return 0;
}