UVALive 5029

用字典树来查询,关键是怎么处理输入的8个数字代表的字符,把每个数分别除以0.95和1.05得到8的区间,按左区间从小到大排序,那么和第一个区间有交集的必然代表二进制0,与它没交集的之后都是1,因为题目保证输入数据是合法的.

#include<cmath>
#include<cstdio>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const double eps = 1e-6;
struct Width{
int idx;
double val, l, r;
Width(int idx, double val){
this->val = val;
this->idx = idx;
this->r = val/0.95;
this->l = val/1.05;
}
bool operator < (const Width &A) const {
if(fabs(l - A.l) < eps) return r + eps < A.r;
return l + eps < A.l;
}
bool isInRange(const Width &A){
return r + eps > A.l;
}
};
struct Node{
int cnt;
Node *child[26];
Node(){
cnt = 0;
for(int i = 0;i < 26;i ++) child[i] = NULL;
}
};
Node *root;
vector<Width>V;
void insertTrie(char str[]){
Node* tmp = root;
while(str[0]){
int idx = str[0]-'a';
if(tmp->child[idx] == NULL) tmp->child[idx] = new Node();
tmp = tmp->child[idx];
tmp->cnt ++;
str++;
}
}
int searchTrie(char str[]){
Node *tmp = root;
while(str[0]){
int idx = str[0]-'a';
if(tmp->child[idx] == NULL) return 0;
tmp = tmp->child[idx];
str++;
}
return tmp->cnt;
}
char fuckAuthorAndFuckAuthorMother(){
int pos, ret(0);
sort(V.begin(), V.end());
for(int i = 1;i < V.size();i ++){
if(V[0].isInRange(V[i])) continue;
pos = i;
break;
}
for(int i = pos;i < V.size();i ++) ret |= (1 << V[i].idx);
return ret;
}
int main(){
int n, m, t;
char str[50];
freopen("in.cpp", "r", stdin);
while(~scanf("%d%d", &n, &m)){
root = new Node();
for(int i = 0;i < n;i ++){
scanf("%s", str);
insertTrie(str);
}
int ans = 0;
for(int i = 0;i < m;i ++){
scanf("%d", &t);
memset(str, 0, sizeof str);
for(int j = 0;j < t;j ++){
V.clear();
double tmp;
for(int k = 7;k >= 0;k --){
scanf("%lf", &tmp);
V.push_back(Width(k, tmp));
}
str[j] = fuckAuthorAndFuckAuthorMother();
}
//printf("str = %s\n", str);
ans += searchTrie(str);
}
printf("%d\n", ans);
}
return 0;
}
上一篇:Android 5.0新特性了解(二)----RippleEffect


下一篇:myeclipse快捷键