[ARC169E] Avoid Boring Matches

题解链接

非常厉害的一道题。

考虑无解是什么情况？ R 的个数超过 \(2^{n-1}\)

先考虑如何判定。从前往后考虑，如果遇到一个 B，那么如果后面有 R，就选最靠前的 R，否则选最靠后的一个 B.如果遇到 R，就选最靠后的一个 B。

但是这个判定很繁琐。我们考虑求出一个合法序列，使得他的 B 尽量靠后。设长度为 \(2^i\) 的 B 尽量靠后的串为 \(t_i\)，那么 \(t_0=\)R，考虑从 \(t_{i-1}\) 扩展到 \(t_i\).

遍历 \(t_{i-1}\)，那么遇到一个 R 的时候，他匹配的是最远的 B,\(t_i\) 增加 R。遇到一个 B 的时候，他匹配最近的 R，所以增加 BR，剩下的用 B 补全即可。

然后有一个结论.考虑原串中前 \(2^{n-1}\) 个，设第 \(i\) 个 B 在 \(g_i\) 出， \(t_n\) 第 \(i\) 个 B 在 \(h_i\) 处。当且仅当 \(\forall i,g_i\le h_i\)，串合法。

感性理解一下，如果原串有个 B 在 \(t_n\) 的 B 的后面，那么他就匹配不到 R
所以最终答案就是原串的 B 和 \(t_n\) 的 B 的位置差加起来就行了。

// LUOGU_RID: 139274680
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+5;
int n,m,k,g[N],c;
long long ans; 
char s[N],t[19][N];
int main()
{
	scanf("%d%s",&n,s+1);
	for(int i=1;s[i];i++)
		if(s[i]=='R')
			++c;
	if(c>(1<<n-1))
		return puts("-1"),0;
	t[0][1]='R';
	for(int i=1;i<=n;i++)
	{
		m=0;
		for(int j=1;j<=(1<<i-1);j++)
		{
			if(t[i-1][j]=='B')
				t[i][++m]='B',t[i][++m]='R';
			else 
				t[i][++m]='R';
		}
		while(m<(1<<i))
			t[i][++m]='B';
	}
	m=0;
	for(int i=1;i<=(1<<n);i++)
		if(t[n][i]=='B')
			g[++m]=i;
	for(int i=1;i<=(1<<n);i++)
	{
		if(s[i]=='B')
		{
			++k;
			if(k>m)
				break;
			ans+=max(i-g[k],0);
		}
	}
	printf("%lld",ans);
}