Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:暴力很快啊,204ms,这题给3000ms根本没有必要吧,是数据太弱了嘛qaq

Posted by 16310320529 at 2017-07-18 09:26:59 on Problem 2406
In 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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator