位運算
應用
- 快速冪
- 標記狀態 —— 動態規劃
- 用異或實作配偶
lowbit運算
| 功能 | 示例 | 位運算 | 運算子 |
|---|---|---|---|
| 去掉最后一位 | (101101->10110) | x shr 1 | x>>1 |
| 在最后加一個0 | (101101->1011010) | x shl 1 | x<<1 |
| 把最后一位變成1 | (101100->101101) | x or 1 | x|1 |
| 最后一位取反 | (101101->101100) | x xor 1 | x^1 |
| 取末三位 | (1101101->101) | x and 7 | x&7 |
1 << n 1 左移 n 位 ——> 2n
n >> x n 右移 x 位 ——> n / 2x
快速冪
求 mk%p，時間復雜度 O(log k)，
int qmi(int m, int k, int p) {
int res = 1 % p, t = m;
while (k) {
if (k & 1) res = res * t % p * 1ll;
// *1ll 將 int 型別轉化為 long long
t = t * 1ll * t % p;
k >>= 1;
}
return res;
}
91.最短Hamilton路徑
給定一張 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 ] ≤ 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
代碼：
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 20, M = 1 << 20;
int mg[N][N], f[M][N];
int main() {
int n;
cin >> n;
for (int i = 0; i < n; ++i)
for (int j = 0; j < n; ++j)
cin >> mg[i][j];
memset(f, 0x3f, sizeof f);
f[1][0] = 0;
for (int i = 0; i < 1 << n; ++i) //第一層狀態為過不過i點
for (int j = 0; j < n; ++j) //第二層狀態為終點為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] + mg[k][j]);
cout << f[(1 << n) - 1][n - 1] << endl;
return 0;
}
用異或實作配偶
e[index]
e[index ^ 1]
lowbit運算
// lowbit(1110010000) = 10000
int lowbit(int n) {
//return (~n + 1) & n;
return (-n) & n;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/254104.html
標籤：其他