Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:暴力很快啊,204ms,这题给3000ms根本没有必要吧,是数据太弱了嘛qaqIn Reply To:暴力很快啊,204ms,这题给3000ms根本没有必要吧,是数据太弱了嘛qaq Posted by:KatrineYang at 2016-07-25 17:25:01 > #include <iostream> > #include <stdio.h> > #include <math.h> > #include <string.h> > using namespace std; > > char s[1000004] = {'\0'}; > > int main() { > while(1){ > scanf("%s", s); > if(s[0] == '.') return 0; > int len = strlen(s); > int divList[2000]; > int pl = 0; > int sq = (int)sqrt(len*1.0); > int SQ = sq; > if(sq * sq == len) sq--; > int i = 1; > while(i <= sq){ > if(len%i != 0){ > i++; > continue; > } > divList[pl] = i; > pl++; > i++; > } > int offset = pl; > if(SQ*SQ == len) { > divList[pl] = SQ; > offset ++; > } > for(int i = 0; i < pl; i++){ > divList[offset + i] = len / divList[pl-1-i]; > } > pl += offset; > //for(int i = 0; i < pl; i++) cout << divList[i] << " "; cout << endl; > int fanjieguo; > for(int i = 0; i < pl; i++){ > bool keyi = true; > int intv = divList[i]; > for(int i = 0; i < len-intv; i++){ > if(s[i] != s[i+intv]){ > keyi = false; > break; > } > } > if(keyi){ > fanjieguo = intv; > break; > } > } > printf("%d\n", len/fanjieguo); > } > return 0; > } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator