[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
又证
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
(第一次写,写的不好请见谅,溜了溜了)