hdu 4162 Shape Number (字符串的最小表示法)

hdu 4162

题意:给出一串代表8个方向的数字,求这串序列的一阶差分(the first difference)的字典序最小的表示。

思路:先做个变换,按照题意,第i位的一阶差分 s[i] = ((s[i+1]-s[i])+8)%8;

然后求出最小表示开始的位置。。输出即可。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2016年08月13日 星期六 02时17分45秒
 4File Name :code/poj/4162.cpp
 5************************************************ */
 6#include <cstdio>
 7#include <cstring>
 8#include <iostream>
 9#include <algorithm>
10#include <vector>
11#include <queue>
12#include <stack>
13#include <set>
14#include <map>
15#include <string>
16#include <cmath>
17#include <cstdlib>
18#include <deque>
19#include <ctime>
20#define fst first
21#define sec second
22#define lson l,m,rt<<1
23#define rson m+1,r,rt<<1|1
24#define ms(a,x) memset(a,x,sizeof(a))
25typedef long long LL;
26#define pi pair < int ,int >
27#define MP make_pair
28using namespace std;
29const double eps = 1E-8;
30const int dx4[4]={1,0,0,-1};
31const int dy4[4]={0,-1,1,0};
32const int inf = 0x3f3f3f3f;
33const int N=4E5+7;
34int n ;
35char s[N];
36int minRep(char *s)
37{
38    int n = strlen(s);
39    int i = 0 ;
40    int j = 1;
41    int k = 0 ;
42    while (i<n&&j<n&&k<n)
43    {
44	int t = s[(i+k)%n]-s[(j+k)%n];
45	if (t==0) k++;
46	else
47	{
48	    if (t>0)
49		i+=k+1;
50	    else j+=k+1;
51	    if (i==j) j++;
52	    k = 0 ;
53	}
54    }
55    return i<j?i:j;
56}
57int main()
58{
59	#ifndef  ONLINE_JUDGE 
60	freopen("code/in.txt","r",stdin);
61  #endif
62	while (~scanf("%s",s))
63	{
64	    int len = strlen(s);
65	    char s0 = s[0];
66	    int p,q;
67	    for ( int i = 0 ; i < len-1 ; i++)
68	    {
69		p = s[i]-'0';
70	        q = s[i+1]-'0';
71		q-=p;
72		if (q<0) q+=8;
73		s[i] = char (q+'0');
74	    }
75	    s[len-1] = char(((s0-s[len-1])+8)%8+'0');
76	    int k = minRep(s);
77	    int cnt = 1;
78	    for (int i = k ; cnt<= len ; i++,cnt++)
79		printf("%c",s[i%len]);
80	    printf("\n");
81	    ms(s,0);
82	}
83  #ifndef ONLINE_JUDGE  
84  fclose(stdin);
85  #endif
86    return 0;
87}