| ||||||||||
| 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 | |||||||||
用字典树TLE,hash可以过,注意MLE,我开的23333*233过了(42928K 250MS)另外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: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator