0x是十六進制常數的開頭；本身是聲明進制，后面是對應具體的數；

數組初始化最大值時用0x3f賦值；

移位運算

左移

把二進制下的數左移低位以0填充

1<<n=2ⁿ n<<1=2n

算數右移

把二進制下的數右移 高位以符號位填充，低位舍棄

相當于除以二向下取整：(-3)>>1=-2，3>>1=2；

與/2不同的點在于/2時是向0取整 (-3)/2=-1；

優先級

+,- > <<,>> > <,>,==,!= > &(位與) > ^(異或) > |(位或)

不確定就加括號！

一些位運算的操作

以N=84，a=5，b=3為例；

換為二進制表示為N=0101 0100，a=0101，b=0011

~（按位非）：將二進制數的每一位都取反

? ~N=1010 1011 ~a=1010 ~b=1100

&（按位與）：比較兩個二進制數的每一位；同時為1時記錄為1

? a&b=0001

? ((~N)+1)&N=0000 0100

|（按位或）：比較兩個二進制數的每一位；只要有1就記錄為1，同時為0才是0

? a|b=0111

? N|(~N)=1111 1111

^（異 或）：比較兩個二進制數的每一位；相同記為0，不同記為1

? N^(~N)=1111 1111

? a^b=0110

最短 Hamilton 路徑（狀態壓縮dp模板，位運算）

題目原文

P10447 最短 Hamilton 路徑 - 洛谷

一張 n 個點的帶權無向圖，求起點 0 至終點 n?1 的最短 Hamilton 路徑（從 0～n?1 不重復地經過每個點一次）。

思路分析

如果暴力去遍歷的話時間復雜度是O(n*n!)顯然會超時；所以這里就可以利用位運算；用二進制的每一位來代表是否選取過這個點；

這樣枚舉的次數就降到了2ⁿ；就可以通過這道題了；
初始時建立a數組存儲點i和點j之間的距離；
再利用f數組進行狀態轉移的模擬；最后求得的f[(1<<n)-1][n-1]即為最小距離；

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N=21;
int a[N][N];
int f[1<<N][N];
signed main(){int n;cin>>n;for(int i=0;i<n;i++)for(int j=0;j<n;j++)cin>>a[i][j];memset(f,0x3f,sizeof f);f[1][0]=0;for(int i=1;i<1<<n;i++){ // 枚舉所有情況for(int j=0;j<n;j++){ // 遍歷每個點if(i>>j&1) //可以到達for(int k=0;k<n;k++){ // 找下一步準備去的點if((i^(1<<j))>>k&1) //(i^(1<<j)是為了把j的哪一位先去掉，避免jk重復f[i][j]=min(f[i][j],f[i^(1<<j)][k]+a[j][k]);}}}cout<<f[(1<<n)-1][n-1];
}

---