本篇题解同步发表于我的 AtCoder 补题记录。

蒟蒻初二时看到晚上有一场 ARC，兴致勃勃地去打了一下，没想到被 A 题硬控，爆零了。

如今，我重新理了一下当时的几个题，觉得这个题特别有意思，写篇题解纪念一下。

这也是我的第一篇黑题题解。

考察知识点

• 【2】string 类与相关函数
• 【3】贪心法

本题难度较大，主要考察选手对贪心法的灵活运用，同时也需要选手对 string 类有一定的理解。

判断某一种已排好的状态是否合法

贪心法。

因为不能将两个 $\texttt R$ 配对，所以任何 $\texttt R$ 的数量大于 $\texttt B$ 的字符串都是不合法的。

每一次将第一个人和后面任意一个人匹配，将这两个人从队列内删除，更新队内人的编号。

如果目前的 $1$ 号人帽子为 $\texttt{R}$，需要选取一个 $\texttt{B}$。因为 $\texttt{B}$ 对后面的要求较为宽松（不能都是 $\texttt{R}$，但可以都是 $\texttt{B}$），所以尽量选位置偏后的 $\texttt{B}$。

如果目前有一个 $\texttt B$，应该首先考虑和 $\texttt R$ 配对，配对掉编号最小的 $\texttt R$。

如果没有 $\texttt R$，也从后面开始匹配 $\texttt B$。

求长度为 $2^n$ 的字典序最大的合法字符串

用 $t_n$ 代表长度为 $2^n$ 的字典序最小的合法字符串，规定 $\texttt B\le\texttt R$。

首先定义 $t_0=\texttt R$。但实际上它不会被最终使用。

之后求 $t_i$ 时遍历 $t_{i-1}$，若 $t_{i-1,j}=\texttt R$，就直接新增一个 $\texttt R$，否则新增一个 $\texttt {BR}$。

若新增不够长度，直接在最后增加若干个 $\texttt B$ 即可。

所以 $t_1=\texttt{RB},t_2=\texttt{RBRB},t_3=\texttt{RBRRBRBB}$。以此类推。

如何计算答案

令 $S_i$ 为 $S$ 串中的第 $i$ 个 $\texttt B$ 的位置，$T_i$ 为 $T_n$ 串中第 $i$ 个 $\texttt B$ 的位置。可通过往前移动 $S$ 串中的 $\texttt B$，实现 $S_i\le T_i$。

答案即为 $\sum \max(0,S_i-T_i)$。

扫一遍即可，时间复杂度 $O(2^n)$。

代码

需要对字符串函数的时间复杂度和字符串的下标问题稍微注意一下，不然会 TLE。

#include<bits/stdc++.h>
#define int long long
using namespace std;

int n;
string s;
string t;
string t1;	//滚动 t  
int sch[3*114514];
int tch[3*114514];
int ptr1,ptr2;
int include13=0;
signed main(){
	memset(sch,0x3f,sizeof(sch));
	memset(tch,0x3f,sizeof(tch));
	cin>>n;
	cin>>s;
	int n1=1<<n;
	s=' '+s;
	int a=0,b=0;
	for(int i=1;i<=n1;i++){
		a+=(s[i]=='R'),b+=(s[i]=='B');
	} 
	if(a>b){
		puts("-1");
		return 0;
	}
	t='R';
	for(int i=1;i<=n;i++){
		int n_=1<<i;
		int t_=t.size();
		for(int j=0;j<t_;j++){
			if(t[j]=='R')	t1+="R";
			else	t1+="BR";
		}
		while(t1.size()<n_)	t1+="B";
//		cout<<t1<<endl; 
		t=t1;
		t1="";
//		while(t1.size())	t1.erase(0,1);
	} 
//	cout<<endl;
//	return 0;
	for(int i=1;i<=n1;i++){//枚举 s 
		if(s[i]=='B'){
			ptr1++;
			sch[ptr1]=i;
//			cout<<ptr1<<' '<<i<<endl;
		} 
	}
//	cout<<endl;
	for(int i=0;i<t.size();i++){
		if(t[i]=='B'){
			ptr2++;
			tch[ptr2]=i+1;
//			cout<<ptr2<<' '<<i+1<<endl;
		}
	}
//	cout<<endl;
	for(int i=1;i<=3e5;i++){
		include13+=max(0ll,sch[i]-tch[i]);
	}
	cout<<include13<<endl;
	return 0;
}//午睡操场传来蝉的声音 多少年后仍然是很好听