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

用字典树TLE,hash可以过,注意MLE,我开的23333*233过了(42928K 250MS)

Posted by KatrineYang at 2016-08-24 00:34:47 on Problem 3630 and last updated at 2016-08-24 00:35:48
另外hash的话用vector或map都T,poj卡STL太狠了
#include <iostream>
#include <stdio.h>
#include <string.h>
#include <vector>
using namespace std;

long long int vc[23333][233];

int main() {
	int t;
	scanf("%d", &t);
	for(int ii = 0; ii < t; ii++){
		int n;
		scanf("%d", &n);
		//vector<long long int> vc[23333];
		int vcNum[23333] = {0};
		char s[15];
		long long int num[10005];
		for(int i = 0; i < n; i++){
			scanf("%s", s);
			long long int hash = 0;
			int len = strlen(s);
			for(int j = 0; j < len; j++){
				hash*=11;
				hash += (s[j]-'0'+1);
				int hh = hash%23333;
				if(j != len-1){
					vc[hh][vcNum[hh]] = hash;
					vcNum[hh]++;
				}
			}
			num[i] = hash;
		}
		bool ky = 1;
		for(int i = 0; i < n; i++){
			int h = num[i]%23333;
			int sz = vcNum[h];
			int j = 0;
			for(; j < sz; j++){
				if(vc[h][j] == num[i]) break;
			}
			if(j < sz){
				ky = 0;
				break;
			}
		}
		if(ky) printf("YES\n");
		else printf("NO\n");
	}
	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