本文主要是介绍NYOJ138 找球号(二）(哈希，位运算，vector,二分)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
找球号(二）
时间限制： 1000 ms | 内存限制： 65535 KB
难度： 5
- 描述
- 在某一国度里流行着一种游戏。游戏规则为：现有一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，还有一个空箱子，现在有两种动作：一种是"ADD"，表示向空箱子里放m(0<m<=100)个球，另一种是"QUERY”，表示说出M(0<M<=100)个随机整数ki(0<=ki<=100000100),分别判断编号为ki 的球是否在这个空箱子中（存在为"YES",否则为"NO"），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。
- 输入
- 第一行有一个整数n(0<n<=10000);
随后有n行;
每行可能出现如下的任意一种形式：
第一种：
一个字符串"ADD"，接着是一个整数m，随后有m个i；
第二种：
一个字符串"QUERY”，接着是一个整数M，随后有M个ki；
输出 - 输出每次询问的结果"YES"或"NO". 样例输入
-
2 ADD 5 34 343 54 6 2 QUERY 4 34 54 33 66
样例输出 -
YES YES NO NO
- 第一行有一个整数n(0<n<=10000);
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
using namespace std;
int a[10000001];
int erfen(int index,int m)
{int mid;int start=0,end=m-1;while(start<=end){mid=(start+end)/2;if(a[mid]>index){end=mid-1;}else if(a[mid]<index){start=mid+1;}elsereturn 1;}return 0;
}
int main()
{int n;int x=0;scanf("%d",&n);char b[15];while(n--){memset(b,'\0',sizeof(b));scanf("%s",b);if(strcmp(b,"ADD")==0){int m;scanf("%d",&m);for(int i=0; i<m; i++)scanf("%d",&a[x++]);}else if(strcmp(b,"QUERY")==0){int k;scanf("%d",&k);sort(a,a+x);while(k--){int m;scanf("%d",&m);printf("%s\n",erfen(m,x)?"YES":"NO");}}}return 0;
}代码2（ vector容器/ac）：
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <string.h>
#include <vector>
using namespace std;
vector<bool>a(100000001);
int main()
{int n;int x=0;scanf("%d",&n);char b[15];while(n--){memset(b,'\0',sizeof(b));scanf("%s",b);if(strcmp(b,"ADD")==0){int m,n;scanf("%d",&m);while(m--){scanf("%d",&n);a[n]=true;}}else if(strcmp(b,"QUERY")==0){int k;scanf("%d",&k);while(k--){int m;scanf("%d",&m);printf("%s\n",a[m]==true?"YES":"NO");}}}return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<time.h>
#include<algorithm>
using namespace std;#define N 1000010
#define CLR(arr, what) memset(arr, what, sizeof(arr))const int fib = 111123;
int Key[N], Head[N], Next[N];
int top;void add(int n)
{int temp;temp = n % fib;Key[top] = n;Next[top] = Head[temp];Head[temp] = top;top++;
}int main()
{int ncase;char str[8];int num, number;bool flag;CLR(Key, 0);CLR(Head, -1);top = 0;flag = false;scanf("%d", &ncase);while(ncase--){scanf("%s", str);if(str[0] == 'A'){scanf("%d", &num);for(int i = 0; i < num; ++i){scanf("%d", &number);add(number);}}else{scanf("%d", &num);for(int i = 0; i < num; ++i){scanf("%d", &number);int temp = number % fib;for(int j = Head[temp]; j != -1; j = Next[j])if(Key[j] == number){flag = true;break;}printf(flag == true ? "YES\n" : "NO\n");flag = false;}}}return 0;
}
代码4（ 位运算版）：//代码来自于别人
#include<stdio.h>
unsigned int hash[3125005] = {0};
int main()
{ int i,a,t,n; char str[10]; scanf("%d", &t); while(t--) { scanf("%s %d", str, &n); if(str[0] == 'A') { for(i = 0; i < n; ++i) { scanf("%d", &a); hash[a / 32] |= 1 << (a % 32); } } else if(str[0] == 'Q') { for(i = 0; i < n; ++i) { scanf("%d", &a); if(hash[a / 32] & (1 << (a % 32))) printf("YES\n"); else printf("NO\n"); } } }return 0;
} ps: 3125005怎么来的？因为最大值是10^7+10。用32来除法散列，（10^7+10）/32 ~~3125000.3125，所以取3125005。为什么是用32来散列呢？数据说了数值不会超过32位。虽然是这样，但是这种方法还是很难理解
这篇关于NYOJ138 找球号(二）(哈希，位运算，vector,二分)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
