博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
hdu3724Encoded Barcodes(Trie tree)
阅读量:5879 次
发布时间:2019-06-19

本文共 1692 字,大约阅读时间需要 5 分钟。

题目大意:给n个字符串,给m个询问,每个询问给k个条形码。每个条形码由8个小码组成,每个小码有相应的宽度,已知一个条形码的宽度只有2种,宽的表示1,窄的表示0。并且宽的宽度是窄的宽度的2倍。由于扫描的时候有误差,每个小码的宽度为一个浮点型数据,保证每个数据的误差在5%内。所以一个条形码可以对应一个ASCC码,表示一个小写字母。k个条形码表示一个字符串s,每个询问表示给定的m个字符串中以s为前缀的字符串个数。

题目分析:将n个字符串插入到字典树中,并记录下每个前缀有多少个字符串。即每插入一个字符串,在相应路径上+1,然后就是模拟出字符串s,在字典树中查询即可。

关于条形码数据的处理:输入的时候记录下8个数据中的最大值,然后对于所有的数据,满足fabs(mx - data[i])/mx < 0.1的,那么第i为为1,否则0。

详情请见代码:

 

#include 
#include
#include
#include
#include
#include
using namespace std;const int N = 10005;const int M = 2005;const int NM = 10000005;const double eps = 1e-6;typedef __int64 ll;struct node{ int cnt; int next[26];}trie[NM];int num,n,m;double dt[9];char str[M];void init(int x){ memset(trie[x].next,0,sizeof(trie[x].next)); trie[x].cnt = 0;}void insert(int cur,int dp,int len){ trie[cur].cnt ++; if(dp == len) return; if(trie[cur].next[str[dp] - 'a'] == 0) { trie[cur].next[str[dp] - 'a'] = num; init(num); num ++; } insert(trie[cur].next[str[dp] - 'a'],dp + 1,len);}int query(int cur,int dp,int len){ if(dp == len) return trie[cur].cnt; if(trie[cur].next[str[dp] - 'a']) return query(trie[cur].next[str[dp] - 'a'],dp + 1,len); else return 0;}int main(){ int i,j,k; while(scanf("%d%d",&n,&m) != EOF) { num = 1; ll ans = 0; init(0); while(n --) { scanf("%s",str); int len = strlen(str); insert(0,0,len); } while(m --) { scanf("%d",&k); for(i = 0;i < k ;i ++) { double mx = 0; int code = 0; for(j = 0;j < 8;j ++) { scanf("%lf",&dt[j]); if(dt[j] - mx > eps) mx = dt[j]; } for(j = 0;j < 8;j ++) { if(fabs(mx - dt[j])/mx - 0.1 < eps) code += (1<<(7 - j)); } str[i] = code; } str[k] = '\0'; ans += query(0,0,k); } printf("%I64d\n",ans); } return 0;}

 

 

转载地址:http://frdix.baihongyu.com/

你可能感兴趣的文章
我的友情链接
查看>>
Html body的滚动条禁止与启用
查看>>
Tengine新增nginx upstream模块的使用
查看>>
多媒体工具Mediainfo
查看>>
1-小程序
查看>>
CentOS图形界面和命令行切换
查看>>
HTML5通信机制与html5地理信息定位(gps)
查看>>
Mind_Manager_2
查看>>
手动升级 Confluence - 规划你的升级
查看>>
汽车常识全面介绍 - 悬挂系统
查看>>
电子政务方向:We7.Cloud政府云门户
查看>>
ansible 基本操作(初试)
查看>>
更改tomcat的根目录路径
查看>>
51nod 1292 字符串中的最大值V2(后缀自动机)
查看>>
加快ALTER TABLE 操作速度
查看>>
学习笔记之软考数据库系统工程师教程(第一版)
查看>>
PHP 程序员的技术成长规划
查看>>
memcached 分布式聚类算法
查看>>
jquery css3问卷答题卡翻页动画效果
查看>>
$digest already in progress 解决办法——续
查看>>