首页 > 代码库 > [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
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。