20161005 NOIP 模拟赛 T3 解题报告

subset

3.1 题目描述

　　　　一开始你有一个空集，集合可以出现重复元素，然后有 Q 个操作
　　　　1. add s 在集合中加入数字 s。

　　　　2. del s 在集合中删除数字 s。保证 s 存在

　　　　3. cnt s 查询满足 a&s = a 条件的 a 的个数
3.2 输入

　　　　第一行一个整数 Q 接下来 Q 行，每一行都是 3 个操作中的一个

3.3 输出

　　　　对于每个 cnt 操作输出答案
3.4 Sample Input

　　　　add 11

　　　　cnt 15

　　　　add 4

　　　　add 0

　　　　cnt 6

　　　　del 4

　　　　cnt 15
3.5 Sample Output

　　　　1 2 2
3.6 数据范围及约定

　　　　对于 30% 的数据满足：1 ≤ n ≤ 1000

　　　　对于 100% 的数据满足，1 ≤ n ≤ 200000 , 0 < s < 2¹⁶。

————————————————分割线————————————————

分析：

　　对于30%的数据直接模拟cnt每次扫一遍即可。

　　对于100%的数据，上述算法主要在cnt统计上较慢，那么可以找&运算的规律，即同一得一。

　　我们可以生成一些数，使得它满足 a&s=a , 在看它之前是否出现过，如此一来，之前算法的速度有显著提升。

代码&注释：

 1 #include "bits/stdc++.h" 
 2 
 3 using namespace std ;
 4 const int maxN = 100010 ;
 5 typedef long long QAQ ;
 6 
 7 char op[ 10 ] ;
 8 
 9 QAQ Ans ;
10 int buc [ maxN ] ;
11 
12 void Creat ( int Bit , int x , int k ) {
13         if ( x==0 ) {//拆分完
14                 Ans += buc[ k ] ;//统计
15                 return ;
16         }
17         else {
18                 int t = x % 2 ;//二进制拆分 
19                 if ( t==1 ) {//最后一位是一则生成数对应位置可以为1或0 
20                         Creat ( Bit + 1 , x / 2 , k ) ;
21                         Creat ( Bit + 1 , x / 2 , k + ( 1 << Bit ) ) ;
22                 }
23                 else {//只能为1 
24                         Creat ( Bit + 1 , x / 2 , k ) ;
25                 }
26         }
27 }
28 int main ( ) {
29         int T , N ; 
30         freopen ( "subset.in","r",stdin) ;
31         freopen ( "subset.out","w" , stdout ) ;
32         scanf ( "%d" , &T ) ;
33         while ( T-- ) {
34                 scanf ( "%s %d" , op , &N ) ;
35                 if ( op[ 0 ]=='a' ) ++ buc[ N ] ;
36                 else if ( op[ 0 ]=='d' ) -- buc[ N ] ;
37                 else if ( op[ 0 ] == 'c' ) {
38                         Ans = 0 ;
39                         Creat ( 0 , N , 0 ) ;
40                         printf ( "%I64d
" , Ans ) ;
41                 }
42         }
43         return 0 ;
44 }

View Code

NOIP_RP++;

2016-10-06 21:18:29

(完)