首页 > ACM题库 > HDU-杭电 > HDU 3937-商品检索-字典树-[解题报告]HOJ
2015
04-14

HDU 3937-商品检索-字典树-[解题报告]HOJ

商品检索

问题描述 :

沃尔玛公司由美国零售业的传奇人物山姆•沃尔顿先生于1962年在阿肯色州成立。经过四十多年的发展,沃尔玛公司已经成为美国最大的私人雇主和世界上最大 的连锁最大零售企业目前,沃尔玛在全球开设了7500家商场,员工总数210万人,分布在全球14个国家。每周光临沃尔玛的顾客1.75亿人次。
当然,每天卖出去的东西也是挺多的。那么就需要一个强大的商品检索系统了,能够快速的找到想找的商品,并且能够准确的给出此件商品的数目。假若,山姆先生找到了身为程序员的你,让你帮忙写个程序来完成这个——–人很难完成的任务。任务书如下:

任务名称 商品检索系统
任务提交方式 程序源码
任务输入 商品条形码 | 输入误差 5%
任务输出 对应商品数目 | 输出允许误差 0%

输入:

输入包括若干组测试数据,每组测试数据第一行两个正整数N,M。N代表所有商品的总件数,M代表要查询的商品件数。接下来N行,每行一个字符串S[ i ],代表第i个商品的名称。之后是M组条形码,每组条形码第一行一个数字n,代表条形码的条数,接下来n行,每行一条条形码,代表了一个字符,每组条形码代表了要查询的一种商品的名称。正确的商品名称中仅包含大写字母,小写字母以及数字。

输出:

输入包括若干组测试数据,每组测试数据第一行两个正整数N,M。N代表所有商品的总件数,M代表要查询的商品件数。接下来N行,每行一个字符串S[ i ],代表第i个商品的名称。之后是M组条形码,每组条形码第一行一个数字n,代表条形码的条数,接下来n行,每行一条条形码,代表了一个字符,每组条形码代表了要查询的一种商品的名称。正确的商品名称中仅包含大写字母,小写字母以及数字。

样例输入:

4 1
Onepiece
Chair
Plant
Pen
16
10 20 20 10 10 10 20 10
10 20 20 10 10 20 10 20
10 20 20 10 10 20 20 20
10 20 20 10 20 10 10 20
10 20 20 10 20 20 20 10
10 20 10 10 20 20 20 20
10 20 20 10 20 20 20 10
10 20 20 10 10 20 10 20
10 20 20 20 10 10 10 10
10 20 20 10 20 10 10 20
10 20 20 10 10 20 10 20
10 20 20 10 10 10 20 20
10 20 20 10 10 20 10 20
10 20 20 10 10 20 10 20
10 20 20 10 20 20 20 10
10 20 20 10 10 20 10 10

样例输出:

1

 http://acm.hdu.edu.cn/showproblem.php?pid=3937

中文描述,题意就没问题了。也没什么好说的,字典树,判断条形码所表示的字符得思考下

直接贴代码

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
using namespace std;
#define ep 1e-8
const int kind=64;
#define maxn 3000550
int tree[maxn][kind],top;
void init()
{
	top=1;
	memset(tree[0],0,sizeof(tree[0]));
}
void insert(char *s)
{
	int rt,nxt,i=0,k;
	for(rt=0;s[i];rt=nxt,i++)
	{
		if(s[i]>='A'&&s[i]<='Z')
			k=s[i]-'A';
		else if(s[i]>='a'&&s[i]<='z')
			k=s[i]-'a'+26;
		else
			k=s[i]-'0'+52;
		nxt=tree[rt][k];
		if(nxt==0)
		{
			tree[rt][k]=nxt=top;
			memset(tree[top],0,sizeof(tree[top]));
			tree[nxt][kind-1]=1;
			top++;
		}
		else
			tree[nxt][kind-1]++;
	}
}
int search(char *s,int ss,int tt)
{
	int rt=0,i,k;
	for(i=ss;i<=tt;i++)
	{
		if(s[i]>='A'&&s[i]<='Z')
			k=s[i]-'A';
		else if(s[i]>='a'&&s[i]<='z')
			k=s[i]-'a'+26;
		else
			k=s[i]-'0'+52;
		if(tree[rt][k]==0) return 0;
		rt=tree[rt][k];
	}
	return tree[rt][kind-1];
}
//判断条形码所表示的字符
struct node
{
	int bit;
	double d;
}a[8];
bool cmp(node a,node b)
{
	return a.d<b.d;
}
int check(node a[])
{
	sort(a,a+8,cmp);
	double Max=a[0].d/0.95; //白色条形码的最小宽度
	double Min=a[7].d/2.10; //白色条形码的最大宽度
	if(Min>Max) return -1;
	double l=Min*0.85;      //白色条形码与黑色条形码的最小宽度差
	for(int i=1;i<8;i++)
	{
		double dis=a[i].d-a[i-1].d;
		if((dis>l||fabs(dis-l)<ep))
			return i;
	}
	return 0;
}
int main()
{
	int n,m,N,i,j,k,flag,p,r;
	char str[32],s[40];
	char begin[]={'b','e','g','i','n'};
	char end[]={'e','n','d'};
	while(scanf("%d%d",&n,&m)!=EOF)
	{
		init();
		for(i=0;i<n;i++)
		{
			scanf("%s",str);
			insert(str);
		}
		for(k=0;k<m;k++)
		{
			scanf("%d",&N);
			memset(s,0,sizeof(s));
			flag=0;
			for(i=0;i<N;i++)
			{
				for(j=0;j<8;j++)
				{
					scanf("%lf",&a[j].d);
					a[j].bit=7-j;
				}
				if(flag||N<=8) continue;
				if((r=check(a))==-1)
					flag=1;
				else
				{
					for(p=r;p<8;p++)
						s[i]+=(1<<a[p].bit);
					if(i<5&&s[i]!=begin[i])
						flag=1;
					if(i>=N-3&&s[i]!=end[i-N+3])
						flag=1;
					if(!((s[i]>='0'&&s[i]<='9')||(s[i]>='a'&&s[i]<='z')||(s[i]>='A'&&s[i]<='Z')))
						flag=1;
				}
			}
			if(flag||N<=8)
				printf("wrong barcode!\n");
			else
			{
				int ans=search(s,5,N-4);
				printf("%d\n",ans);
			}
		}
	}
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/ywhorizen/article/details/6704935


  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 你的理解应该是:即使主持人拿走一个箱子对结果没有影响。这样想,主持人拿走的箱子只是没有影响到你初始选择的那个箱子中有奖品的概率,但是改变了其余两个箱子的概率分布。由 1/3,1/3 变成了 0, 2/3

  3. 我还有个问题想请教一下,就是感觉对于新手来说,递归理解起来有些困难,不知有没有什么好的方法或者什么好的建议?

  4. 题目需要求解的是最小值,而且没有考虑可能存在环,比如
    0 0 0 0 0
    1 1 1 1 0
    1 0 0 0 0
    1 0 1 0 1
    1 0 0 0 0
    会陷入死循环