洛谷-UVA1584 环状序列 Circular Sequence

逃离我推掉我的手 2023-06-13 09:59 181阅读 0赞

## 题目描述 ##

[PDF][]

## 输入格式 ##

无

## 输出格式 ##

无

## 题意翻译 ##

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

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

## 输入输出样例 ##

无

方法一：用C++ 字符串自动比较大小

#include <bits/stdc++.h>
    using namespace std;
    int main(){
    	int n;
    	cin>>n;
    	string s;
    	while(n--){
    		cin>>s;
    		int len=s.size();
    		string minS=s; //初始化最小串 
    		s=s+s;//处理环状 
    		for(int i=1;i<len;i++){//例如： 1(可省略，可不省略) 2 3 4 1 2 3 4 
    			string cs=s.substr(i,len);
    			if(cs<minS){//比较字符串大小 
    				minS=cs;
    			} 
    		}
    		cout<<minS<<endl;
    	}
    	return 0;
    }

方法二：自己比较大小

#include <bits/stdc++.h>
    using namespace std;
    int main(){
    	int n;
    	cin>>n;
    	string s;
    	while(n--){
    		cin>>s;
    		int len=s.size();
    		string minS=s; //初始化最小串
    		int minLocal=0;
    		s=s+s;//处理环状 
    		for(int i=1;i<len;i++){//例如： 1(可省略，可不省略) 2 3 4 1 2 3 4 
    			for(int j=0;j<len;j++){//挨个比较大小 
    				if(s[i+j]!=s[minLocal+j]){
    					if(s[i+j]<s[minLocal+j]){
    						minLocal=i;
    						break;
    					}					
    			}
    		}
    		minS=s.substr(minLocal,len);
    		cout<<minS<<endl;
    	}
    	return 0;
    }

[PDF]: https://uva.onlinejudge.org/external/15/p1584.pdf

发表评论取消回复

表情：

评论列表（有 0 条评论，181人围观）

还没有评论，来说两句吧...

相关阅读

相关洛谷-UVA1584 环状序列 Circular Sequence

题目描述 [PDF][] 输入格式无输出格式无题意翻译长度为nn 的环状串有nn 种表示法，分别为从某个位置开始顺时针得到的。在环状串的

逃离我推掉我的手/ 2023年06月13日 09:59/ 0 赞/ 182 阅读

相关洛谷-UVA11988 损坏的键盘

题目描述 [PDF][] ![format_png][] 输入格式 ![format_png 1][] 输出格式 ![format_png 2][]

不念不忘少年蓝@/ 2023年05月31日 10:25/ 0 赞/ 140 阅读

相关洛谷-UVA101 The Blocks Problem

输入格式 ![format_png][] 输出格式 ![format_png 1][] 题意翻译初始时从左到右有n个木块，编号为0~n-1,要求实现下列

爱被打了一巴掌/ 2023年05月31日 03:11/ 0 赞/ 126 阅读

相关洛谷-UVA514 铁轨 Rails

题目描述 [PDF][] ![format_png][] 输入格式 ![format_png 1][] 输出格式 ![format_png 2][]

我会带着你远行/ 2023年05月29日 06:43/ 0 赞/ 152 阅读

相关环状序列（Circular Sequence)

输入一个长度为n（n<=100)的环状DNA串（只包含A,C,G,T这4种字符）的一种表示法，锂的任务是输出该环状串的最小表示（字典序最小）。例如：CTCC的最小表示为CCCT

╰+哭是因爲堅強的太久メ/ 2023年03月04日 13:27/ 0 赞/ 36 阅读

相关环状序列(Circular Sequence,ACM/ICPC Seoul 2004,UVa1584)题解

文章目录题目描述输入输出原题（PDF）题目分析案例分析解题标程

浅浅的花香味﹌/ 2022年12月28日 04:24/ 0 赞/ 367 阅读

相关 D - Circular Sequence

Some DNA sequences exist in circular forms as in the following figure, which shows a cir

た入场券/ 2022年10月01日 04:51/ 0 赞/ 150 阅读

相关 F - Circular Sequence

think: 1字符串元素移位+字符串字典序比较 [vjudge题目链接][vjudge] 以下为Accepted代码 include <bits/stdc+

水深无声/ 2022年06月18日 09:36/ 0 赞/ 343 阅读

相关环状序列

前言没什么好说的了，哈哈，现在快凌晨一点了，为了晚上睡觉不梦见做题，把这个问题还是解决了环状序列问题描述长度为n的环状串有n种表示法，分别为某个位置开始顺时

￡神魔★判官ぃ/ 2022年05月28日 03:49/ 0 赞/ 327 阅读

相关洛谷题解UVA524 素数环

一、题目 [https://www.luogu.org/problemnew/show/UVA524][https_www.luogu.org_problemnew_sh

淡淡的烟草味﹌/ 2022年02月27日 13:26/ 0 赞/ 413 阅读