问题 A: 哈希

时间限制: 1 Sec  内存限制: 128 MB
提交: 37  解决: 18
[提交][状态][讨论版][命题人:外部导入][Edit] [TestData]

题目链接：http://acm.ocrosoft.com/problem.php?cid=1716&pid=0

题目描述

在数据结构中，我们学过哈希表。我们知道，哈希存储方法是一种根据关键码值(Key value)而直接进行访问的数据结构方法。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做哈希函数H(key)，存放记录的数组叫做哈希表。
在哈希表的构造中，哈希函数的选取显得异常重要。比如，在存储一个班级所有学生的某一门学科成绩的时候（假设该班人数<100），每个学生的学号有10~12位，我们不可能开出这么大的数组来储存，由于每个学生的学号末2位均不相同，我们可以开一个大小为100的数组，假设一个同学的学号为090104100151,那么，我们可以将该同学的成绩记录在下标为51数组元素中。这里我们用到的哈希方法叫做除留余数法，即H(key)=key % p(此处的p为100)。但是，这种哈希函数经常会产生冲突，即对于key1!=key2，却有H(key1)==H(key2)。现给定p以及n个关键码(key)，问：按这种哈希函数对着n个关键码进行映射，是否有冲突。

输入

输入文件中包含多个测试数据。每个测试数据占两行。每个测试数据的第一行为2个数p和n，第二行为n个关键码。其中p和n为不大于10000的正整数，其它的数均为不大于10000000的正整数。
最后一行为0 0，表示输入结束。

输出

对于每个测试数据，如果存在冲突，则输出"Conflict"，否则输出"All right"。

样例输入

100 3

1002 1103 2111

13 5

2 3 5 13 15

0 0

样例输出

All right

Conflict

思路：题目叫哈希，我也不知道这个和哈希有啥关系,可能是告诉你某种哈希入门的思想吧，直接map一弄就好了。代码：

#include<bits/stdc++.h>

using namespace std;

map<int, int>sxw;

int main()

{

    int p, n;

    while (cin >> p >> n && p != 0 && n != 0)

    {

         int fla = 0;

         sxw.clear();

         for (int i = 1; i <= n; i++)

         {

             int x;

             cin >> x;

             if (sxw[x%p])//说明之前已经出现过这个学号了

             {

                  fla = 1;//标记

             }

             sxw[x%p] = 1;

         }

         if (fla == 0)

         {

             cout << "All right" << endl;

         }

         else cout << "Conflict" << endl;

    }

}