题面描述

给定 n 个 01 串，每次你可以从某个串开头移除一个字符并把它加入一个新串 S 的末尾。最大化 S 中相邻两个字符相同的对数。

输入格式

第一行一个正整数 n 表示串的个数。

接下来 n 行，每行一个 01 字符串。

输出格式

一行一个整数表示答案。

输入输出样例

输入 #1

3
0011
0110
1100

输出 #1

9

说明/提示

样例解释

最优方案下，每次取的串的编号为 1,1,2,1,2,3,1,2,3,2,3,3，最终的 S=000111111000。

数据范围

设 s 表示输入的 01 串的长度之和。

对于所有数据，保证 $1\leq n\leq s\leq 10^6$。

分析过程

要最大化S中相邻两个字符相同的对数。那么相同的字符要尽可能的堆积在一块。

若有n个相同的数在一起，那么相邻两个字符的对数存在n-1对。

当我们能把所有的字符串都尽可能按相同的字符在一块的方式拼接好的话，只需要将连续相同的字符个数-1进行累加即可求出总对数。

拼接后的字符串不是以0开头就是以1开头。我们可以分别求解出以0开头和以1开头的总对数，两者取其高即可。

将合并后的字符串可看做，0和1交替出现的字符串。

实现代码

#include <iostream>
#include <cstdio>
#include <string>
using namespace std;
const int N=1e6+5;
string s;
/*
将合并后的字符串可看做0和1交替出现的字符串
num[] 存储合并后以0开头的 信息 
01010101...
num[i]=k 第i段连续相同的元素个数 

num2[] 存储合并后以1开头的 信息
10101010...
num2[i]=k 第i段连续相同的元素个数 
*/
int num[N],num2[N];
int main(){
	int n,MAX1=0,MAX2=0;//MAX1-0开头最大的段数 MAX2-1开头的最大的段数
	cin>>n;
	for(int i=1;i<=n;i++){
		int cnt1=0,cnt2=0;//cnt1-0开头的段数 cnt2-1开头的段数
		cin>>s;
		int len=s.length();
		for(int j=0;j<len;j++){//遍历输入的字符串
            //统计以0开头做标准，各段相同元素的个数
			if((cnt1%2)==(s[j]-'0')){//当各位置，对应上匹配的元素
				num[cnt1]++;//统计个数
			}else{//出现不同元素
				num[++cnt1]++;//段数增加，增加下一段个数
			}
            //统计以1开头做标准，各段相同元素的个数
			if((cnt2+1)%2==(s[j]-'0')){//当各位置，对应上匹配的元素
				num2[cnt2]++;//统计个数
			}else{
				num2[++cnt2]++;//段数增加，增加下一段个数
			}
		}
		MAX1=max(MAX1,cnt1);//更新最大的段数
		MAX2=max(MAX2,cnt2);
	}
	int sum1=0,sum2=0;
	for(int i=0;i<=MAX1;i++){//统计合并后以0开头的字符串，对数个数
		sum1+=(num[i]-1);
	}
	for(int i=0;i<=MAX2;i++){//统计合并后以1开头的字符串，对数个数
		sum2+=(num2[i]-1);
	}
	cout<<max(sum1,sum2);//两者取其高
	return 0;
}

Q.E.D.