[NOIP模拟题] 位运算入门详解+富有诗意的模拟题

位运算

就是二进制下数的运算。。

1. and 运算 “&”

对于数 A , B 在二进制下的任意第 i 位 Ai,Bi, 当且仅当 Ai=Bi=1 时,Ai & Bi=1

1101 & 100 :

1 1 0 1

& 0 1 0 1

0 1 0 1

一般用于二进制取位操作,例如一个数 and 1的结果就是取二进制的最末位,

A & (1<<X) = 取出二进制下 A 的末第 X-1 位

2. or 运算 “ | ”

对于数 A , B 在二进制下的任意第 i 位 Ai,Bi, 当 Ai=1 或 Bi=1 时,Ai | Bi=1

or运算通常用于二进制特定位上的无条件赋值,对二进制任意一位 or 1 就等于将这

一位赋值为 1

1101 | 100 :

1 1 0 0 1

or 1 0 0 1 1

1 1 0 1 1

3. xor 运算 "^"

对于数 A , B 在二进制下的任意第 i 位 Ai,Bi, 当 Ai=Bi 时,Ai ^ Bi=0,

Ai !=Bi 时,Ai ^ Bi=1 按位异或运算, 对等长二进制模式按位或二进制

数的每一位执行逻辑按位异或操作. 操作的结果是如果某位不同则该位为1,

否则该位为 0

00101 ^ 11100 :

0 0 1 0 1

^ 1 1 1 0 0

1 1 0 0 1

一件美妙的事情,xor运算的逆运算是它本身

就是 (A xor B) xor B = A

所以,我们得到了一个神奇的swap的过程:

void swap(int &a,int &b)
{
    a = a ^ b;
    b = a ^ b;
    a = a ^ b;<br />    return;
}

注意: 在交换两个数时,若出现 a == b 的情况 ,就会翻车

因为任意一个数 XOR 本身 都会得到 0

4. not 运算 "~"

取反,顾名思义 若 A = "10010" , B=~A,那么 B = "01101"

使用 not 运算时要格外小心,你需要注意整数类型有没有符号。如果 not 的对象是无符号整数(不能表示负数的那种)

那么会得到它与上界的差。

int main()
{
    unsigned short a=;
    a = ~a;
    printf( "%dn", a );    
    return ;
}

这其中的输出的 a = 65435.

若对于有符号的整数,计算机用 00 到 $7FFF 依次表示 0 到 32767 的数,剩下的 $8000 到 $FFFF 依次表示 -32768 到 -1 的数。

32位有符号整数的储存方式也是类似 的。稍加注意你会发现,二进制的第一位是用来表示正负号的,0表示正,1表示负,那么

对于 0 来说,他不属于整数或负数,但是占用了 00 的位置,所以导致该范围中正数比负数少一个,对一个有符号的数进行not运算

后,最高位的变化将导致正负颠倒,并且数的绝对值会差1。

所以 not a实际上等于 -a-1(或 -a= not a+1)。这种整数储存方式叫做“补码”(正数的补码和原码相同,负数的补码是该数的绝对值的

二进制形式,按位取反后再加 1)。

5. shl运算 “ <<”和 shr 运算 “>>”

A << B 等于将 A 向左移 B 位(在二进制 A 后面添上 B 个0),A >> B 等于将 A 向右移 B 位(去掉最后 B 位)

所以 A << B = A *2B , A >> B= A / 2B (整除)

主要用于代替代码中连续乘除 2 的运算,要快一丢丢(二分查找,堆的插入)。

常用的就这么几个,按运算优先级排为

1 ~ not

2 << , >> shl ,shr

3 & and

4 ^ xor

5 | or

6 |= , &= , ^= .........


例题T1

(很诗意。。。)

信(believe.cpp/c/pas)

背景描述:

一切死亡都有冗长的回声—— 《一切》北岛

给定一个N个元素的序列A,

定义Bi = (Ai and A1)+ (Ai and A2) + (Ai and A3)+ ...... + (Ai and An)

定义Ci = (Ai or A1)+ (Ai or A2) + ... + (Ai or An)

求B和C序列。

输入格式:

第一行一个整数N表示序列长度

接下来一行N个整数, 第i个整数为Ai

输出格式:

第一行N个整数输出B序列

第二行N个整数输出C序列

样例输入:

4

3 5 1 1

样例输出:

6 8 4 4

16 22 10 10

数据规模:

对于50%的数据, N <= 1000

对于100%的数据, N <= 100000, Ai <= 100000

题目大意:

B , 对于每一个 Ai ,求 Ai 与每一个 A 的 & 值的和

C , 对于每一个 Ai ,求 Ai 与每一个 A 的 | 值的和

分析:

朴素算法,枚举 Ai,再枚举 Aj ,直接计算,复杂度 O(n2),能拿一半的分(暴力出奇迹)

正解:

因为B[i]=(Ai and A1)+ (Ai and A2) + (Ai and A3)+ ...... + (Ai and An)

假设两个数 X , Y . 因为 & 运算的值只与参与运算的两个二进制数相同的那一位有关

X.1 & Y.1 + X.2 & Y.2+.....+ X.n & Y.n = X & Y (将 Y 的二进制拆分成每一位后逐一计算,值相等)

所以,我们只需要统计A1-An中二进制每一位上 1 的出现次数(0就不管了,任意一个数 & 0=0)sum[i]

如果 Ai.i =1 , B[i].i = sum[i]*(1<<i ); /*&值乘以出现次数*/ 若 Ai.i = 0, 那就 =0;

把每一位的值相加,就得到 B[i] 了

同理,对于 C[i] 也可以这样拆分,不同的是,

若 C[i].i=1 那么 这一位 or 每一个Aj.i = 1, C[i].i = n*(1<<i);

若 C[i].i=0 那么就要考虑第 i 位上出现 1 的次数 (同sum[i]) C[i].i = sum[i]*(1<<i);,再把每一位累加。

代码如下 复杂度 O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define pr(x) printf("%lld ",x)
#define sc(x) scanf("%lld",&x)
#define go(i,x,a) for(int i=a;i<x;i++)
#define ll long long
using namespace std;
ll n,map[100005],sum[20]; 
ll b[100005],c[100005]; 
int main()
{
   cin>>n;
   go(i,n,0)
   {
         sc(map[i]);
         go(j,20,0)  
            if(map[i]&(1<<j)) sum[j]++;//统计第j位 1 的出现次数 
   }
   go(i,n,0)
   {
         go(j,20,0)
         {
              if(map[i]&(1<<j)) // map[i]的第j位=1 
              {
                   b[i]+=sum[j]*(1<<j);
                   c[i]+=n*(1<<j);
         }
         else {           // map[i]的第j位=0 
             c[i]+=sum[j]*(1<<j);
         }
      }
   }
   go(i,n,0) pr(b[i]); printf("\n");
   go(i,n,0) pr(c[i]);
   return 0;
}//ME.FORY

例题T2

(搞不懂这些人为什么非要加一句诗)

题(problem.cpp/c/pas)

背景描述:

黑夜给了我黑色的眼睛

我却用它寻找光明 ——《一代人》 顾城

已知一个N个元素的非负整数序列A,

定义Bi = (Ai and A1)+ (Ai and A2) + (Ai and A3)+ ...... + (Ai and An)

定义Ci = (Ai or A1)+ (Ai or A2) + ... + (Ai or An)

给出B和C序列, 构造一个满足条件的A序列, 如果没有, 输出-1

输入格式:

第一行一个整数N。

接下来一行N个整数表示B序列

接下来一行N个整数表示C序列

输出格式:

如果有解, 输出一行N个整数表示你构造的A序列, SPJ很脆弱, 所以你构造的序列每个整数必须在[0,8191]这个区间内, 我们保证如果有解, 那么定存在一个解满足每个元素均在[0,8191]内,否则输出-1

样例输入:

4

6 8 4 4

16 22 10 10

样例输出:

3 5 1 1

数据规模:

对于30%的数据, N = 2

对于70%的数据, N <= 200

对于100%的数据, N <= 100000, Bi , Ci<= 1000000000

题目大意:

和第一题正好反过来,但要考虑无解和超出范围的问题

分析:

在那遥远的地方,有一个神奇的式子

对于任何非0 A , B 有 A & B + A | B = A + B

[NOIP模拟题]  位运算入门详解+富有诗意的模拟题

又证

C[i] + B[i] = (A[i] & A[1])+(A[i] | A[1])+(A[i] & A[2])+(A[i] | A[2])+......

= (A[i] + A[1])+(A[i] + A[2])+(A[i] + A[3])+...

= n*A[i] + ∑(A[i])

所以 ∑(C[i] + B[i])= 2*n*(A[i])

在读入的同时我们可以直接得到 ∑(A[i]), 再有 C[i] + B[i]-∑(A[i]) = n*A[i]

直接得到每一个 A[i] 就OK了

注意:

注意判断 A[i] 是否大于 8191 和无解的情况,当任意一步计算时不能整除则无解

注意变量要开long long,输出不能用 cout ,否则会超时

代码如下: 复杂度O(n)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<algorithm>
#define pr(x) printf("%lld ",x)
#define sc(x) scanf("%lld",&x)
#define go(i,x,a) for(int i=a;i<x;i++)
#define ll long long
#define p_q priority_queue
#define maxx  8191*n
#define MM 100005
using namespace std;
ll n,map[MM],b[MM],c[MM],tt=; 
int main()
{
   cin>>n;
   go(i,n,)  
   {
        sc(b[i]);
        tt+=b[i];
   }
   go(i,n,)  
   {
       sc(c[i]);
       tt+=c[i];//  累加 
   }
   if(tt%!=||tt%n!=)// 判断是否无解 
   {
         cout<<"-1";
         return ;
   } 
   tt=(tt/)/n;
   if(tt>maxx) 
   {
         cout<<"-1";
         return ;
   } 
   go(i,n,)
   {
         map[i]=b[i]+c[i]-tt;
         if(map[i]%n!=||map[i]>maxx) 
         {
             cout<<"-1"; return ;    
      }
         map[i]=map[i]/n; //   直接计算 
   }
   go(i,n,) pr(map[i]);
   return ;
}//ME.FORY

(第一次写,写的不好请见谅,溜了溜了)

相关推荐