题意:给定n个字符串和m个经过处理得到的字符串,问对于m个字符串中的每个字符串,n个字符串中以该字符串为前缀的个数。
分析:
1、误差在[0.95x, 1.05x],因此求8个数的平均数,大于平均数为1,否则为0。
2、字典树求前缀个数。

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
#include<algorithm>
#include<string>
#include<iostream>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<vector>
#include<sstream>
typedef long long LL;
const int INF = 0x3f3f3f3f;
using namespace std;
const int MAXN = 1000000 + 10;
const double eps = 1e-8;
int dcmp(double a, double b){
if(fabs(a - b) < eps) return 0;
return a < b ? -1 : 1;
}
struct Trie{
int val;
Trie *nex[26];
Trie(){
val = 0;
for(int i = 0; i < 26; ++i) nex[i] = NULL;
}
};
void build(string x, Trie *root){
int len = x.size();
for(int i = 0; i < len; ++i){
int cur = x[i] - 'a';
if(root -> nex[cur] == NULL){
root -> nex[cur] = new Trie();
}
root = root -> nex[cur];
++root -> val;
}
}
int query(string x, Trie *root){
int len = x.size();
for(int i = 0; i < len; ++i){
int cur = x[i] - 'a';
if(root -> nex[cur] == NULL) return 0;
root = root -> nex[cur];
}
return root -> val;
}
int POW[10];
void init(){
POW[0] = 1;
for(int i = 1; i <= 7; ++i){
POW[i] = POW[i - 1] * 2;
}
}
int main(){
int N, M;
init();
while(scanf("%d%d", &N, &M) == 2){
string s;
Trie *root = new Trie();
for(int i = 0; i < N; ++i){
cin >> s;
build(s, root);
}
int K;
int ans = 0;
while(M--){
scanf("%d", &K);
s = "";
while(K--){
double ave = 0;
double a[10];
for(int i = 0; i < 8; ++i){
scanf("%lf", &a[i]);
ave += a[i];
}
ave /= 8;
int x = 0;
for(int i = 0; i < 8; ++i){
if(a[i] > ave){
x += POW[7 - i] * 1;
}
}
s += x - 97 + 'a';
}
ans += query(s, root);
}
printf("%d\n", ans);
}
return 0;
}

 

最新文章

  1. Linux 下dns的搭建
  2. MVC Autofac构造函数注入
  3. IOS越狱开发之——进程通讯
  4. HDU 4709:Herding
  5. 使用phantomjs生成网站快照
  6. C#学习笔记之线程 - 通知Signal
  7. 【方言】Access to DialectResolutionInfo cannot be null when &#39;hibernate.dialect&#39; not set
  8. ASCII码表(0 - 255)
  9. Unix,windows和Mac中的换行
  10. LeetCode:链表排序
  11. eclipse-jee 配置tomcat7,解决404错误
  12. ssh-copy-id
  13. Java 之 HTML
  14. JAVA基础面试(四)
  15. Ubuntu系统安装Pyenv
  16. multiset的erase()操作中出现跳过元素的问题
  17. 象棋start
  18. css中border画三角形
  19. python常见的数据结构
  20. jQuery几个易混淆之处(参考《众妙之门》及相关博客)

热门文章

  1. StringUtils工具类中的isBlank()方法和isEmpty()方法的区别
  2. 自定义组装json对象
  3. target信息异常
  4. Visual Studio Code 格式化ESlint 的方法
  5. 记录一次Git远程仓库版本回退
  6. Laradock 下安装Beast扩展
  7. pug
  8. 关于c++ 感想
  9. IdentityServer4专题之一:OAuth2.0介绍
  10. NFS实战