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

UVA1584 环状序列 Circular Sequence

程序员文章站 2022-06-09 20:26:19
...

题意翻译

长度为nn 的环状串有nn 种表示法,分别为从某个位置开始顺时针得到的。在环状串的所有表示法中,字典序最小的称为“最小表示”。

输入一个长度为nn 的环状DNA串(只包含AA ,CC ,GG ,TT 这四种字符)的一种表示法,你的任务是输出该环状串的最小表示。

输入输出如下图:

洛谷链接
UVA1584 环状序列 Circular Sequence

代码如下:
1、数组

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<iostream>
#include<cstdio>
using namespace std;
#pragma warning(disable:4996)
#pragma warning(disable:6031)
#define maxn 105

int lessa(const char* s,int p,int q)
{
	int n = strlen(s);//字符串长度
	//第二层循环,根据所给的原起始位置,
	//如1,2,3等,一个个与更新的起始位置ans比对,决定是否更新ans,取得新起始位
	for (int i=0;i<n;i++)
	{
		if (s[(p+i)%n]!=s[(q+i)%n])//循环对比
		{
			return s[(p + i) % n] < s[(q + i) % n];
			//如果既定开始的字符串比ans开始的小,返回1,更新位置ans
		}
	}
	return 0;
}

int main()
{
	int t;
	char s[maxn];
	scanf("%d",&t);
	while (t--)
	{
		scanf("%s",s);
		int ans = 0;//起始位置
		int n = strlen(s);//字符串长度
		for (int i=1;i<n;i++)//第一重循环,获取第二层循环的结果,取得起始位置
		{
			if (lessa(s, i, ans))//判断
			{
				ans = i;//更新位置
			}
		}
		for (int i=0;i<n;i++)//输出
		{
			putchar(s[(ans+i)%n]);
		}
		putchar('\n');
	}
	return 0;

}

2、字符串
来源:https://www.luogu.com.cn/blog/sss7020/solution-uva1584

#include<iostream>
#include<string>
#include<algorithm>
//sort必备
using namespace std;
int main(){
    string s;
    int kase,k;
    cin>>kase;
    while(kase--){//循环开始了
        cin>>s;//输入字符串
        string st[105];
        //为节省空间,系统将string类默认为空串
        for(k=0;k<s.length();k++){
            //k是代表从哪个字符开始读
            for(int i=k;i<k+s.length()/*循环s.lenth()次*/;i++){
                st[k]+=s[i%s.length()];
                //字符串往后填几个字符串
                //+运算符的用法:
                //看我题解:
                //https://www.luogu.org/blog/winnerking1412/solution-uva455
            }
        }
        sort(st,st+s.length());
        //排序
        cout<<st[0]<<endl;//输出第一个字符串
    }
    return 0;
}

3、substr
来源:https://www.luogu.com.cn/blog/52rsj/solution-uva1584

#include <iostream>
#include <string>
using namespace std;
int main(){
    int i,j,k,m,n;
    string s;
    cin>>n;
    for(i=1;i<=n;i++){
        cin>>s;
        string ans=s;
        for(j=0;j<s.length();j++){
            string t;
            t=s.substr(j,s.length()-j)+s.substr(0,j);//这是重点
            if(t<ans)ans=t;
        }
        cout<<ans<<endl;
    }
} 

substr(x,y)从x开始,截取y个,x起始为0

相关标签: ACM