poj 1509 Glass Beads (字符串的最小表示法)
poj 1509 题目链接
题意&思路：同uva 1314
1/* *********************************************** 2Author :111qqz 3Created Time :2016年08月12日 星期五 18时48分29秒 4File Name :code/uva/1314.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=1E5+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 int T; 63 cin>>T; 64 while (T--) 65 { 66 scanf("%s",s); 67 printf("%d\n",minRep(s)+1); 68 } 69 #ifndef ONLINE_JUDGE 70 fclose(stdin); 71 #endif 72 return 0; 73}