|
|
思路：
这题是暴力枚举，哈哈。
枚举每一种可能的字母分配情况。
然后再对每个单词求出按键序列以后，对按键序列进行 hash，用普通的字串hash函数即可。
最后就可以统计具有唯一按键序列的单词个数了。
这种做法还是相当快的，代码跑到了450ms 。是第一哦！
 #include <stdio.h>
#include <string.h>
#define MAX_D 1024
#define HASH_SIZE 65536
  struct node  {
 struct node *next;
int val, cnt;
 };
int B, L, D;
int map[256], ans[256], best;
char dict[MAX_D][16];
struct node nodes[MAX_D], *hash[HASH_SIZE];
int nodes_cnt;
int vis[HASH_SIZE], tm;
inline void calc()
{
int i, h, val, uni;
char *s;
struct node *t;
tm++;
nodes_cnt = 0;
  for (i = 0; i < D; i++) {
val = 0;
for (s = dict[i]; *s; s++)
val = val*31 + map[*s] + 'a';
h = val & (HASH_SIZE - 1);
if (vis[h] != tm) {
vis[h] = tm;
hash[h] = NULL;
 }
for (t = hash[h]; t; t = t->next)
if (t->val == val)
break;
if (!t) {
t = &nodes[nodes_cnt++];
t->val = val;
t->cnt = 0;
t->next = hash[h];
hash[h] = t;
}
t->cnt++;
}
uni = 0;
for (i = 0; i < nodes_cnt; i++)
if (nodes[i].cnt == 1)
uni++;
if (uni > best) {
best = uni;
memcpy(ans, map, sizeof(map));
}
}
void dfs(int b, int l)
{
int i, cnt;
cnt = L - l - (B - b) + 1;
for (i = 0; i < cnt; i++)
map[l + 'A' + i] = b;
if (b == B - 1) {
calc();
return ;
}
for (i = cnt; i >= 1; i--)
dfs(b + 1, l + i);
}
int main()
{
int i;
freopen("e:\\test\\in.txt", "r", stdin);
scanf("%d%d%d", &B, &L, &D);
for (i = 0; i < D; i++)
scanf("%s", dict[i]);
dfs(0, 0);
printf("%d\n", best);
for (i = 'A'; i < 'A' + L; i++) {
if (ans[i] != ans[i - 1])
putchar('\n');
putchar(i);
}
putchar('\n');
return 0;
}
|