1550: AA

Time Limit:?1 Sec??Memory Limit:?128 MB
Submit:?88??Solved:?26
[Submit][Status][Web Board]

Description

?其實第一次聽說要出題目我是拒絕的，因為，你不能讓我出，我就馬上去出，我要試一下，因為我不愿意出完了以后再加一些案例上去，然后題目duang的一下就被AC了。現在要求對字符串進行環狀左移操作，每次向左移動一個位置。例如：對duang進行操作，得到的全部字符串為：

duang

uangd

angdu

ngdua

gduan

輸出得到最小字典序的字符串的最小移動次數。

Input

輸入一個數T(1<=T<=100),表示接下來有T行字符串；輸入字符串S，S的長度為L（5<=l<=100000）。

Output

輸出一個數字，表示為得到最小字典序的字符串的最小移動次數。

Sample Input

2 baabaa alabala

Sample Output

1 6
【解析】 這道題我提交了好多次都是超時...但是呢我覺得做題目嘛主要是學東西..我是用map，結構體還有用劉汝佳老師書上的方法也試了一下還是超時...此處附上我的超時代碼...其實有的時候我們不能真的為了AC而去AC。還可以直接比較..還有就是當我們用map<string,int>的時候是按照string的最小字典序來排列的所以我們也可以用map#include<cstdio> #include<algorithm> #include<iostream> #include<map> #include<cstring> using namespace std; struct E {string zi;//結構體存儲int b; }; bool cmp(E a,E b) {return (a.zi).compare(b.zi)<0;//兩個字符串進行比較,字典序小的排在前面 } int main() {int t,n,i,j,k,p;string s,s1;scanf("%d",&t);while(t--){p=0;E f[100010];cin>>s;f[p].zi=s;f[p].b=0;n=s.size();for(i=1;i<=n;i++){string s1;for(j=i;j<n;j++){s1+=s[j];}for(k=0;k<i;k++){s1=s1+s[k];//獲取移動的字符串}p++;f[p].zi=s1;f[p].b=i;}sort(f,f+p,cmp);//根據字典序來排序cout<<f[0].b<<endl;}return 0; }#include<cstdio> #include<algorithm> #include<iostream> #include<map> #include<cstring> using namespace std; int main() {int t,n,i,k;string s,s1,s3;scanf("%d",&t);while(t--){cin>>s;s3=s;k=0;n=s.size();for(i=1;i<=n;i++){string s1,s2;s1=s.substr(i,n-i);s2=s.substr(0,i);s1=s1+s2;if(s3.compare(s1)>0)//此函數用來比較字典序{s3=s1;k=i;}}printf("%d\n",k);}return 0; }#include<cstdio> #include<algorithm> #include<iostream> #include<map> #include<cstring> using namespace std; map<string,int>a; int main() {int t,n,i;string s,s1;scanf("%d",&t);while(t--){a.clear();cin>>s;a[s]=0;n=s.size();for(i=1;i<=n;i++){string s1,s2;s1=s.substr(i,n-i);s2=s.substr(0,i);//獲取字符串從0開始取i個s1=s1+s2;if(a[s1]==0)a[s1]=i;}map<string,int>::iterator it=a.begin();//map<string,int>是按照最小字典序來排列的cout<<it->second<<endl;}return 0; }#include<stdio.h> #include<string.h> #define maxn 100010 int less(char s[],int p,int q) {int n=strlen(s);int i;for(i=0;i<n;i++){if(s[(p+i)%n]!=s[(q+i)%n])return s[(p+i)%n]<s[(q+i)%n];}return 0; } int main() {int t,ans,n,i;char s[maxn];scanf("%d",&t);while(t--){scanf("%s",s);ans=0;n=strlen(s);for(i=1;i<n;i++){if(less(s,i,ans))ans=i;}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的ZCMU-1550-AA的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。