HDU 6085 bitset Rikka with Candies

Time Limit: 7000/3500 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1452 Accepted Submission(s): 634

Problem Description

As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:

There are

.

But It is still too difficult for Rikka. Can you help her?

Input

The first line contains a number

Output

For each query, print a single line with a single

digit -- the answer.

Sample Input

1 5 5 5 1 2 3 4 5 1 2 3 4 5 0 1 2 3 4

Sample Output

0 0 0 0 1

Source

2017 Multi-University Training Contest - Team 5

 1 #pragma comment(linker, "/STACK:1024000000,1024000000")
 2 #include<iostream>
 3 #include<cstdio>
 4 #include<cmath>
 5 #include<string>
 6 #include<queue>
 7 #include<algorithm>
 8 #include<stack>
 9 #include<cstring>
10 #include<vector>
11 #include<list>
12 #include<set>
13 #include<map>
14 #include<bitset>
15 #include<time.h>
16 using namespace std;
17 int t;
18 int n,m,q;
19 bitset<50004> a,b,ans,exm;
20 int main(){
21     scanf("%d",&t);
22     for(int i=1;i<=t;i++){
23         scanf("%d %d %d",&n,&m,&q);
24         a.reset();
25         b.reset();
26         int maxn=0;
27         int x;
28         for(int j=0; j<n;j++){
29           scanf("%d",&x);
30           a.set(x);
31         }
32         for(int j=0;j<m;j++){
33             scanf("%d",&x);
34             b.set(x);
35             maxn=max(maxn,x);
36         }
37         exm.reset();
38         ans.reset();
39         for(int j=maxn;j>=0;j--){
40             ans[j]=(exm&(a>>j)).count()&1;//ans[j]:(a-j)%b==0的个数的奇偶性
41             if(b[j]){
42                 for(int k=0;k<=50000;k+=j)
43                  exm.flip(k);
44             }
45         }
46         for(int j=1;j<=q;j++){
47             scanf("%d",&x);
48             printf("%c
",ans[x]?'1':'0');
49         }
50     }
51     return 0;
52 }

HDU 6085 bitset Rikka with Candies

相关推荐