4258216_wa.cpp

北大大牛代码 1240道题的原代码 超级权威

#include <stdio.h>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

bool cmp(string a, string b)
{
	return a.length() > b.length();
}

bool same(string a, string b)
{
	size_t i;
	int cnt = 0;
	vector <string> v;

	if (a.length() != b.length())
		return false;
	if (a[0] != '0' || b[0] != '0')
		return false;
	if (a[a.length() - 1] != b[b.length() - 1])
		return false;
	if (a == b)
		return true;
	v.clear();
	while (!a.empty())
	{
		for (i = 0; i < a.length(); i++)
		{
			if (a[i] == '0')
				cnt++;
			else
				cnt--;
			if (cnt == 0)
			{
				v.push_back(a.substr(0, i + 1));
				break;
			}
		}
		a = a.substr(i + 1);
	}
	sort(v.begin(), v.end(), cmp);
	bool update = true;
	while (update && !b.empty())
	{
		update = false;
		for (vector<string>::iterator j = v.begin(); j != v.end(); j++)
		{
			int len = j->length();
			if (b.find(*j) == 0 || same(j->substr(1, len - 2), b.substr(1, len - 2)))
			{
				update = true;
				b = b.substr(len);
				v.erase(j);
				break;
			}
		}
	}
	return update;
}

int main()
{
	int n;
	char tmp[3001];
	string a, b;

	scanf("%d", &n);
	while (n--)
	{
		scanf("%s", tmp);
		a = string(tmp);
		scanf("%s", tmp);
		b = string(tmp);
		puts(same(a, b) ? "same" : "different");
	}
	return 0;
}