Codeforces Round #470 (rated, Div. 1, based on VK Cup 2018 Round 1) 923D 947D 948E D. Picking Strings

题：

　　OvO http://codeforces.com/contest/947/problem/D

　　923D 947D 948E

解：

　　记要改变的串为 P1 ，记目标串为 P2

　　由变化规则可得：

　　1. B -> AC -> AAB -> AAAC -> C ( 即 B -> C -> B )

　　2. AB -> AAC -> AAAB -> B （即 AB -> B )

　　3. B -> AC -> AB ( 即 B -> AB )

　　4. A -> BC -> BB ( 即 A -> BB )

　　（由规则1可得，B 与 C 等价，所以下文 C 全由 B代替）

　　那么对于一个串 S ，可以从这个串中提取 3 个特征，记这3个特征为 val0, val1, val2,

　　这3个特征的意义为：

　　　　对于串 S，把 S 串分成2个部分 S1, S2，其中 S2 是 S 的后缀，其内含字符全为 A，使 S2 长度尽可能长，记 S2 串长度为 val2 。S1 串为去掉 S2 后的部分，记 S1 串中非 A 字符的个数为 val1 。并且，如果 S1 串为空，记 val0=0，否则 val=1。

　　（接下去的思路就是转化 P1 中的 S1 与 S2，使其与 P2 中的 S1，S2 相同）

　　然后进行分类讨论，以下 5 种情况，P1 串无法转换为 P2 串（不具体证明）

　　1. (P1.val1 & 1) != (P2.val1 & 1)

　　2. P1.val1 > P2.val1

　　3. P1.val2 < P2.val2

　　4. P1.val1 == P2.val1 && (P1.val2 - P2.val2) % 3 != 0

　　5. P1.val0 == 0 && P1.val1 < P2.val1 && P1.val2 == P2.val2

　　其余情况，P1 均可以转化为 P2

#include <iostream>

#include <cstring>

#include <cmath>

#include <algorithm>

#include <cstdio>

using namespace std;

struct Val

{

	int val0,val1,val2;

} ;

const int M=1e5+44;

char s[2][M];

int len[2],p[2][M],a[2][M],lst[2][M],b[2][M];

int lans,ans[M];

void init(int id)

{

	int tmp;

	scanf("%s",s[id]+1);

	len[id]=strlen(s[id]+1);

	for(int i=1;i<=len[id];i++)

		if(s[id][i]=='A') p[id][i]=0;

		else p[id][i]=1;

	a[id][0]=b[id][0];

	for(int i=1;i<=len[id];i++)

		a[id][i]=a[id][i-1]+(p[id][i]==0),b[id][i]=b[id][i-1]+(p[id][i]==1);

	tmp=0;

	for(int i=1;i<=len[id];i++)

		if(p[id][i]==1)

			tmp=i,lst[id][i]=tmp;

		else lst[id][i]=tmp;

}

Val solve(int id,int li,int ri)

{

	int tag=lst[id][ri],part0,part1,part2;

	if(tag<li) tag=li-1,part0=0;

	else part0=1;

	part2=(a[id][ri]-a[id][tag]);

	part1=(b[id][ri]-b[id][li-1]);

	return Val{part0,part1,part2};

}

bool check(Val tp0,Val tp1)

{

	if((tp0.val1&1)!=(tp1.val1&1)) return false;

	if(tp0.val1>tp1.val1) return false;

	if(tp0.val2<tp1.val2) return false;

	if(tp0.val1==tp1.val1 && (tp0.val2-tp1.val2)%3!=0) return false;

	if(tp0.val0==0 && tp0.val1<tp1.val1 && tp0.val2==tp1.val2) return false;

	return true;

}

int main()

{

	init(0),init(1);

	int cas,li0,ri0,li1,ri1;

	Val tp[2];

	lans=0;

	scanf("%d",&cas);

	while(cas--)

	{

		scanf("%d%d%d%d",&li0,&ri0,&li1,&ri1);

		tp[0]=solve(0,li0,ri0),tp[1]=solve(1,li1,ri1);

//		cout<<tp[0]<<" "<<tp[1]<<endl;

		if(check(tp[0],tp[1])) ans[++lans]=1;

		else ans[++lans]=0;

	}

	for(int i=1;i<=lans;i++)

		printf("%d",ans[i]);

	return 0;

}

巴特西

Codeforces Round #470 (rated, Div. 1, based on VK Cup 2018 Round 1) 923D 947D 948E D. Picking Strings

最新文章

热门文章