洛谷 P1709 隐藏口令
生活随笔
收集整理的這篇文章主要介紹了
洛谷 P1709 隐藏口令
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
題目描述
有時候程序員有很奇怪的方法來隱藏他們的口令。Binny會選擇一個字符串S(由N個小寫字母組成,5<=N<=5,000,000),然后他把S順時針繞成一個圈,每次取一個做開頭字母并順時針依次取字母而組成一個字符串。這樣將得到一些字符串,他把它們排序后取出第一個字符串。把這個字符串的第一個字母在原字符串中的位置-1做為口令。
如字符串alabala,按操作的到7個字符串,排序后得:
aalabal
abalaal
alaalab
alabala
balaala
laalaba
labalaa
第一個字符串為aalabal,這個a在原字符串位置為7,7-1=6,則6為口令。
輸入輸出格式
輸入格式:
第一行:一個數:N
第二行開始:字符串:S(每72個字符一個換行符)
輸出格式:
一行,為得到的口令
輸入輸出樣例
輸入樣例#1: 復制
7
anabana
輸出樣例#1: 復制
6
說明
題目滿足:
30%的數據n<=10000
70%的數據n<=100000
100%的數據n<=5000000
時限 1s
題目翻譯來自NOCOW。
USACO Training Section 5.5
//20170523新增數據四組
分析:
這道題很明顯是一個字符串最小表示的問題,在原先的博客中我也發過這個算法,主要是在處理字符串的時候要有特殊的技巧,因為數據量比較大,不能用常規的字符串進行接收。
代碼:
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner; public class Main {
public static void main(String args[]) throws IOException {
Scanner sc=new Scanner(System.in);
int num=sc.nextInt();
char[] c=new char[num];
String str;
int ll;
int now=0;
while(sc.hasNext()) {
str=sc.next();
ll=str.length();
for(int n=0;n<ll;++n)
c[now+n]=str.charAt(n);
now+=ll;
if(now==num)
break;
}
System.out.print(res(c,num));
}
public static int res(char[] c,int len) {
int i=0,j=1,k=0;
while(i<len&&j<len&&k<len) {
if(c[(i+k)%len]==c[(j+k)%len])
k++;
else if(c[(i+k)%len]<c[(j+k)%len]) {
j=j+k+1;
k=0;
}
else {
i=j;
j=i+1;
k=0;
}
}
return i;
}
}
總結
以上是生活随笔為你收集整理的洛谷 P1709 隐藏口令的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: web ch6 表单基础(部分选学)
- 下一篇: web 小程序 ch2 第一个小程序