不少航空公司都会提供优惠的会员服务，当某顾客飞行里程累积达到一定数量后，可以使用里程积分直接兑换奖励机票或奖励升舱等服务。现给定某航空公司全体会员的飞行记录，要求实现根据身份证号码快速查询会员里程积分的功能。
输入格式说明：
输入首先给出两个正整数N（<=105）和K（<=500）。其中K是最低里程，即为照顾乘坐短程航班的会员,航空公司还会将航程低于K公里的航班也按K公里累积。随后N行，每行给出一条飞行记录。飞行记录的输入格式为：“18位身份证号码（空格）飞行里程”。其中身份证号码由17位数字加最后一位校验码组成，校验码的取值范围为0~9和x共11个符号；飞行里程单位为公里，是(0, 15 000]区间内的整数。然后给出一个正整数M（<=105），随后给出M行查询人的身份证号码。
输出格式说明：
对每个查询人，给出其当前的里程累积值。如果该人不是会员，则输出“No Info”。每个查询结果占一行。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 |
4 500 330106199010080419 499 110108198403100012 15000 120104195510156021 800 330106199010080419 1 4 120104195510156021 110108198403100012 330106199010080419 33010619901008041x |
800 15000 1000 No Info |
#include<iostream>
#include<stdio.h>
#include<time.h>
#include<ctype.h>
#include<algorithm>
#include<string.h>
#include<queue>
#include<vector>
using namespace std;
typedef long int lld;//long int
#define rot(v) (((v)>>3)|(((v)&7)<<9))
const int MAX=110000;
const int MOD=100003;
const int INF=1000000000;
struct Node
{
int a,b;
char x;
int mile,next;
}node[MAX];
int head[MOD],E;
char buf[22];
int chg(char x)
{
if(x==‘x‘)return 10;
return x-‘0‘;
}
int fun(char s[],int &a,int &b,char &x)
{
int ret=0,i;
int tmp;
a=b=0;
for(i=0;i<9;i++)
{
tmp=s[i]-‘0‘;
a=a*10+tmp;//记录没取余数的数值
ret=ret*10+tmp;
}
ret%=MOD;
for(;i<17;i++)
{
tmp=s[i]-‘0‘;
b=b*10+tmp;//记录后面没取余数的数值
ret=(ret*10+tmp)%MOD;
}
x=s[i];//记录最后一位
return (ret*100+chg(s[i]))%MOD;//返回取余数的数值
}
void ins(char s[],int mile)
{
int a,b;
char x;
int h=fun(s,a,b,x);
int i;
//发生冲突时的处理
for(i=head[h];i!=-1;i=node[i].next)//head 全局变量
{
if(node[i].x==x&&node[i].a==a&&node[i].b==b)
{
node[i].mile+=mile;
return ;
}
}
node[E].a=a;
node[E].b=b;
node[E].x=x;
node[E].mile=mile;
node[E].next=head[h];
head[h]=E++;
}
int query(char s[])
{
int a,b;
char x;
int h=fun(s,a,b,x);
int i;
for(i=head[h];i!=-1;i=node[i].next)
{
if(node[i].x==x&&node[i].a==a&&node[i].b==b)return node[i].mile;
}
return -1;
}
void out(int n)
{
if(n)
{
out(n/10);
putchar(‘0‘+n%10);
}
}
int main()
{
int n,m;
int k,i;
while(scanf("%d%d",&n,&k)!=EOF)
{
memset(head,-1,sizeof(head));
E=0;
int mile=0;
while(n--)
{
scanf("%s%d",buf,&mile);
if(mile<k)mile=k;
ins(buf,mile);
}
scanf("%d",&m);
getchar();
while(m--)
{
//scanf("%s",buf);
gets(buf);
mile=query(buf);
if(mile==-1)puts("No Info");
else
{
out(mile);
// cout<<mile;
// printf("%d",mile);
putchar(‘\n‘);
}
}
}
return 0;
}
解题报告：题目要求的查询次数可能有105的数量级。时间只有100ms 所以一般顺序查询算法是不能满足要求的。这时候就想到了Hash查询，键值对应结果的查询算法。
即使明确了思路，本题依然存在一下难点：
【1】如何选取适当的Hash函数，构造键值对。
【2】我们要知道任何Hash函数都会存在冲突的问题，即：多组查询结果对应同一个键值，如何解决冲突。
【3】如何在有限的时间限制下找到方法进一步优化程序。
【1】关于函数的选取尝试了几个方法，如果不侦查冲突的话，一般的取余数算法不能满足要求，折叠取余数算法也不行。最后采取的是累加取余数+冲突检测。
【2】要进行冲突检测就必须有足够的数据特征来区别不同的数值。根据本题的特点我们选取前9位的和a和后9位的和b以及最后一位x，还有键值h四个值来标识一个数值。
但是这样存储数据的数据结构就必须要使用结构体。所以我们构建了一个结构体node，包括a,b,x,next,mile。其中next用于存放发生冲突时的下一个数组下标。正常情况下一个键值对应一个数值，这时候的存储过程如下所示：
node[E].next=-1
|
node[0] node[1] node[2] node[3]........node[E]
| |
head[3456] head[h]
发生冲突时存储过程如下所示：
node[E].next=-1 node[E].next=2
| |
node[0] node[1] node[2] node[3]........node[E]
| |
head[3456] head[h]
所以当我们进行查询时，先计算出键值h和标识数值a,b,x,得i=head[h]，如果查询node[i]发现(node[i].x==x&&node[i].a==a&&node[i].b==b)的条件不成立，我们知道发生的冲突，接下来就好办了，令i=node[E].next，继续(node[i].x==x&&node[i].a==a&&node[i].b==b)的比对，直到符合条件。
从更一般的角度看其实数据的存储如下图：
有冲突的数据 head[h] 无冲突的数据 head[q]
| |
node[E] node[x]
| |
node[s] （s=node[E].next） NULL（-1=node[x].next）
.......................
【3】效率问题除了一般的时间换空间的思路外，还有一个值得注意的就是输入输出上。
航空公司VIP客户查询【PAT】,布布扣,bubuko.com
原文：http://blog.csdn.net/linsheng9731/article/details/22619583