CF447A 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.
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 a single integer — the answer to the problem.
10 5
0
21
53
41
53
4
5 5
0
1
2
3
4
-1
就是问hash是否存在冲突;
用 map 去判重即可;
当然开数组也没问题;
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstdlib>
#include<cstring>
#include<string>
#include<cmath>
#include<map>
#include<set>
#include<vector>
#include<queue>
#include<bitset>
#include<ctime>
#include<deque>
#include<stack>
#include<functional>
#include<sstream>
//#include<cctype>
//#pragma GCC optimize(2)
using namespace std;
#define maxn 20005
#define inf 0x7fffffff
//#define INF 1e18
#define rdint(x) scanf("%d",&x)
#define rdllt(x) scanf("%lld",&x)
#define rdult(x) scanf("%lu",&x)
#define rdlf(x) scanf("%lf",&x)
#define rdstr(x) scanf("%s",x)
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int U;
#define ms(x) memset((x),0,sizeof(x))
const long long int mod = 1e9 + 7;
#define Mod 1000000000
#define sq(x) (x)*(x)
#define eps 1e-3
typedef pair<int, int> pii;
#define pi acos(-1.0)
//const int N = 1005;
#define REP(i,n) for(int i=0;i<(n);i++)
typedef pair<int, int> pii;
inline ll rd() {
ll x = 0;
char c = getchar();
bool f = false;
while (!isdigit(c)) {
if (c == '-') f = true;
c = getchar();
}
while (isdigit(c)) {
x = (x << 1) + (x << 3) + (c ^ 48);
c = getchar();
}
return f ? -x : x;
} ll gcd(ll a, ll b) {
return b == 0 ? a : gcd(b, a%b);
}
ll sqr(ll x) { return x * x; } /*ll ans;
ll exgcd(ll a, ll b, ll &x, ll &y) {
if (!b) {
x = 1; y = 0; return a;
}
ans = exgcd(b, a%b, x, y);
ll t = x; x = y; y = t - a / b * y;
return ans;
}
*/ int n, p;
int x[maxn]; map<int, int>mp;
int main() {
//ios::sync_with_stdio(0);
cin >> p >> n;
int pos = -1;
for (int i = 1; i <= n; i++)cin >> x[i];
for (int i = 1; i <= n; i++) {
int tmp = x[i];
if (!mp[tmp%p]) {
mp[tmp%p] = 1;
}
else if (mp[tmp%p]) {
pos = i; break;
}
}
cout << pos << endl;
return 0;
}
最新文章
- loop 循环和检测点 9.3
- 记录asp.net在IE10下事件丢失排错经过
- [Tool] Chrome内的本地网页,使用XMLHttpRequest读取本地档案
- set的用法
- ytu 1041: 迭代法求平方根(水题)
- 关于c语言二维数组与指针的个人理解及处理办法。
- Java-->;实现断点续传(下载)
- 【翻译】Zakas解答Baranovskiy的JavaScript测验题
- NET Web开发
- iOS开发之左右抖动效果
- JavaScript Date(日期)对象
- 内网gitlab11.2升级至11.4.5
- Django 的逆向解析url--reverse(转)
- dubbo-admin 无法支持JDK1.8
- 使用Xpath定位元素
- TCP、UDP详解
- 【HDOJ 1337】I Hate It(线段树维护区间最大值)
- sum(sum(abs(y))) 中 sum(sum())什么意思?
- Walk of Length 6
- pytorch笔记:09)Attention机制