输入包括一行,两个整数表示任务ID.
输出是否完成
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)); 即可。 */
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 } }
//头一次发代码,略鸡冻 //话说那么多人直接几个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; } }
看到有些牛友只是考虑了输入一次时的情况,感觉不太对 我认为这道是要连续输入的,要不然我只需判断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; }
#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; }
#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; }
#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(); }
//位图基础知识请见: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;
}
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); } } }
importsysarr=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")
# 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)
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; } } }
//如果按照题目的思路,那就是大小为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;
}