欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVa 1584 - Circular Sequence

程序员文章站 2022-07-12 16:40:31
...

题意

环形DNA
找到一个序列使得该链状DNA字典序最小

思路

水题
枚举开始节点
每次更新最小字典序的枚举点即可

AC代码

#include <cstdio>
#include <cstring>

using namespace std;

const int maxn = 100 + 50;
char s[maxn];

struct dic{
    int m[maxn];
    int st;
};
struct dic p[maxn];

int main()
{
    int T, len, i, j, k;
    int mrk;
    scanf("%d",&T);
    while(T--){
        scanf("%s",s);
        len = strlen(s);
        mrk = 0;
        for( i = 0; i < len; i++ )
            p[0].m[i] = s[i];
        for( i = 1; i < len; i++ ){
            k = 0;
            for( j = i; j < len; j++ ){
                p[i].m[k] = s[j];
                k++;
            }
            for( j = 0; j < i; j++ ){
                p[i].m[k] = s[j];
                k++;
            }
            for( k = 0; k < len; k++ ){
                if( p[i].m[k] == p[mrk].m[k] )
                    continue;
                else if( p[i].m[k] < p[mrk].m[k] ){
                    mrk = i;
                    break;
                }
                else    break;
            }
        }
        for( int i = 0; i < len; i++ )
            printf("%c",(char)p[mrk].m[i]);
        puts("");
    }
    return 0;
}
相关标签: uva 枚举