codeforces 559B – Equivalent Strings(最小表示法)

Equivalent Strings

【题意】给出两个字符串,确定,是否相等,定义字符串是否相等为,如果为奇数串,只能比较是否每个字符相同,如果为偶数串,第一个串分成两个相等长度的串为a1 b1,第二个串也分成a2 b2,a1== a2 && b1 == b2 || a1 == b2 && a2 == b2.

【分析】类似树上的最小表示法,和字符串的最小表示是不同的,每次偶数个合并时比较大小,找出最小表示,字符串ab最小表示是否相同,复杂度N*logN。还可以暴力,按照Q神的方法可以达到31ms。但还是感觉最小表示复杂度稳定点。

【AC CODE(最小表示)】202ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 200000+10;
char a[MAXN],b[MAXN];

string dfs(char *s, int x, int y)
{
	if((y-x+1)&1)
	{
		string ans = "";
		repe(i,x,y) ans += s[i];
		return ans;
	}
	int m = (x+y)>>1;
	string l = dfs(s,x,m),r = dfs(s,m+1,y);
	return l<r?l+r:r+l;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	scanf("%s%s",a,b);
	int len = strlen(a);
	if(dfs(a,0,len-1) == dfs(b,0,len-1)) puts("YES");
	else puts("NO");
	return 0;
}

【暴力剪枝】31ms

#include <cstdio>
#include <cstring>
#include <cctype>
#include <cmath>
#include <set>
//#include <unordered_set>
#include <queue>
#include <stack>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;
typedef long long LL;
#define rep(i,a,n) for(int i = a; i < n; i++)
#define repe(i,a,n) for(int i = a; i <= n; i++)
#define per(i,n,a) for(int i = n; i >= a; i--)
#define clc(a,b) memset(a,b,sizeof(a))
const int INF = 0x3f3f3f3f, MAXN = 200000+10;
char a[MAXN],b[MAXN];

bool dfs(int x1, int y1, int x2, int y2)
{
	int len = y1-x1+1;
	if(!strncmp(a+x1,b+x2,len)) return true;
	if(len&1) return false;
	int m1 = (x1+y1)>>1, m2 = (x2+y2)>>1;
	if(dfs(x1,m1,m2+1,y2)) return dfs(m1+1,y1,x2,m2);
	else return dfs(x1,m1,x2,m2) && dfs(m1+1,y1,m2+1,y2);
	return false;
}
int main()
{
#ifdef SHY
	freopen("d:\\1.txt", "r", stdin);
#endif
	scanf("%s%s", a,b);
	int len = strlen(a);
	if(dfs(0,len-1,0,len-1)) puts("YES");
	else puts("NO");
	return 0;
}

 

发表评论

邮箱地址不会被公开。 必填项已用*标注

请输入正确的验证码