Codeforces Round #FF (Div. 2/A)/Codeforces447A_DZY Loves Hash(哈希)

2024-09-04 08:38

文章标签 codeforces round div 哈希 hash ff loves dzy codeforces447a

本文主要是介绍Codeforces Round #FF (Div. 2/A)/Codeforces447A_DZY Loves Hash(哈希)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

DZY has a hash table with p buckets, numbered from 0 to p - 1. He wants to insert n numbers, in the order they are given, into the hash table. For the i-th number xi, DZY will put it into the bucket numbered h(xi), where h(x) is the hash function. In this problem we will assume, that h(x) = x mod p. Operation a mod b denotes taking a remainder after division a by b.

However, each bucket can contain no more than one element. If DZY wants to insert an number into a bucket which is already filled, we say a "conflict" happens. Suppose the first conflict happens right after the i-th insertion, you should output i. If no conflict happens, just output -1.

Input

The first line contains two integers, p and n (2 ≤ p, n ≤ 300). Then n lines follow. The i-th of them contains an integer xi (0 ≤ xi ≤ 109).

Output

Output a single integer — the answer to the problem.

Sample test(s) 
input 
10 5
0
21
53
41
53
output 
4
input 
5 5
0
1
2
3
4
output 
-1
 
 

解题报告

水，好像写麻烦了。

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
int p,n,i,num[1000],j;
vector<int>hashh[1000];
int main()
{while(cin>>p>>n){memset(hashh,0,sizeof(hashh));for(i=0;i<n;i++){cin>>num[i];}for(i=0;i<n;i++){int sz=hashh[num[i]%p].size();if(sz){cout<<i+1<<endl;break;}else hashh[num[i]%p].push_back(num[i]);}if(i==n)cout<<"-1"<<endl;}return 0;
}

这篇关于Codeforces Round #FF (Div. 2/A)/Codeforces447A_DZY Loves Hash(哈希)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

http://www.chinasem.cn/article/1135530。 23002807@qq.com

相关文章

Redis的Hash类型及相关命令小结

Redis的Hash类型及相关命令小结

《Redis的Hash类型及相关命令小结》edisHash是一种数据结构,用于存储字段和值的映射关系,本文就来介绍一下Redis的Hash类型及相关命令小结,具有一定的参考价值,感兴趣的可以了解一下... 目录HSETHGETHEXISTSHDELHKEYSHVALSHGETALLHMGETHLENHSET

阅读更多...

哈希leetcode-1

哈希leetcode-1

目录 1前言 2.例题 2.1两数之和 2.2判断是否互为字符重排 2.3存在重复元素1 2.4存在重复元素2 2.5字母异位词分组 1前言哈希表主要是适合于快速查找某个元素（O(1)）当我们要频繁的查找某个元素，第一哈希表O(1)，第二，二分O(log n) 一般可以分为语言自带的容器哈希和用数组模拟的简易哈希。最简单的比如数组模拟字符存储，只要开26个c

阅读更多...

学习hash总结

学习hash总结

2014/1/29/ 最近刚开始学hash，名字很陌生，但是hash的思想却很熟悉，以前早就做过此类的题，但是不知道这就是hash思想而已，说白了hash就是一个映射，往往灵活利用数组的下标来实现算法，hash的作用：1、判重；2、统计次数；

阅读更多...

hdu1043（八数码问题，广搜 + hash（实现状态压缩））

hdu1043（八数码问题，广搜 + hash（实现状态压缩））

利用康拓展开将一个排列映射成一个自然数，然后就变成了普通的广搜题。 #include<iostream>#include<algorithm>#include<string>#include<stack>#include<queue>#include<map>#include<stdio.h>#include<stdlib.h>#include<ctype.h>#inclu

阅读更多...

康拓展开（hash算法中会用到）

康拓展开（hash算法中会用到）

康拓展开是一个全排列到一个自然数的双射（也就是某个全排列与某个自然数一一对应）公式： X=a[n]*(n-1)!+a[n-1]*(n-2)!+...+a[i]*(i-1)!+...+a[1]*0! 其中,a[i]为整数,并且0<=a[i]<i,1<=i<=n。（a[i]在不同应用中的含义不同）；典型应用：计算当前排列在所有由小到大全排列中的顺序，也就是说求当前排列是第

阅读更多...

hdu1496（用hash思想统计数目）

hdu1496（用hash思想统计数目）

作为一个刚学hash的孩子，感觉这道题目很不错，灵活的运用的数组的下标。解题步骤：如果用常规方法解，那么时间复杂度为O（n^4）,肯定会超时，然后参考了网上的解题方法，将等式分成两个部分，a*x1^2+b*x2^2和c*x3^2+d*x4^2，各自作为数组的下标，如果两部分相加为0，则满足等式；代码如下： #include<iostream>#include<algorithm

阅读更多...

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

usaco 1.3 Prime Cryptarithm(简单哈希表暴搜剪枝)

思路： 1. 用一个 hash[ ] 数组存放输入的数字，令 hash[ tmp ]=1 。 2. 一个自定义函数 check( ) ，检查各位是否为输入的数字。 3. 暴搜。第一行数从 100到999，第二行数从 10到99。 4. 剪枝。代码： /*ID: who jayLANG: C++TASK: crypt1*/#include<stdio.h>bool h

阅读更多...

usaco 1.2 Milking Cows（类hash表）

usaco 1.2 Milking Cows（类hash表）

第一种思路被卡了时间到第二种思路的时候就觉得第一种思路太坑爹了代码又长又臭还超时！！第一种思路：我不知道为什么最后一组数据会被卡超时超了0.2s左右大概想法是快排加一个遍历先将开始时间按升序排好然后开始遍历比较 1 若下一个开始beg[i] 小于 tem_end 则说明本组数据与上组数据是在连续的一个区间取max( ed[i],tem_end ) 2 反之这个

阅读更多...

uva 10029 HASH + DP

uva 10029 HASH + DP

题意：给一个字典，里面有好多单词。单词可以由增加、删除、变换，变成另一个单词，问能变换的最长单词长度。解析： HASH+dp 代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#inc

阅读更多...

整数Hash散列总结

整数Hash散列总结

方法： step1 :线性探测 step2 散列当 h(k)位置已经存储有元素的时候，依次探查(h(k)+i) mod S, i=1,2,3…，直到找到空的存储单元为止。其中，S为数组长度。 HDU 1496 a*x1^2+b*x2^2+c*x3^2+d*x4^2=0 。 x在 [-100,100] 解的个数 const int MaxN = 3000

阅读更多...