2728: [HNOI2012]与非

Time Limit: 10 Sec  Memory Limit: 128 MB

Submit: 813  Solved: 389

Description

Input

输入文件第一行是用空格隔开的四个正整数N，K，L和R，接下来的一行是N个非负整数A1,A2……AN，其含义如上所述。 100%的数据满足K≤60且N≤1000,0<=Ai<=2^k-1,0<=L<=R<=10^18

Output

仅包含一个整数，表示[L,R]内可以被计算出的数的个数

Sample Input

3 3 1 4

3 4 5

Sample Output

4

HINT

样例1中，(3 NAND 4) NADN (3 NAND 5) = 1，5 NAND 5 = 2，3和4直接可得。

Source

 

 

【分析】

　　看错题了。。这题也好迷人啊。。。

给定k位二进制下的n个数，求[l,r]区间内有多少个数能通过这几个数与非得到

首先观察真值表 我们有A nand A = not A

然后就有not ( A nand B ) = A and B

与和非都弄到了，我们就可以做出一切逻辑运算了，比如说或和异或

A or B = not ( ( not A ) and ( not B ) )

A xor B = ( A or B ) and ( A nand B )

然后我们对于位运算可以发现一个性质

对于某两位来说，如果对于每一个数，这两位上的值都是相同的，那么这两位无论怎么计算最终结果都会是相同的

比如说10(1010)和7(0111)，第一位和第三位都是相同的，所以最后无论怎么计算，这两位都是一样的

然后我们这么处理：

对于每一位，我们枚举每一个数，若该数该位上为0，我们就对这个数取非

然后把所有数取与

该位上都是1，所以取与后一定是1；对于其他位，只要有这两位不同的数存在，那么这位一定是0

最后取与的结果中与该位全部相同的位都是1，其余都是0

对于每一位这样处理，标记去重，然后可以得到线性基，保证每一位存在且仅存在于线性基中的一个数上

拿去从大到小贪心处理即可 得到二进制序列即为答案

特判L=0

来自：

 

 

　　~和！不同，~是把二进制数每一位取反。

 

1 #include
       
         2 #include
        
          3 #include
         
           4 #include
          
            5 #include
           
             6 using namespace std; 7 #define LL long long 8 #define Maxn 1010 9 10 LL a[Maxn],w[Maxn];11 int tot;12 bool vis[Maxn];13 14 LL get_ans(LL x)15 {16     if(x==-1) return -1;17     LL now=0,ans=0;18     for(int i=1;i<=tot;i++)19     {20         if((now|w[i])<=x)21         {22             now|=w[i],ans+=(1LL<
            
             =0;j--) if(!vis[j])37 {38 LL now=tt;39 for(int i=1;i<=n;i++)40 if(a[i]&(1LL<
            
           
          
         
        
       

 

2017-04-06 19:36:34