本文共 4283 字,大约阅读时间需要 14 分钟。
再谈位运算
位运算基础:
基本运算:
与 : x & y | 只要有一个为 0 即为 0, 都为 1 为 1 |
---|---|
或: x | y | 只要有一个为 1 即为 1, 都为 0 为 0 |
非 : ! x | 取反 |
异或 : x ^ y | 加法不进位, 相同为0, 不同为1 |
int 32位
:
1: 0000000000…1
2: 0000000000…10
3: 0000000000…11
补码: 一个数与 x 相加 为 0, 则这个数即为 x 的补码, 等于 x 取反 + 1, 也可以用 0 减去 x 得到
1 + x = 0000000000000000
1 + 1111111111111111111 = 0000000000…00
2 + 1111111111111111110 = 0000000000…00
x + ? = 000000000000…00
? 即为 x 的补码 :
求? : ? = ~x + 1
由此可得: -n = ~n + 1
优点 : 根据此原理在计算机中可以通过加法来实现减法
例子:
初始化数组为正无穷 : memset(f, 0x3f, sizeof (f) );
memset是按字节进行复制, int数组每个元素为 4 个字节, 故复制后每个元素为 0x3f3f3f3f
当数组中两个元素相加的时候, 0x3f3f3f3f * 2 < 0xffffffff
此时不会发生溢出错误
重要运算: 位运算
左移: 1 << n = 2 n 2^n 2n
右移: n >> x = n ÷ 2 x n \div {2^x} n÷2x 当右移的时候, 最左边的数被移除, 最高位补齐, 算术右移为补上它的符号位, 负数补1, 正数补0
例题解析:
1. a ^ b
求 a 的 b 次方对 p 取模的值。
输入格式
三个整数 a,b,p,在同一行用空格隔开。
输出格式
输出一个整数,表示a^b mod p
的值。
数据范围
0 ≤ a , b ≤ 1 0 9 0 \le a,b \le {10^9} 0≤a,b≤109
1 ≤ p ≤ 1 0 9 1 \le p \le {10^9} 1≤p≤109输入样例:
3 2 7
输出样例:
2
思路 : 快速幂, 将 b 拆分成二进制, 通过右移操作查看 b 的每一位, 同时 a 左移, 如果此位为 1 就乘上 a
**代码如下 : **
#includeusing namespace std ; int main() { int a, b, p ; cin >> a >> b >> p ; int res = 1 % p ; // 这里 mod p 是为了防止 b 为 0, p 为 1 这组数据 while (b) { if (b & 1) res = res * 1ll * a % p ; // 这里乘 1ll 的目的是将res转换为长整型, 防止溢出 a = a * 1ll * a % p ; b >>= 1 ; } cout << res << endl ; return 0 ; }
2. 64位整数乘法
求 a 乘 b 对 p 取模的值。
输入格式
第一行输入整数a,第二行输入整数b,第三行输入整数p。输出格式
输出一个整数,表示a*b mod p的值。数据范围
1≤a,b,p≤ 1 0 18 {10^{18}} 1018输入样例:
3 4 5 输出样例: 2
思路: 快速幂思想, 两个64位的数相乘为128位, 必然溢出, 相加不溢出 --> 把乘法变成加法
a * b
a + a + a + … + a
a * 1 = a
a * 2 = 2a = a + a
a * 4= 4a = 2a + 2a
a * 8 = 8a = 4a + 4a
…
a * (2 ^ k) = 2^k * a
代码如下:
#includeusing namespace std ;typedef unsigned long long ULL ;int main(){ ULL a, b, p ; cin >> a >> b >> p ; ULL res = 0 ; while (b) { if (b & 1) res = (res + a) % p ; b >>= 1 ; a = (a + a) % p ; // a * 2 % p 也可 } cout << res << endl ; return 0 ;}
3.最短Hamilton路径 (NP完全问题)
旅行商问题
NP完全问题: NP完全问题(NP-C问题),是之一。 NP的英文全称是Non-deterministic Polynomial的问题,即复杂程度的问题。简单的写法是 NP=P?,问题就在这个上,到底是NPP,还是NP不等于P。
因此只能通过暴力 (直接暴力会TLE) 优化的方法求解
给定一张 n 个点的带权无向图,点从 0∼n−1 标号,求起点 0 到终点 n−1 的最短 Hamilton 路径。
Hamilton 路径的定义是从 0 到 n−1 不重不漏地经过每个点恰好一次。
输入格式
第一行输入整数 n。接下来 n 行每行 n 个整数,其中第 i 行第 j 个整数表示点 i 到 j 的距离(记为 a[i,j])。
对于任意的 x,y,z,数据保证 a[x,x]=0,a[x,y]=a[y,x] 并且 a[x,y]+a[y,z]≥a[x,z]。
输出格式
输出一个整数,表示最短 Hamilton 路径的长度。数据范围
1≤n≤20 0≤a[i,j]≤ 1 0 7 10^7 107输入样例:
5 0 2 4 5 1 2 0 6 5 3 4 6 0 8 3 5 5 8 0 5 1 3 3 5 0 输出样例: 18
思路:
假设遍历 0, 1, 2, 3这四个点
0 -> 1-> 2 -> 3 18
0 -> 1-> 2 -> 3 20
根据以上两种遍历方式可知, 当到第三个点的时候, 此时第一种方式的路径长度比第二种方式的少2
又因为从 3 号点遍历其他剩余的点的可能方式是相同的, 所以接下来第二种方式的每一种遍历方式都会比
第一种方式的遍历方式多 2, 因此 此时我们不需要再遍历第二种方式
两个关键点:
- 哪些点被用过;
- 目前停止哪个点上
第一维状态 : 2^20
第二维状态 : 20
数量 (时间复杂度) --> 2 ^ 20 * 20 = 2 * 10 ^ 7
考虑每个状态怎么被计算:
state表示哪些点被用过, j表示当前停在哪个点上
假设从 k 转移过来:
f[state] [j] = f[state_k] [k] + weight[k] [j], state_k = state除掉 j 之后的集合
集合表示当前状态已经遍历过的点
state_k 里面需要包含 k
状态压缩
用一个二进制的整数来表示我们的 state
是一个20位的整数 00…0
某一位为 1 表示这个点存在, 为 0 表示这个点不存在
假设现在 包含了 0, 1, 4 这三个点
state = 10011
整个程序复杂度 = 状态数量 * 状态转移复杂度
2 * 10 ^ 7 * 20
题目的 时/空限制:5s / 256MB 5s == 5亿次
我们这里程序的复杂度约为 4亿次 能够通过
代码如下:
#include#include #include using namespace std ; const int N = 20, M = 1 << 20 ; int n ; int f[M][N], weight[N][N] ; // 开数组到全局变量, 存到对空间中, 防止栈溢出 爆栈 // 一般较大数组都开为全局变量int main(){ cin >> n ; for (int i = 0;i < n;i ++ ) for (int j = 0;j < n;j ++ ) cin >> weight[i][j] ; memset(f, 0x3f, sizeof f) ; f[1][0] = 0 ; // 初始位置 for (int i = 0;i < 1 << n;i ++ ) for (int j = 0;j < n;j ++ ) if (i >> j & 1) // 判断当前状态是否合法, 判断 i 的第 j 位是否为 1 for (int k = 0;k < n;k ++ ) if (i - (1 << j) >> k & 1) f[i][j] = min(f[i][j], f[i - (1 << j)][k] + weight[k][j]) ; cout << f[(1 << n) - 1][n - 1] << endl ; return 0 ; }
异或 ^
- 实现 成对的 思想
0, 1
2, 3
4, 5
6, 7
0 ^ 1 = 1, 1 ^ 1 = 0
4 ^ 1 = 5, 5 ^ 1 = 4
也就是说将 每一个整数异或 1 即可得到它的配偶
作用: 图论中的最小费用流, 在用数组模拟邻接表存边的时候, 需要存一条边以及其反向边, 此时需要快速求出某一条边的反向边, 一般会将一条边的正向边与反向边放在一起
- lowbit运算
树状数组基础
快速求出一个整数 n 在二进制中最低的一位 1 是哪个
lowbit(11001000) = 1000
00111000
int lowbit(n){ return (-n) & n ; }
转载地址:https://blog.csdn.net/weixin_45877540/article/details/116210941 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!