首页 > 代码库 > [USACO5.5]隐藏口令Hidden Password

[USACO5.5]隐藏口令Hidden Password

题目链接:传送门

题目大意:给你一个长度 N 的字符串,5<=N<=5,000,000,将首尾合并成环,断环成链并满足字典序最小,输出此时首字母在原串中的位置-1;

题目思路:最小表示法

#include <iostream>#include <cstdio>#include <cstdlib>#include <cmath>#include <algorithm>#include <cstring>#include <stack>#include <cctype>#include <queue>#include <string>#include <vector>#include <set>#include <map>#include <climits>#define lson rt<<1,l,mid#define rson rt<<1|1,mid+1,r#define fi first#define se second#define ping(x,y) ((x-y)*(x-y))#define mst(x,y) memset(x,y,sizeof(x))#define mcp(x,y) memcpy(x,y,sizeof(y))using namespace std;#define gamma 0.5772156649015328606065120#define MOD 1000000007#define inf 0x3f3f3f3f#define N 100005#define maxn 5000005typedef pair<int,int> PII;typedef long long LL;int n,m,cnt,S,T,k;char ch[100];char str[maxn<<1],str1[maxn<<1];int main(){    //freopen("in.txt","r",stdin);    int i,j,Case=0,x,y;    scanf("%d",&n);    i=0;    while(scanf("%s",str+i)!=EOF)i+=72;    strcpy(str1,str);    strcat(str,str1);    i=0,j=1;    while(i<n&&j<n){        k=0;        while(k<n&&str[i+k]==str[j+k])++k;        if(k==n)break;        if(str[i+k]>str[j+k])i+=k+1;        else j+=k+1;        if(j<=i)j=i+1;    }    printf("%d\n",i);    return 0;}

 

[USACO5.5]隐藏口令Hidden Password