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

浅浅的花香味﹌ 2022-12-28 04:24 255阅读 0赞

### 文章目录 ###

*  题目描述
 *   *  输入
     *  输出
 *  原题（PDF）
 *   *  题目分析
     *  案例分析
     *  解题标程
     *  错题总结

--------------------

# 题目描述 #

长度为 n 的环状串有 n 种表示法，分别为从某个位置开始顺时针得到的。在环状串的所有表示法中，字典序最小的称为“最小表示”。  
输入一个长度为 n 的环状DNA串（只包含A ，C ，G ，T 这四种字符）的一种表示法，你的任务是输出该环状串的最小表示。

## 输入 ##

2  
    CGAGTCAGCT  
    CTCC

## 输出 ##

AGCTCGAGTC  
    CCCT

--------------------

# 原题（PDF） #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]

--------------------

## 题目分析 ##

**字典序最小**，可认为**要求第i位的字符为当前可选的第i位的字符中最小的**。

## 案例分析 ##

例如案例中 CGAGTCAGCT  
第一位最小字符为：A ，因此从两个 A 可能的字符开始组成字符串  
第二位最小字符比较：G与G  
第三位最小字符比较：T与C ， 因此可知AGC当前字符为“最小表示”

## 解题标程 ##

#include <stdio.h>
    #include <string.h>
    #define maxn 105
    
    //自定义一个在字符串不同位置开始，来比较后续组成的字符串的字典序大小
    int less(const char *s,int p,int q)
    {
        
      int n=strlen(s);
      for(int i=0;i<n;i++)
        if(s[(p+i)%n]!=s[(q+i)%n])    // %n 处理下标溢出
          return s[(p+i)%n] < s[(q+i)%n]; //当字符不同时，返回比较结果
      return 0;     //字符串相同，返回 0
    }
    
    int main()
    {
        
      int t,n;
      scanf("%d",&t);
      
      while(t--){
        
        scanf("%s",s);
        n=strlen(s);
        
        int ans=0;        //用于记录从 ans 位置开始的字符串字典序最小
        for(int i=1;i<n;i++)
          if(less(s,i,ans)) ans=i;  //不断比较，以求得最小 ans 位置
    
        //输出从 ans 位置开始的字符串
        for(int i=0;i<n;i++)
          putchar(s[(ans+i)%n]);
        putchar('\n');
      }
      return 0;
    }

## 错题总结 ##

*  1、*用字符串字典顺序的总和数值判断是否为最小不合理*，**因为无法判断当前位置是否为此刻最小**
 *  2、采用结构化编程，将比较过程写成自定义比较函数，**遍历所有可能的字符串起始位置进行比较**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzg0NTk1Ng_size_16_color_FFFFFF_t_70]: /images/20221120/b6b36ffe52514b978e12efd758b18777.png