学步园

题意：8个方向，分别用0、1、2、3、4、5、6、7表示，用这些数字连成一个串就可表示一个回路图，方向2转到方向4要转2次，方向6转到方向4也要2次，给出一个回路图，求出字典序最小的转向串。

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3745

                    http://acm.hdu.edu.cn/showproblem.php?pid=4162

——>>比赛时被吓了，有队伍从971B写到5110B再到2454B才过，我们试了900多B的总超时，难道要用特别的数据结构，纠结时比赛结束……今天找找方法，发现不用什么特别的数据结构，也没用写那么长……

先求出一个串，并且记录ASCII最小的字符到minn，然后让其翻倍加长自身，这样从任一点开始都可以扫到原长度的串；接着，扫描每个位置，碰到minn开头的才与现有串比较（先扫到第一个符合条件的位置作为现在串的起始点再进行普遍扫描）。

 

#include <iostream>
#include <string>

using namespace std;

int main()
{
    int i;
    string a, ret;
    while(cin>>a)
    {
        int len = a.length();
        a += a[0];
        ret = "";
        char minn = '9', c;
        for(i = 1; i <= len; i++)       //求一结果串
        {
            c = (char)((a[i]-a[i-1]+8) % 8 + '0');
            ret += c;
            if(c < minn) minn = c;
        }
        ret = ret + ret;
        int start;      //起点
        for(i = 0; i < len; i++)        //先找第一个可能的起始点
            if(ret[i] == minn)
            {
                start = i;
                break;
            }
        for(++i; i < len; i++)      //接着扫
        {
            if(ret[i] == minn)
            {
                for(int j = 0; j < len; j++)
                    if(ret[i+j] < ret[start+j])
                    {
                        start = i;
                        break;
                    }
                    else if(ret[i+j] > ret[start+j]) break;
                while(i+1 < len && ret[i+1] == minn) i++;
            }
        }
        for(i = start; i < start+len; i++)
            cout<<ret[i];
        cout<<endl;
    }
    return 0;
}