[NOIP模拟题] 位运算入门详解+富有诗意的模拟题
松鼠的窝 2017-11-29
位运算
就是二进制下数的运算。。
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模拟题] 位运算入门详解+富有诗意的模拟题](https://cdn.ancii.com/article/image/v1/I2/rz/TY/YTr2zIFHT1VxQyWDl1hfDlXS7CekulRK1O6rDXfrJ59HsGpRM2pNCFIoQ1Corud9gLkmhYTQ_hIthCvCTl4RzFIXv3NO4kLgMl7qiWk93NB2xaJC5AAb0eFdRdbvDw5u.png "[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（第一次写，写的不好请见谅，溜了溜了）
