Educational Codeforces Round 82 (Rated for Div. 2)(A-C)(暑假训练8.13)(D可做)

本文主要是介绍Educational Codeforces Round 82 (Rated for Div. 2)(A-C)(暑假训练8.13)(D可做)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

前排高铁
经典战绩图

总结：自己模的一场，打之前看自己之前a题一直没有通过，所以模的时候a题想的比较透彻，然后过了之后罚站一个半小时，一开始开b想了个数学，发现wa了之后想可能没这么简单，看c能做果断开c，敲了个快百行的构造题，提交都没有自信果然wa了555，但是赛后补两个题不到三十分钟全补完了（就离谱！）状态感觉越来越好了捏

A. Erasing Zeroes

题意：给定一个由 0和1组成的字符串s，你需要去掉一些0，使得串内所有的 1 都连续，问最小去掉的0的个数。
思路：可以从结果去想，我要使得最后的串1都连续那么肯定只有三个结果
①:111110000 →前缀1
②:000001111 →后缀1
③:000111100 →中间1
那么暴力的模拟三种情况的删除情况，取个min即可
对于①而言，当出现第一个0之后再出现1那么1之前的0都要删
对于②而言，出现第一个1之后再出现0就删除即可
对于③而言，找前面①和②的最先找到的那么一段即可
具体看代码吧~

#include<bits/stdc++.h>using namespace std;int main()
{string s1;int n,i,j,t;cin>>t;while(t--){cin>>s1;int cnt=0,cnt1=0,cnt2=0;for(i=0;i<s1.length();i++){if(s1[i]=='0') cnt2++;}int d=s1.length();int f=0,ff=0;for(i=0;i<d;i++)  //000001111111{if(s1[i]=='1'){f=1;}else if(f==1&&s1[i]=='0'){cnt++;}else if(f==0&&s1[i]=='0')ff++;}f=0;for(i=0;i<d;i++) //111100000{if(s1[i]=='0'){f++;}else{cnt1+=f;f=0;}}cnt2-=(f+ff);cout<<max(0,min(cnt,min(cnt1,cnt2)))<<endl;}
}

B. National Project

题意：
工程队修长度为n的路，每天可以修长度为1的路或者跳过。每g天好天气以后是b天坏天气，然后又是g天好天气，b天坏天气，以此类推。在好天气修路长度至少为总长度的一半，求修完路所需的最小天数（包括跳过的天数）。
思路：
其实是个比较简单的数学题，虽然是1400分，可能是题意给的不清楚吧，首先明确题意的要求有两个：①所有道路必须要铺满，②至少在晴天铺满一半的路。

之后其实比较好想了 ，先把需要在晴天铺的天数求出来，再判断在晴天铺的天数是否能被g个连续的好天气整除，看需要几段好天气，因为知道要几段好天气就可以知道已经过去了几段差天气，再判断当条件②铺了一半之后，路有没有铺满。
①铺满了就输出好天气所用的天数+过去了几段差天气的天数
②没铺满就输出所需好天气天数+所需坏天气
本题还可以二分答案~
具体看代码吧~

#include<bits/stdc++.h>using namespace std;
#define int long longsigned main()
{int g,b,n,i,t,need1,need2;cin>>t;while(t--){cin>>n>>g>>b;need1=(n%2==0?n/2:n/2+1);need2=n-need1;int cnt1=0,cnt2=0;int ans=0;if(g>=n){cout<<n<<endl;continue;}if(need1%g==0){cnt1=need1/g;}else{cnt1=need1/g+1;}int ans1=0,ans2=0;ans2=(cnt1-1)*b;if(ans2>=need2){cout<<need1+ans2<<endl;}else{cout<<need1+need2<<endl;}}return 0;
}

C - Perfect Keyboard

题意：
给出一个字符串S，求是否存在一种26个字母排列的构造方式T使得S中任意相邻两位都在T中相邻，数据保证S不会存在相邻两位字母相同，若存在则输出YES并输出一种合法的构造方式，否则输出NO。
思路：
先去想能构造的情况，会发现只有两种，一种是有两个字母相邻的字母只有一个，那么一个做头一个做尾巴，如果能一直从头连到尾，那么成立，还有一种就是我wa蒙了且没考虑的情况，就是密码长度为1的时候。。
接下来就是大构造啦_{通过用结构体存每个字母相邻的两个或者一个字母是哪种，然后如果只有两个字母出现过一次，那么就进入循环判断，任取一个字母当头，递归的去找}

#include<bits/stdc++.h>using namespace std;struct node{char c1,c2;int cnt;
}mo[1000];
void inti()
{for(int i=0;i<999;i++){mo[i].cnt=0;mo[i].c1=' ';mo[i].c2=' ';}}
int main()
{string s1;int t,n,i,j,d;cin>>t;while(t--){inti();cin>>s1;d=s1.length();for(i=0;i<d;i++){if(i==0){mo[s1[i]].c1=s1[i+1];mo[s1[i]].cnt++;}else if(i==d-1){if(mo[s1[i]].cnt==0)mo[s1[i]].c1=s1[i-1],mo[s1[i]].cnt++;else{if(s1[i-1]!=mo[s1[i]].c1)mo[s1[i]].c2=s1[i-1],mo[s1[i]].cnt++;}}else{int cn=mo[s1[i]].cnt;if(s1[i+1]==s1[i-1]){if(cn==0){mo[s1[i]].c1=s1[i+1];mo[s1[i]].cnt++;}else{if(s1[i-1]!=mo[s1[i]].c1)mo[s1[i]].c2=s1[i-1],mo[s1[i]].cnt++;}}else{mo[s1[i]].c1=s1[i+1];mo[s1[i]].c2=s1[i-1];mo[s1[i]].cnt=2;}}}int anss=0,flag=0;char bg,ed;for(i=0;i<26;i++){char c1='a'+i;if(mo[c1].cnt==1){anss++;if(anss==1) bg=c1;else ed=c1;}else if(mo[c1].cnt!=0){flag=1;}}if(anss==1){if(flag==1){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;cout<<bg;for(i=0;i<26;i++){char c1='a'+i;if(mo[c1].cnt==0) cout<<c1;}cout<<endl;}}else if(anss==2){int flag=0;char cc=bg;string anss="";map<char ,int >m1;anss+=cc;m1[cc]++;int cntt=0;char lf=bg;while(1){if(mo[cc].c1!=lf){lf=cc;cc=mo[cc].c1;}else{lf=cc;cc=mo[cc].c2;}anss+=cc;m1[cc]++;if(m1[cc]>=2){flag=0;break;}if(cc==ed){flag=1;break;}cntt++;if(cntt==50){break;}}if(flag==0){cout<<"NO"<<endl;}else{cout<<"YES"<<endl;for(i=0;i<26;i++){char x='a'+i;if(m1[x]==0)anss+=x;}cout<<anss<<endl;}}else{cout<<"NO"<<endl;}}
}

这篇关于Educational Codeforces Round 82 (Rated for Div. 2)(A-C)(暑假训练8.13)(D可做)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---