NYOJ 86 找球号(一）

雨点打透心脏的1/2处 2022-09-19 08:17 164阅读 0赞

## 找球号(一） ##

时间限制： 3000 ms | 内存限制： 65535 KB

难度： 3

描述

在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，现在说一个随机整数k(0<=k<=100000100)，判断编号为k的球是否在这堆球中（存在为"YES",否则为"NO"），先答出者为胜。现在有一个人想玩玩这个游戏，但他又很懒。他希望你能帮助他取得胜利。

输入

第一行有两个整数m，n(0<=n<=100000，0<=m<=1000000)；m表示这堆球里有m个球，n表示这个游戏进行n次。  
接下来输入m+n个整数，前m个分别表示这m个球的编号i，后n个分别表示每次游戏中的随机整数k

输出

输出"YES"或"NO"

样例输入

6 4
    23 34 46 768 343 343
    2 4 23 343

样例输出

NO
    NO
    YES
    YES

思路：前几天刚好看了《编程珠玑》上的一个算法,现在就直接拿来用了

#include <stdio.h>
    
    #define BITSPERWORD  32   /*一个整型数值的大小*/
    #define SHIFT        5    /* 2^5 = 32,即一个整型数值有32位，那么用一个元素就能保存32个状态位，0表示不存在，1表示存在*/
    #define MASK         0x1F /*低5位*/
    #define N            100000000 /*待处理的数字的个数*/
    
    int a[1+N/BITSPERWORD];/*节省大量的空间*/
    
    int main(void)
    {
    	int m,n;
    	int x;
    	scanf("%d%d",&m,&n);
    	while (m--)
    	{
    		scanf("%d",&x);
    		a[x>>SHIFT] |= (1<<(x & MASK));
    	}
    	while (n--)
    	{
    		scanf("%d",&x);
    		if (a[x>>SHIFT] & (1<<(x & MASK)))
    		{
    			printf("YES\n");
    		}
    		else
    		{
    			printf("NO\n");
    		}
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，164人围观）

还没有评论，来说两句吧...

相关阅读

相关用天平找小球

三个球A、B、C，大小形状相同且其中有一个球与其他球重量不同。要求找出这个不一样的球。输入格式：输入在一行中给出3个正整数，顺序对应球A、B、C的重量。输出格式：

àì夳堔傛蜴生んèń/ 2024年03月30日 17:49/ 0 赞/ 67 阅读

相关使用天平找出12球中的问题球

有12个球，其中之一重量与其他11个不同，使用天平称三次找出问题球。 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shad

谁借莪１个温暖的怀抱￠/ 2022年12月07日 12:15/ 0 赞/ 148 阅读

相关 NYOJ 138 找球号(二）

找球号(二）时间限制： 1000 ms | 内存限制： 65535 KB 难度： 5 描述在某一国度里流行着一种游戏。游戏规则为：现有一堆球中，每个球上都有一个

╰半橙微兮°/ 2022年09月19日 08:19/ 0 赞/ 167 阅读

相关 NYOJ 528 找球号（三）

找球号（三）时间限制： 2000 ms | 内存限制： 3000 KB 难度： 2 描述 xiaod现在正在某个球场负责网球的管理工作。为了方便管理，他把每个球都

傷城~/ 2022年09月19日 08:17/ 0 赞/ 185 阅读

相关 NYOJ 86 找球号(一）

找球号(一）时间限制： 3000 ms | 内存限制： 65535 KB 难度： 3 描述在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整

雨点打透心脏的1/2处/ 2022年09月19日 08:17/ 0 赞/ 165 阅读

相关 NYOJ--找点

找点时间限制： 2000 ms | 内存限制： 65535 KB 难度： 2 描述上数学课时，老师给了LYH一些闭区间，让他取尽量少的点，使得每个闭区间内至

女爷i/ 2022年08月26日 05:58/ 0 赞/ 187 阅读

相关 NYOJ—题目88 找球号(一）

找球号(一）时间限制：3000 ms | 内存限制：65535 KB 难度：3 描述在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(

女爷i/ 2022年08月25日 05:29/ 0 赞/ 169 阅读

相关 NYOJ 277 车牌号

车牌号时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述茵茵很喜欢研究车牌号码，从车牌号码上可以看出号码注册的早晚，据研究发现，车牌

你的名字/ 2022年08月24日 15:29/ 0 赞/ 206 阅读

相关 NYOJ 242 计算球体积

计算球体积时间限制： 3000 ms | 内存限制： 65535 KB 难度： 1 描述根据输入的半径值，计算球的体积。输入输入数据有多组，每组占一行，

小灰灰/ 2022年08月24日 14:22/ 0 赞/ 210 阅读

相关找球号(一）

找球号(一）描述在某一国度里流行着一种游戏。游戏规则为：在一堆球中，每个球上都有一个整数编号i(0<=i<=100000000),编号可重复，现在说一个随机整数k(

男娘i/ 2022年03月31日 10:36/ 0 赞/ 220 阅读