前排高铁
经典战绩图
总结：自己模的一场，打之前看自己之前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 long signed 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; } } }
