首页 > 代码库 > HDU 4850 Wow! Such String!(欧拉道路)

HDU 4850 Wow! Such String!(欧拉道路)

HDU 4850 Wow! Such String!

题目链接

题意:求50W内的字符串,要求长度大于等于4的子串,只出现一次

思路:需要推理,考虑4个字母的字符串,一共有26^4种,这些由这些字符串,如果一个字符串末尾加上一个字符,可以变成另一个字符串的话,就当作这有一条边,每多一个字符多一个结点,那么对于这道题目,一共就能有26^4 + 3条边,在加上尾巴可以多放3个,一共是26^4+3个边,这些边全部连起来就是要的字符串,这样就可以知道每个节点会经过的次数为26,这样就只要考虑如何把这些节点串起来,形成一个欧拉道路即可,这样情况是最大的,选一个起始点aaa,不断往后走,每次选择被占用最少的节点去走,边都标记掉,然后要有一个注意点,就是由于是从aaa开始走,最后必须回到aaa,所以要让选择a这条边的优先级变成最小,不然如果先被占用了就无法构成了

代码:

#include <cstdio>
#include <cstring>

const int N = 20005;
int vis[N], vis2[N][30], on = 0;
char out[500005];

int getnext(int x, int a) {
    return x % (26 * 26) * 26 + a;
}

void init() {
    int now = 0;
    for (int i = 0; i < 3; i++)
	out[on++] = 'a';
    while (true) {
	int Min = 26, iv = 0;
	for (int i = 1; i < 26; i++) {
	    if (vis2[now][i]) continue;
	    int tmp = getnext(now, i);
	    if (vis[tmp] < Min) {
		Min = vis[tmp];
		iv = i;
	    }
	}
	int tmp = getnext(now, iv);
	if (vis[tmp] == 26) break;
	vis2[now][iv] = 1;
	now = tmp;
	vis[now]++;
	out[on++] = now % 26 + 'a';
    }
}

int n;

int main() {
    init();
    while (~scanf("%d", &n)) {
	if (n > 456979) printf("Impossible\n");
	else printf("%s\n", (out + 456979 - n));
    }
    return 0;
}