P8153 「PMOI-5」送分题/Yet Another Easy Strings Merging
题目背景
本题征集假做法和 hack 数据，如果您用假做法 AC 了，欢迎私信出题人提供 hack。
信息可能有冗余。
——command_block 《考前小贴士》
djy 在看 P8001，看错题了，很自闭，然后就有了这个题。
题目描述
给定nnn个 01 串，每次你可以从某个串开头移除一个字符并把剩下的字符串加入一个新串SSS的末尾。最大化SSS中相邻两个字符相同的对数。
例如你有1010 111两个串，如果你移除第一个串的第一个字符，则010被加入到SSS中。
串可以重复使用。
输入格式
第一行一个正整数nnn表示串的个数。
接下来nnn行，每行一个 01 字符串。
输出格式
一行一个整数表示答案。
输入输出样例 #1
输入 #1
1 1100输出 #1
4输入输出样例 #2
输入 #2
5 10010 10000 01110 111111 000000输出 #2
48说明/提示
【样例解释】
依次取走第一个字符，SSS的变化过程为100->10000->100000，答案为444。
【数据范围】
记∣s∣|s|∣s∣为字符串sss的长度，sis_isi为第iii个字符串 。
本题采用捆绑测试。
- Subtask 1（30 pts）：n,∑∣si∣≤11n,\sum|s_i|\le 11n,∑∣si∣≤11；
- Subtask 2（30 pts）：n,∑∣si∣≤103n,\sum|s_i|\le 10^3n,∑∣si∣≤103；
- Subtask 3（30 pts）：n,∑∣si∣≤105n,\sum|s_i|\le 10^5n,∑∣si∣≤105；
- Subtask 4（10 pts）：无特殊限制。
对于100%100\%100%的数据，1≤n≤1061\le n\le 10^61≤n≤106，n≤∑∣si∣≤106n\le \sum |s_i|\le 10^6n≤∑∣si∣≤106，∀i∈[1,n]\forall i\in [1,n]∀i∈[1,n]，∣si∣≥1|s_i|\ge 1∣si∣≥1。
C++实现
#include<bits/stdc++.h>#defineilinline#definereregister#defineOrzputs("Szt Lps Fjh AK IOI!");#defineIOSios::sync_with_stdio(false),cin.tie(0),cout.tie(0);usingnamespacestd;constintINF=1e9+7,mod=1e9+7;constintmaxn=2e5+10,MAXN=3e3+10,N=1e6+10;typedeflonglongLL;string s[N];LL ans,n;intL[N],sum=0;boolf1,f2;intsum1,sum2,sum3,sum4;signedmain(){IOS cin>>n;for(reinti=1;i<=n;i++)cin>>s[i],s[i]="$"+s[i],L[i]=s[i].length()-1;for(reinti=1;i<=n;i++)sum+=L[i];if(!(sum^n))returnprintf("0"),0;for(reinti=1;i<=n;i++){intcnt=0;for(reintj=L[i]-1;j>=2;j--){if(s[i][j]==s[i][j+1])cnt++;ans+=cnt;}}for(reinti=1;i<=n;i++){if(L[i]==1)continue;// 长度为 1 的串删完就成了空串，没用if(s[i][L[i]]=='0')sum1+=L[i]-1;elsesum2+=L[i]-1;for(reintj=2;j<=L[i];j++){if(s[i][j]=='0')sum3++;elsesum4++;}if(s[i][2]=='0')f1=true;elseif(s[i][2]=='1')f2=true;}if(f1&&f2)ans+=max(min(sum3,sum1)+min(sum4-1,sum2),min(sum3-1,sum1)+min(sum4,sum2));elseif(f1)ans+=min(sum3-1,sum1)+min(sum4,sum2);elseans+=min(sum3,sum1)+min(sum4-1,sum2);cout<<ans<<endl;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容
