首页 > 代码库 > hdu 4850 Wow! Such String!

hdu 4850 Wow! Such String!

2024-07-16 13:14:23   221人阅读

这是当时西安邀请赛的题目，也就是因为这道题，我们无缘银牌。。。

其实这道题的大致想法当时我想出来了，就是我是想找到一条通过所有顶点的通路，顶点是所有的长度是4的子串。但是当时没有尝试搜索，以为不会这么简单就找到那条路。但是现在明白了，对于所有顶点度数为偶数的图，一定可以找到这样一条路的。

下面是代码

#include <iostream>#include <cstdio>#include <cstring>using namespace std;const int mod = 26*26*26;const int maxn = 26*26*26*26;bool v[mod][30];int used[maxn + 10];char s[maxn + 10];int num = 0;int get_next(int a, int x){    a %= mod;    a *= 26;    a += x;    return a;}int get_x(int a){    a %= mod;    int ret = 0, t = a;    for(int i = 0; i < 26; i++)    {        if(v[a][i])        continue;        if(ret == 0 || used[t] > used[a * 26 + i])        t = a * 26 + i, ret = i;    }    v[a][ret] = 1;    return ret;}void init(){    int a = 0;     num = 3;    for(int i = 0; i < 3; i++)    s[i] = ‘a‘;    while(1)    {        int x = get_x(a);        a = get_next(a, x);        if(used[a])        return;        used[a] = 1;        s[num++] = ‘a‘ + x;    }}int main(){    init();    //cout << num << endl;    int n;    while(scanf("%d", &n) == 1)    {        if(n > num)        printf("Impossible");        else        for(int i = 0; i < n; i++)        printf("%c",s[i]);        printf("\n");    }}
View Code

 


联系
我们