怪盗基德的挑战书
Time Limit: 3000/1000 MS (Java/Others) Memory Limit: 65535/32768 K (Java/Others)Total Submission(s): 414 Accepted Submission(s): 187
Problem Description
“在树最美丽的那天,当时间老人再次把大钟平均分开时,我会降临在灯火之城的金字塔前,带走那最珍贵的笑容。”这是怪盗基德盗取巴黎卢浮宫的《蒙娜丽莎的微笑》这幅画时,挑战书上的内容。 但这次,怪盗基德的挑战书上出现了一串串小写字母“aaab sdfeeddd...”。柯南以小学生的眼睛,超凡高中生的头脑,快速统计各种字母频率,字符串长度,并结合挑战书出现的时间等信息,试图分析怪盗基德的意图。最后,他将线索锁定在字符串的循环次数上。并且进一步推理发现,从字符串的第一位开始,到第i位,形成该字符串的子串(c1, c2, c3 ... ci )。对于某一子串ci在该字符串中出现的次数记为ki,则全部子串的循环次数总和AIM = k1 + k2 + ... + ki + ... + kn,柯南发现,AIM恰好对应一个ASCII码!所以,只要把挑战书上的字符串转变成数字,再找到对应的ASCII码,就可以破解这份挑战书了! 现在,你的任务就是把字符串转变成对应数字,因为ASCII码以及扩展ASCII码全部只有256个,所以,本题只要把结果对256取余即可。
Input
输入有多组测试数据;每组测试数据只有一个字符串,由各种小写字母组成,中间无空格。字符串的长度为L(0 < L <= 100000)。
Output
请计算并输出字符串的AIM值,每组数据输出一行。
Sample Input
aaa abab
Sample Output
6 6
Source
Recommend
liuyiding
题目的数据很水所以很多人用暴力都过了而且时间还是0MS
其实可以用后缀数组来做:
题目的思路就是:拿所有的后缀来和最长的后缀(rank[0])比较把之间的最长公共前缀的长度相加就是答案!!!!!
下面的就是LCP问题了。。。。
得记住LCP问题!!!!!!!!!!!!!!!!!!!!!!
我自己用RMQ写了一下。。。。。
AC代码:
#include <stdio.h> #include <string.h> #include <algorithm> #include <math.h> #include <stdlib.h> #define INF 10000000 using namespace std; #include <stdio.h> #include <string.h> /* 待排序的字符串放在r 数组中,从r[0]到r[n-1],长度为n,且最大值小 于m。为了函数操作的方便,约定除r[n-1]外所有的r[i]都大于0, r[n-1]=0。 函数结束后,结果放在sa 数组中,从sa[0]到sa[n-1]。 */ const int MAX=100010; int wa[MAX],wb[MAX],wv[MAX],ws[MAX]; int sa[MAX]; int cmp(int *r,int a,int b,int l) { return r[a]==r[b]&&r[a+l]==r[b+l]; } void da(char *r,int *sa,int n,int m)//注意此处的char*r有时可以改成int* r { int i,j,p,*x=wa,*y=wb,*t; for(i=0;i<m;i++) ws[i]=0; for(i=0;i<n;i++) ws[x[i]=r[i]]++; for(i=1;i<m;i++) ws[i]+=ws[i-1]; for(i=n-1;i>=0;i--) sa[--ws[x[i]]]=i; for(j=1,p=1;p<n;j<<=1,m=p) { for(p=0,i=n-j;i<n;i++) y[p++]=i; for(i=0;i<n;i++) if(sa[i]>=j) y[p++]=sa[i]-j; for(i=0;i<n;i++) wv[i]=x[y[i]]; for(i=0;i<m;i++) ws[i]=0; for(i=0;i<n;i++) ws[wv[i]]++; for(i=1;i<m;i++) ws[i]+=ws[i-1]; for(i=n-1;i>=0;i--) sa[--ws[wv[i]]]=y[i]; for(t=x,x=y,y=t,p=1,x[sa[0]]=0,i=1;i<n;i++) x[sa[i]]=cmp(y,sa[i-1],sa[i],j)?p-1:p++; } return ; } int rank[MAX],height[MAX]; void calheight(char *r,int *sa,int n) { int i,j,k=0; for(i=1;i<=n;i++) rank[sa[i]]=i; for(i=0;i<n;height[rank[i++]]=k) for(k?k--:0,j=sa[rank[i]-1];r[i+k]==r[j+k];k++); return ; } char str[MAX]; char ans[MAX]; int d[MAX][20]; void RMQ_init_min(int n) { for(int i = 1;i<=n;++i) d[i][0] = height[i]; for(int j = 1;(1<<j)<=n;++j) for(int i = 1;i+(1<<j)-1<=n;++i) d[i][j] = min(d[i][j-1],d[i+(1<<(j-1))][j-1]); } int RMQ_min(int l,int r) { int k = 0; while((1<<(k+1))<= r-l+1) ++k; return min(d[l][k],d[r-(1<<k)+1][k]); } int main() { //freopen("in.txt","r",stdin); while(scanf("%s",str)==1) { int len = strlen(str); da(str,sa,len+1,'z'+1); calheight(str,sa,len); int ans = len;//最长字符串和最长字符串本身比 RMQ_init_min(len); for(int i = 1;i<=len-1;++i) { ans += RMQ_min(min(rank[i],rank[0])+1,max(rank[i],rank[0])); } printf("%d\n",ans%256); } return 0; }
同学的用暴力过的0MS秒过。。。。
#include<stdio.h> #include<string.h> char input[100003]; bool state[100003]; int position[100001]; int main(){ long long num; int i,j,pnum,k; int value; int fcount; while(1){ num=0; fcount=0; pnum=0; if(scanf("%s",input)==-1) break; int len=strlen(input); num=len; for(i=1;i<len;i++){ if(input[0]==input[i]){ num++; state[i]=true; position[pnum++]=i; }else{ state[i]=false; fcount++; } } int index; for(i=2;i<=len;i++){ if(fcount==len-1) break; k=0; index=0; for(j=position[k];j<=len-i;){ if(input[i-1]==input[j+i-1]){ num++; position[index++]=j; }else{ state[j]=false; fcount++; } j=position[++k]; if(k>=pnum) break; } pnum=index; } value=int(num%256); printf("%d\n",value); } return 0; }