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;

}