3981451_ac_297ms_8100k.cpp

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

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

using namespace std;

char digit[] = "57630499617851881234762239";

struct node
{
	int len;
	char str[51], dic[51];

	bool operator < (const node &t)	const
	{
		return strcmp(str, t.str) < 0;
	}

	void getDigit()
	{
		int i;
		char ch;

		len = 0;
		for (i = 0; dic[i]; i++)
		{
			ch = dic[i];
			if (!isalpha(ch))
				continue;
			ch = tolower(ch);
			str[len++] = digit[ch-'a'];
		}
		str[len] = '\0';
	}
}num[75000];

__int64 can[51];

typedef vector <int> VI;
typedef vector <VI> VVI;

VVI getans(int l)
{
	VVI ret, tmp;
	int i, j;

	if (l == 0)
	{
		VI vi;
		vi.push_back(0);
		VVI vvi;
		vvi.push_back(vi);
		return vvi;
	}
	for (i = 0; i < l; i++)
	{
		if (can[l] & ((__int64)1 << i))
		{
			tmp = getans(i);
			for (j = 0; j < tmp.size(); j++)
			{
				tmp[j].push_back(l);
				ret.push_back(tmp[j]);
			}
		}
	}
	return ret;
}

int n;

void change(char str[], int &l)
{
	int i, j;

	for (j = 0, i = 0; str[i]; i++)
	{
		if (isdigit(str[i]))
		{
			str[j++] = str[i];
		}
	}
	str[j] = '\0';
	l = j;
}

int find(char str[])
{
	int min, max, mid;

	min = 0;max = n;
	while (min < max)
	{
		mid = (min + max) >> 1;
		int v = strcmp(str, num[mid].str);
		if (v == 0)
			return 1;
		if (v > 0)
			min = mid + 1;
		else
			max = mid;
	}
	return 0;
}

int getlower(char str[])
{
	int min, max, mid;

	min = 0;max = n;
	while (min < max)
	{
		mid = (min + max) >> 1;
		int v = strcmp(str, num[mid].str);
		if (v > 0)
			min = mid + 1;
		else
			max = mid;
	}
	return min;
}

int main()
{
	int cas, now;
	int i, j, m, l, k, f;
	char no[51];
	char tmp[51], bak[51];
	vector <string> all, tmpstr, tmpans;
	set <string> tot;
	VVI ans;

	scanf("%d", &cas);
	for (now = 1; now <= cas; now++, puts(""))
	{
		tot.clear();
		printf("Scenario #%d:\n", now);
		scanf("%d", &n);
		for (i = 0; i < n; i++)
		{
			scanf("%s", num[i].dic);
			num[i].getDigit();
		}
		sort(num, num + n);
		scanf("%d", &m);
		can[0] = 0;
		while (m--)
		{
			ans.clear();
			tot.clear();
			scanf("%s", no);
			strcpy(bak, no);
			change(no, l);
			for (i = 1; i <= l; i++)
			{
				can[i] = 0;
				strncpy(tmp, no, i);
				tmp[i] = '\0';
				for (j = 0; j < i; j++)
				{
					if ((j == 0 || can[j] != 0) && find(&tmp[j]))
					{
						can[i] |= ((__int64)1 << j);
					}
				}
			}
			if (can[l] == 0)
			{
				printf("%s cannot be encoded.\n", bak);
				continue;
			}
			ans = getans(l);
			for (i = 0; i < ans.size(); i++)
			{
				all.clear();
				for (j = 1; j < ans[i].size(); j++)
				{
					tmpstr.clear();
					int st = ans[i][j - 1];
					int len = ans[i][j] - ans[i][j - 1];
					int lower;
					strncpy(tmp, &no[st], len);
					tmp[len] = '\0';
					lower = getlower(tmp);
					while (lower < n && strcmp(num[lower].str, tmp) == 0)
					{
						tmpstr.push_back(" " + string(num[lower++].dic));
					}
					tmpans = all;
					if (all.size() == 0)
					{
						for (k = 0; k < tmpstr.size(); k++)
						{
							all.push_back(tmpstr[k]);
						}
						continue;
					}
					all.clear();
					for (k = 0; k < tmpans.size(); k++)
					{
						for (f = 0; f < tmpstr.size(); f++)
						{
							all.push_back(tmpans[k] + tmpstr[f]);
						}
					}
				}
				for (j = 0; j < all.size(); j++)
				{
					tot.insert(all[j]);
				}
			}
			for (set<string>::iterator s = tot.begin(); s != tot.end(); ++s)
			{
				printf("%s:%s\n", bak, (*s).c_str());
			}
		}
	}
	return 0;
}