hdu 6085 Rikka with Candies (set计数)

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

5 5 5

1 2 3 4 5

0 1 2 3 4

Sample Output

给你一个长度为n的a数组,m的b数组,再给你q个询问,每个询问为一个k,问在a b 数组中满足 a[i]%b[j]=k的i,j有多少对,答案对2取模.保证a b 中的数组不会重复.

答案对2取模的话就提示你在用bitset来加速处理.我们先对询问排一个序,b数组排一个序.我们先用一个aa的bitset存下a数组中出现的数字

bb存b[j]的倍数,因为如果[i]%b[j]=k,那么b[j]应该是>k的.然后对已每一个询问不断更新bb也就是不断加上下一个较小的b[j]

对于每一个询问的结果我们只需要(((aa>>q[i].k)&bb).count())&1;这样就是答案了

代码如下:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int BufferSize=1<<16;
 4 char buffer[BufferSize],*head,*tail;
 5 inline char Getchar() {
 6     if(head==tail) {
 7         int l=fread(buffer,1,BufferSize,stdin);
 8         tail=(head=buffer)+l;
 9     }
10     return *head++;
11 }
12 inline int read() {
13     int x=0,f=1;char c=Getchar();
14     for(;!isdigit(c);c=Getchar()) if(c=='-') f=-1;
15     for(;isdigit(c);c=Getchar()) x=x*10+c-'0';
16     return x*f;
17 }
18 inline void write(int x)
19 {
20     if(x>=10)write(x/10);
21     putchar(x%10+'0');
22 }
23 const int maxn = 55000;
24 int n,m,qu;
25 int a[maxn],b[maxn];
26 int ret[maxn];
27 bitset<maxn> aa,bb;
28 struct query
29 {
30     int k,id;
31 }q[maxn];
32 bool cmp (query q1,query q2)
33 {
34     return q1.k>q2.k;
35 }
36 int main()
37 {
38     //freopen("de.txt","r",stdin);
39     int T;
40     T=read();
41     while (T--){
42         n=read(),m=read(),qu=read();
43         aa.reset();
44         bb.reset();
45         for (int i=1;i<=n;++i){
46             a[i]=read();
47             aa.set(a[i]);
48         }
49         for (int i=1;i<=m;++i)
50             b[i]=read();
51         sort(b+1,b+1+m);
52         for (int i=1;i<=qu;++i)
53             q[i].k=read(),q[i].id=i,ret[i]=0;
54         sort(q+1,qu+1+q,cmp);
55         int now = m+1;
56         for (int i=1;i<=qu;++i){
57             while (now-1>=1&&b[now-1]>q[i].k){
58                 now--;
59                 for (int j=0;j<=50000;j+=b[now])//枚举b[now]的倍数,从0开始
60                     bb[j]=bb[j]^1;
61             }
62             ret[q[i].id] =(((aa>>q[i].k)&bb).count())&1;
63         }
64         for (int i=1;i<=qu;++i)
65             write(ret[i]),putchar(10);
66     }
67     return 0;
68 }

加上快速读入3400ms左右,时限是3500...

hdu 6085 Rikka with Candies (set计数)

相关推荐