「arc113E」Rvom and Rsrev 题解

题意

\(~~~~\) 有一个仅由 ab 组成的字符串 \(s\)。每次可以选择两个位置分别为 \(l,r\) 且 \(s_l = s_r\) 并将 \(s[l \cdots r]\) 一段翻转后删除 \(s_l,s_r\)。问经过最多无限次操作可以操作出来的字典序最大的字符串是什么。

题解

大力分类讨论题,恶心心。

\(\sf 1\) 若 \(cnt_a\) 为偶数,则至少有方法使得字符串前面全部为 b ,因此不能动 b

\(~~~~\) \(\sf 1.1\) 若原串末尾为 b ,显然不可能有办法让这个 b 到最前面,故删完 a

\(~~~~\) \(\sf 1.2\) 若原串末尾为 a ,则想办法用最少操作次数把所有 a 放到最后 :

  bbabaaaaabbaababaaabbabbbbbaaaaa
    ↑           ↑
  bbbaabbaaaaabbaaabbabbbbbaaaaa
     ↑                     ↑
  bbbbbbbbabbaaabbaaaaabbaaaaa
             ↑           ↑
  bbbbbbbbabbbbaaaaabbaaaaaa
          ↑    ↑
  bbbbbbbbbbbbaaaabbaaaaaa
              ↑     ↑
  bbbbbbbbbbbbbbaaaaaaaa

\(~~~~ ~~~~\) 形式化地,我们认为若前面(除去最后的一块 a )划分出的 a 的连续段长度为 \(1\) 的有 \(x\) 个,大于 \(1\) 的有 \(y\) 个,则需要 \(\lceil \dfrac{x}{2} \rceil+y\) 次操作来把它们都放到最后,损失 a 的个数为 \(2\) 倍操作次数。

\(\sf 2\) 若 \(cnt_a\) 为奇数

\(~~~~\) \(\sf 2.1\) 若原串末尾为 a ,不动 b 显然不会更劣,因此同 1.2

\(~~~~\) \(\sf 2.2\) 若原串末尾为 b 的联通,则考虑能否将其转化为 \(2.1\) :

\(~~~~ ~~~~\) \(\sf 2.2.1\) 若联通的 b 在两个以内或联通的 b 前面没有 b ,不能转化,直接把 a 删成只留下最后一个 a

\(~~~~ ~~~~\) \(\sf 2.2.2\) 否则可以转化,剩下的 \(cnt_b-2\) 个 b 都可以在最前面,但注意若最后一个 a 块只有一个 a 的话可以通过被删掉的两个 b 尝试把它换到前面,使得操作次数可能贪心地被降低。而如果一个 a 的块能与最后交换,则那个块前面必定是 b

按照这个讨论的结果写代码就行了

代码

view code
#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;
char S[200005];
int Blo[200005],cnta,cntb;
int Geta()
{
	int cnt1=0,cnt2=0;
	for(int i=1;i<Blo[0];i++) Blo[i]>1?cnt2++:cnt1++;
	return cnta-((cnt1/2+cnt1%2+cnt2)<<1);
}
int main() {
	int T,len;
	scanf("%d",&T);
	while(T--)
	{
		memset(S,0,sizeof(S));
		scanf("%s",S+1);
		len=strlen(S+1);
		cnta=Blo[0]=cntb=0;
		for(int i=1;i<=len;i++) S[i]=='a'?cnta++:cntb++;
		for(int i=1;i<=len;i++)
		{
			if(S[i]=='a'&&(S[i-1]!='a'||i==1))
			{
				Blo[0]++;Blo[Blo[0]]=0;
				for(int j=i;j<=len&&S[j]=='a';j++) Blo[Blo[0]]++;
			}
		}
		if((!(cnta&1))||S[len]=='a')//case 1 & case 2.1
		{
			while(cntb--) putchar('b');
			if(S[len]=='a')//case 1.2
			{
				int Times=Geta();
				while(Times--) putchar('a');	
			}
			puts("");
			continue;
		}
		else
		{
			int Siz=0;
			for(int i=len;i&&S[i]=='b';i--) Siz++;
			if(Siz<=2||Siz==cntb)
			{
				for(int i=1;i<=cntb-Siz;i++) putchar('b');
				putchar('a');
				for(int i=1;i<=Siz;i++) putchar('b');
				puts("");
				continue;
			} 
			else
			{
				for(int i=1;i<=cntb-2;i++) putchar('b');
				if(Blo[Blo[0]]==1)
				{
					for(int i=1;i<Blo[0];i++)
					{
						if(Blo[i]>1&&(i>1||S[1]=='b')){swap(Blo[i],Blo[Blo[0]]);break;}
					}	
				}
				int Times=Geta();
				while(Times--) putchar('a');puts("");
				continue;
			}
		}
	}
	return 0;
}
上一篇:轻松让你理解装饰器与面向切面编程(AOP)


下一篇:python 字典拆分写入数据库(学习笔记)