#include<cmath>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;

/* POJ 3188 */

const int N = 1024;
const int MOD = 10000007;

int n, m, k;
int dic[N][15];
int bestAns, ans[30];
int map[30], vis[MOD], tim = 0;

char in[1000000], *p = in;

inline int nextInt(void) {

	int res = 0;

	while (*p < '0' || *p > '9')p++;

	while (*p >= '0'&&*p <= '9')
		res = res * 10 + *p++ - '0';

	return res;

}

inline void readString(int id) {

	while (*p<'A' || *p>'Z')p++;

	while (*p >= 'A'&&*p <= 'Z')
		dic[id][++dic[id][0]] = *p++ - 'A';

}

inline void checkAns(void) {

	int tmp = 0, cnt = 0; tim++;
	for (int i = 1; i <= k; i++, tmp = 0) {
		for (int j = 1; j <= dic[i][0]; j++) {
			tmp = tmp * 31 + map[dic[i][j]];
			if (tmp >= MOD)tmp %= MOD;
		}
		if (abs(vis[tmp]) != tim)cnt++, vis[tmp] = tim;
		else if (vis[tmp] == tim)cnt--, vis[tmp] = -tim;
	}

	if (cnt > bestAns)
		memcpy(ans, map, sizeof(ans)), bestAns = cnt;

}

inline void dfs(int x, int y) {

	if (bestAns >= k)return;

	if (y == n) {
		for (int i = x; i < m; i++)map[i] = y;
		checkAns();
	} 
	else {
		for (int i = x; m - i > n - y; i++)map[i] = y;
		for (int i = m - n + y; i > x; i--)dfs(i, y + 1);
	}

}

signed main(void) {

	fread(p, 1, 1000000, stdin);
	
	/* input */ {
		n = nextInt();
		m = nextInt();
		k = nextInt();
		for (int i = 1; i <= k; i++)
			readString(i);
	}

	/* solve */ {
		bestAns = 0; dfs(0, 1);
		printf("%d\n", bestAns);
		for (int i = 1, j = 0; i <= n; i++, puts(""))
			while (j < m && ans[j] == i)putchar('A' + j++);
	}

#ifndef ONLINE_JUDGE
	system("pause");
#endif // !ONLINE_JUDGE

}

• 分享Github上的代码， 努力打榜 (66) youshiki 2016-08-29 11:34:37