ZOJ3983 & CCPC2017 秦皇岛站 签到题C E L题解
快要省赛了所以就开始补以前比赛的题目。不过由于水平限制只能补补签到题，算是监督自己吧，决定把这最后两个星期补的水题都写写题解吧。
C - Crusaders Quest
C题理解了题意就是消除方块，求最大消除的三连块数量。因为只有9个方块，而且每种方块的数量都只有3个，所以其实第一反应是暴力，但是我刚开始理解错了题意，想着每种字母的数量不一样，所以打算暴力枚举每个位置上的消除和未被消除两种状态，虽然暴力枚举好像理论上也行，不过我毕竟代码能力弱爆，我居然卡了半天没想到怎么枚举完状态之后递归下一层枚举？？？因为每层枚举的时候他的方块的数量都在变化，然后我就卡住了，GG，菜是真的菜。后来学弟说他每种方块只有三个，那么就不需要暴力枚举每个位置上的两种状态了，思考了一下，首先确定只有1，2，3三种答案。如果扫一遍直接得到3，那么就肯定是3了，但是也有可能是一个三连块消除然后其他的自己就拼成了下一个三连块，所以我写了一个比较特殊的coun函数，凡是消除完又构成三个了就继续消除，然后统计一共消除了多少。所以我拿到数组先扫一遍，如果得到3，答案为3。如果得到1，那么答案就是2；如果得到0，那么就要考虑一下情况，得到0的话，那么最好的情况也就是2，最差是1，因为一共三种字符且每种各三个，所以我们直接暴力把移除三种字符的情况能得到的结果计算，并且取其中的最大值，就得到了答案，代码如下。
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。1 #include<bits/stdc++.h> 2 using namespace std; 3 int ans; 4 int coun(string str){ 5 int ans=0; 6 for(int i=0;i<str.size();){ 7 if(str[i]==str[i+1] && str[i+1]==str[i+2]){ 8 ans++; 9 str.erase(i,3); 10 i=0; 11 }else{ 12 i++; 13 } 14 } 15 return ans; 16 } 17 18 int main(){ 19 20 ios::sync_with_stdio(false); 21 int t; 22 string str; 23 cin>>t; 24 while(t--){ 25 ans=0; 26 cin>>str; 27 int cnt1=0,cnt2=0,cnt3=0; 28 ans=coun(str); 29 if(ans==3){ 30 cout<<ans<<endl; 31 continue; 32 } 33 if(ans==1){ 34 cout<<"2"<<endl; 35 continue; 36 } 37 if(ans==0){ 38 string str1=str; 39 str1.erase(std::remove(str1.begin(),str1.end(),'a'),str1.end()); 40 ans=max(ans,coun(str1)); 41 42 string str2=str; 43 str2.erase(std::remove(str2.begin(),str2.end(),'g'),str2.end()); 44 ans=max(ans,coun(str2)); 45 46 string str3=str; 47 str3.erase(std::remove(str3.begin(),str3.end(),'o'),str3.end()); 48 ans=max(ans,coun(str3)); 49 50 if(ans>0){ 51 cout<<"2"<<endl; 52 }else{ 53 cout<<"1"<<endl; 54 } 55 } 56 } 57 return 0; 58 }
然后是E题，签到题的特点大概就是第一反应都让人觉得是暴力，但是这题思考了一下暴力方法。首先能确定的是，因为插第i个字符需要花费i-1的价值，所以当插第二个字符的时候，需要消耗1单位的价值，然而我们需要求的是最大价值，那么有没有插入一个字符能够使一个原先0个"CCPC"的字符串，变成存在2个“CCPC”的字符串呢？我们构造出"CCPCCPC",发现删除其中任意一个字符都不能使其的"CCPC"子串数量变成0个，所以得到的结论就是最多只能插入一个字符，增加多于等于2个字符都是不划算的。得到结论然后就很好算了，先统计一下原串有多少个"ccpc"然后考虑再不影响原串数量的情况下，有没有能够构成CCPC的字串，如果有，那么答案就是原串CCPC的数量+1，如果没有答案就是原串CCPC的数量。代码如下
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 6 int main() 7 { 8 9 ios::sync_with_stdio(false); 10 cin.tie(0);cout.tie(0); 11 int t,n,m; 12 string str; 13 cin>>t; 14 while(t--){ 15 cin>>n>>str; 16 int cnt=0,ans=0; 17 for(int i=0;i<n;i++){ 18 if( str[i]=='C' && str[i+1]=='C' && str[i+2]=='P' && str[i+3]=='C'){ 19 ans++; 20 } 21 if( str[i]=='C' && str[i+1]=='P' && str[i+2]=='C' && (str[i-1]!='C' || i<1)){ 22 cnt++; 23 continue; 24 } 25 if( str[i]=='C' && str[i+1]=='C' && str[i+2]=='C' && (str[i+3]!='P' || str[i+4]!='C')){ 26 cnt++; 27 continue; 28 } 29 if( str[i]=='C' && str[i+1]=='C' && str[i+2]=='P' && (str[i+3]!='C' || i>=n-3)){ 30 cnt++; 31 continue; 32 } 33 } 34 //cout<<cnt<<" "<<ans<<endl; 35 if(cnt){ans++;} 36 cout<<ans<<endl; 37 } 38 return 0; 39 }
L - One-Dimensional Maze
L题是确实水了，按照题意，从起点开始，往左扫一遍统计如果往左走需要改变多少个R，然后往右扫统计需要改变的L数量，两个数量取其中小的，就是答案。代码如下
1 #include<bits/stdc++.h> 2 using namespace std; 3 typedef long long ll; 4 5 6 int main() 7 { 8 ios::sync_with_stdio(false); 9 cin.tie(0);cout.tie(0); 10 int t,n,m; 11 string str; 12 cin>>t; 13 while(t--){ 14 int cnt1=0,cnt2=0; 15 cin>>n>>m; 16 cin>>str; 17 int len=str.size(); 18 for(int i=1;i<m;i++){ 19 if(str[i]=='R'){ 20 cnt1++; 21 } 22 } 23 for(int i=m-1;i<n-1;i++){ 24 if(str[i]=='L'){ 25 cnt2++; 26 } 27 } 28 int ans=min(cnt1,cnt2); 29 cout<<ans<<endl; 30 } 31 return 0; 32 }
2019-05-05 17:28:09
