| ||||||||||
| 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