首页 > 试题广场 >

游戏任务标记

[编程题]游戏任务标记
  • 热度指数:23469 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 32M,其他语言64M
  • 算法知识视频讲解
游戏里面有很多各式各样的任务,其中有一种任务玩家只能做一次,这类任务一共有1024个,任务ID范围[1,1024]。请用32个unsigned int类型来记录着1024个任务是否已经完成。初始状态都是未完成。 输入两个参数,都是任务ID,需要设置第一个ID的任务为已经完成;并检查第二个ID的任务是否已经完成。 输出一个参数,如果第二个ID的任务已经完成输出1,如果未完成输出0。如果第一或第二个ID不在[1,1024]范围,则输出-1。

输入描述:
输入包括一行,两个整数表示任务ID.


输出描述:
输出是否完成
示例1

输入

1024 1024

输出

1
//参考pku_coder,改进版(速度更快)
//解释:1024=32*32,因此可用32个整数表示1024位(因为每个整数32位)
//因为任务ID范围是1~1024,所以减1转化为0~1023
//然后任务ID除以32,商为存到哪个整数,余数为该整数对应位(置1即可)
//注:除以32相当于直接右移5位,对32取余相当于"与31"(这个技巧只对2的次方数有效).
//拓展:大数据处理,可自行查找1-bitmap和2-bitmap.
#include <iostream>
using namespace std;
   
unsigned int arr[32];
   
int main()
{
    int id1, id2;
    while(cin>>id1>>id2)
    {
        if(!(id2>=1 && id2<=1024))
        {
            cout<<-1<<endl;
            continue;
        }
        arr[(id1-1)>>5] |= (1<<(id1&31));
        cout<<( (arr[(id2-1)>>5] & (1<<(id2&31))) != 0)<<endl;
    }
    return 0;
}


/*
再扩展一点:本算法只支持一次标记(已经满足题意:status只能从0变成1)。
在实际中如果需要重复标记(就是status可能从0变成1,也可能从1变成0),
则需要在设置状态之前先将对应的位清除,在第22行之前加一句
arr[(id1-1)>>5] &= ~(1<<(id1&31));
即可。
*/

编辑于 2018-09-30 20:10:14 回复(11)
//1024种任务有2^1024种可能,需要1024个bit,就是1024/8=128byte。一个int是4byte,刚好需要32个int。就是说,把32个int排成一行,就是1024个bit,每个bit来表示某个任务是否完成。
#include<iostream>
using namespace std;
//参数:s是32个int构成的数组。n表示第几个任务(在这里从0开始),deal表示操作类型:如果为1表示置位,否则表示取位。
int check(unsigned int* s,int n,int deal){//if deal==1 set; else get;
    int id=n/32;//注意n是从0开始的,否则就会不统一
    int id2=n%32;
    unsigned int b=0x80000000;//测试时候发现如果不加unsigned的话,就会出错。有符号数字会填充符号位
// b 表示左边第一位是1其他都是0的无符号整数。
    b>>=id2;
    if(deal==1){
    s[id]|=b;
        return -1;
    }else{
      
        return (s[id]&b)!=0;
    }
}
int main(){
    int a,b;
    cin>>a>>b;
    unsigned int s[32]={};
    if(a<1||a>1024 ||b<1||b>1024){
        cout<<-1;
        return 0;
    }
    check(s,a-1,1);
    int i=check(s,b-1,0);
    if(i)
        cout<<1;
    else
        cout<<0;
    return 0;
}
发表于 2017-08-11 16:15:06 回复(4)
import java.util.Scanner;

public class Main{
    public static long flag[] = new long[32];
    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        if(x1024||y1024) {
            System.out.println(-1);
        }
        else {
            set(x);
            if(get(y))System.out.println(1);
            else System.out.println(0);
        }

    }
    public static void set(int x) {
        x--;
        int t = x >> 5;//选择进入哪个组
        int c = x & 31;//选择组内位置
        flag[t] = flag[t] | 1<<c;//加上那个位置 

    }
    public static boolean get(int y) {
        y--;
        int t = y >> 5;//选择进入哪个组
        int c = y & 31;//选择组内位置
        return (flag[t]>>c&1)==1;//将其右移c位然后看最后一位是不是1
    }
}

发表于 2018-05-16 10:45:48 回复(0)
//头一次发代码,略鸡冻
//话说那么多人直接几个if就提交了的是怎么想的,只是为了过case?
//题目中心要求是 将1024个任务的状态平均分给32unsigned int个变量,每个unsigned变量恰好有32位,每一位有0,1两种状态,
//所以32个unsigned int变量恰好可以表示一共1024个任务的状态,上码
import java.util.*;
public class Main {

	static long[] ar = new long[32]; //定义long型,但只用前32位,java没有unsigned int怪我喽
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		while (sc.hasNext()) {
			int change = sc.nextInt()-1;
			int find = sc.nextInt()-1;
			System.out.println(Find(change,find));
		}
	}
	public static int Find(int change,int find){
		if(change>=1024||find>=1024) return -1;
        
        //将1024个任务的状态平均分给32个变量,每个变量恰好可以表示32个任务(32位,一位一个),刚好满足题意
        
		int ch_b = change/32;    //计算要完成的任务在哪一个变量
		int ch_s = change-ch_b*32; //计算要完成的任务在该变量的哪一位
        
		int f_b = find/32;     //计算要查找的任务在哪一个变量
		int f_s = find-f_b*32;  //计算要查找的任务在该变量的哪一位
        
		ar[ch_b] = ar[ch_b]|(long)Math.pow(2, ch_s);  //通过或运算把表示要完成任务的那一位置为1
        
		if( (ar[f_b]|(long)Math.pow(2, f_s)) ==(long)Math.pow(2, f_s) ) //通过或运算来确定表示要查找的任务的那一位是否为1,long型问题同上
			return 1;
		else return 0;
	}
}

发表于 2017-09-03 18:29:49 回复(15)
看到有些牛友只是考虑了输入一次时的情况,感觉不太对
我认为这道是要连续输入的,要不然我只需判断ID1和ID2相不相等就可以了完全不用做题!
这道题主要是考察位预算,在实际中这样考虑问题可以大大减少内存的使用
比如控制彩灯,之类的程序
附上我理解的题意,应该还算清晰吧。

#include <iostream>
using namespace std;

int main() {
    
    unsigned int task_flag[32] = { 0 };

    int id1, id2;
    while (cin >> id1 >> id2) {
        if (id1 > 1024 || id1 < 1 || id2 > 1024 || id2 < 1) {
            cout << -1 << endl;
            break;
        }

        int index = (id1 - 1) / 32;
        int bit = (id1 - 1) % 32;
        task_flag[index] |= 1 << bit;         // 设置任务

        index = (id2 - 1) / 32;
        bit = (id2 - 1) % 32;
        //cout << (1 << bit & task_flag[index]) << endl;  简洁写法
        if (1 << bit & task_flag[index]) {    // 检查任务
            cout << 1 << endl;
        } else {
            cout << 0 << endl;
        }
    }

    return 0;
}

编辑于 2017-09-03 10:55:50 回复(4)
#include <string.h>
#include <iostream>
using namespace std;

int main(){
    int x,y;
    unsigned bitmap[32];//位图
    while(cin>>x>>y){
        if(x<1||x>1024||y<1||y>1024){
            cout<<-1<<endl;
            continue;
        }
        bzero(bitmap,sizeof(bitmap));
        bitmap[(x-1)/32]|=1<<(x-1)%32;
        if((bitmap[(y-1)/32]>>(y-1)%32)&1)
            cout<<1<<endl;
        else
            cout<<0<<endl;
    }
    return 0;
}

编辑于 2017-09-04 13:25:36 回复(3)
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

int main() {
    using namespace std;
    unsigned int n, m;
    while (cin >> n >> m) {
        if (n < 1 || n > 1024 || m < 1 || m > 1024) {
            cout << -1 << endl;
        }
        else {
            if (n == m) {
                cout << 1 << endl;
            }
            else {
                cout << 0 << endl;
            }
        }
    }
    return 0;
}

发表于 2017-06-28 15:22:32 回复(9)
#include<bits/stdc++.h>
using namespace std;

void test()
{
    int id1, id2;
    cin >> id1 >> id2;
    if(id1 > 1024 || id1 < 1 || id2 > 1024 || id2 < 1)
    {
        cout << -1 << endl;
        return ;
    }
    unsigned int arr[32];  // 用 32 个 unsigned int 来记录任务是否已完成
    // 先找出这个 id 属于第几个 unsigned int 元素
    int id1_index = id1 / 32;  // 例如: 第 34 个任务 34/32 = 1, 下标为 1
    // 再找出这个任务属于这个元素的第几个比特位
    int id1_bits = id1 % 32;  // 34 % 32 = 2, 下标为 1 的元素的第 2 个比特位
    // 将这个比特位置为 1, 代表任务 id1 已结完成
    arr[id1_index] |= (1 << (id1_bits - 1) );
    
    // 再找出任务 id2 的下标和比特位
    int id2_index = id2 / 32;
    int id2_bits = id2 % 32;
    // 判断这个位是否为 1
    if( ((arr[id2_index] >> (id2_bits-1)) && 1) == 1)
    {
        cout << 1 << endl;
    }
    else
    {
        cout << 0 << endl;
    }
}

int main()
{
    test();
}

发表于 2018-09-03 15:45:25 回复(0)
//位图基础知识请见:http://blog.csdn.net/billcyj/article/details/78948977 #include <iostream>
#include <algorithm>
#define N 1024
using namespace std;

int main()
{
    int ID1,ID2;
    while(cin>>ID1&&cin>>ID2)
    {
        if(ID1<1||ID1>1024||ID2<1||ID2>1024)
        {
            cout<<-1<<endl;
            continue;
        }

        //32*32=1024,32个unsigned int刚好可以存放1024个1、0数据
        unsigned int arr[32];
        /*位运算
        arr[(ID1-1)>>5]:先将[1,1024]变成[0,1023],所以ID1-1
        再把ID1-1除以32,也就是右移5位,得到ID1-1在arr中的索引号
        把ID1-1对32求余,也就是&31(对于2的幂才能这样干),得到其
        在该索引中的位号,在将1移动该位号的长度,再把arr[(ID1-1)>>5]
        和(1<<(ID1-1)&31)做或运算,最后复制给等式左边。*/
        arr[(ID1-1)>>5]|=(1<<((ID1-1)&31));
        //拿ID2来验证是否已完成该任务
        cout<< ((arr[(ID2-1)>>5]&(1<<((ID2-1)&31)))!=0) <<endl;
    }
    return 0;
}

发表于 2018-01-02 16:13:17 回复(1)
Java 基本包里面没有无符号整数啊。。。开long的话就是64位了
发表于 2021-03-27 14:46:05 回复(0)
这个题按我的理解就是这么简单,但总感觉有什么阴谋😑
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int id1 = sc.nextInt();
        int id2 = sc.nextInt();
        if(id1 < 1 || id1 > 1024 || id2 < 1 || id2 > 1024){
            System.out.println(-1);
        }else{
            if(id1 == id2)
                System.out.println(1);
            else
                System.out.println(0);
        }
    }
}


发表于 2021-02-05 23:51:48 回复(1)
感觉用位图做是正解,32个int型刚好是128个字节,128*8 = 1024

import java.util.Scanner;

public class Main {

    private byte[] bytes = new byte[128];

    public int getValue(int n, int m) {
        if (n < 0 || n > 1023 || m < 0 || m > 1023) {
            return -1;
        }
        bytes[n/8] = (byte) (bytes[n/8] | 0b00000001 << (n%8));
        byte temp = bytes[m/8];
        if ((temp << (7-m%8)) >> m%8 == -1) {
            return 1;
        }
        return 0;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt()-1; int m = sc.nextInt()-1;
        Main t1 = new Main();
        System.out.println(t1.getValue(n, m));
    }
}
发表于 2020-08-01 22:24:52 回复(0)
importsys
arr=list(map(int,sys.stdin.readline().strip().split()))
ifarr[1]==arr[0]:
    print("1")
elifarr[0]<1orarr[0]>1024:
    print("-1")
elifarr[1]<1orarr[1]>1024:
    print("-1")
elifarr[1]!=arr[0]:
    print("0")

发表于 2019-04-07 16:40:31 回复(0)
# python3 解法
# 运行时间:20ms
# 占用内存:3556k
import sys
t1, t2 = list(map(int, input().split()))
task = [0] * 32
if t1 in range(1, 1025) and t2 in range(1, 1025):
    index1 = int((t1-1)/32)
    index2 = (t1-1)%32
    if not task[index1] & (1<<index2): 
        task[index1] = task[index1] + 1<<index2
    index1 = int((t2-1)/32)
    index2 = (t2-1)%32
    if task[index1]&(1<<index2):
        print(1)
    else:
        print(0)
else:
    print(-1)

发表于 2018-09-03 15:31:47 回复(0)
我喜欢看简单粗暴的解决方法
发表于 2018-08-30 23:37:26 回复(0)
import java.util.Scanner;

public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int first=sc.nextInt();
        int second=sc.nextInt();
        System.out.println(check(first,second));
    }
    public static int check(int first,int second){
        if (first>=1&&first<=1024&&second>=1&&second<=1024){
            if(first==second){
                return 1;
            }
            else{
                return 0;
            }
        }
        else{
            return -1;
        }
    }
}

发表于 2018-06-27 14:49:41 回复(0)
#include<iostream>
using namespace std;
 
int main()
{
    unsigned int n1,n2;
    cin>>n1>>n2;
    if(n1<1 || n1>1024 || n2<1 || n2>1024)
        cout<<-1;
    elseif(n1==n2)
        cout<<1;
    else
        cout<<0;
    return 0;
}

发表于 2018-06-13 23:22:32 回复(0)




int main()
{
//begin();
int a,b;
cin>>a>>b;
if((a>1024)||(b>1024))
{
cout<<-1<<endl;
return 0;
}
if(a==b)
{
cout<<1<<endl;
}
else
{
cout<<0<<endl;
}
return 0;
}
皮一下我很开心
编辑于 2018-04-20 20:23:03 回复(0)
#include <iostream>
using namespace std;
int main() {
    unsigned int n,m;
    while (cin>>n>>m)
        if (n<1||n>1024||m<1||m>1024)
            cout<<-1<<endl;
        else if (n==m) cout<<1<<endl;
        else cout<<0<<endl;
}

发表于 2017-10-29 11:34:41 回复(0)
//如果按照题目的思路,那就是大小为32的Unsigned int数组来存储标记
//Unsigned int刚好是32位,32*32=1024,数组的每一位用二进制表示不同的32个ID
//1表示已完成,0表示未完成,用&符号来判断任务是否完成,即二进制的那一位是否为1
//题目的bug在于好像不是多行输入。。。所以取巧的话可以直接判断输入的两位数字是否相等 #include<iostream>
#include<cstdio>
using namespace std;
unsigned int a[32];
int main(){
    int ID1,ID2;
    while(scanf("%d%d",&ID1,&ID2)!=EOF){
        if(ID1<1||ID1>1024||ID2<1||ID2>1024){
            cout<<-1<<endl;
            continue;
        }
        int index=(ID1-1)/32;
        int temp=(ID1-1)%32;
        a[index]+=1<<temp;
        index=(ID2-1)/32;
        temp=(ID2-1)%32;
        if(a[index]&(1<<temp))
            cout<<1<<endl;
        else
            cout<<0<<endl;
    }
    return 0;
}

发表于 2017-09-21 14:09:08 回复(0)