說點大家知道的

位運算

二進制狀態壓縮

1. 第 k 位： (n>>k)&1
2. 第 0 ~ k-1 位： n&((1<<k)-1)
3. 將第 k 位取反： n xor (1<<k)
4. 將第 k 位設為 1： n|(1<<k)
5. 將第 k 位設為 0： n&(~(1<<k))

成對變換

對于 n 為奇數， n xor 1 = x-1

對于 n 為偶數， n xor 1 = x+1

因此我們可以將 (0,1) , (2,3) ··· 為一對。

lowbit 運算

lowbit(n) = n&(~n+1) = n&(-n)

實際意義:

找出二進制下第一個是1的位置。

lowbit(0b1011011000) = 1000

運算優先級

雙指針

雙指針算法是一種通過設置兩個指針不斷進行單向移動來解決問題的算法。

例題：

給定一個長度為n的數組a和一個整數x，現在要請你在數組中尋找一個區間，使得這個區間的元素之和等于x。這樣的區間存在多個，請按字典序大小輸出。

CODE:

signed main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>a[i];
	cin>>m;
	while(sum<m&&r<n) sum+=a[++r];
	if(r==n) return 0;
	if(sum==m) cout<<l<<' '<<r<<'\n';
	for(r++;r<=n;r++){
		sum+=a[r];
		while(sum-a[l]>=m&&l<=r) sum-=a[l++];
		if(sum==m) cout<<l<<' '<<r<<'\n';
	}
	return 0;
}

前綴和與差分

前綴和

一維：

對于數組 A[]

設置前綴和數組為 \(sum_i=\sum_{j=1}^i {A_j}\)

因此 A[l]+A[l+1]+···+A[r-1]+A[r] = sum[r]-sum[l-1]

二維：

對于數組：A[][]

設置前綴和數組為： \(sum_{i,j}=\sum_{u=1}^i \sum_{v=1}^j A_{u,v}\)

因此 \(\sum_{u=a}^b \sum_{v=c}^d A_{u,v} = sum_{b,d}-sum_{a,d}-sum_{b,c}+sum_{a,c}\)

圖是：

適用場景

查詢區間多，修改少。

差分

對于數組 A[]

設置差分數組為： d[i] = A[i]-A[i-1] (d[1]=A[1])

因此： A[i] = d[1]+d[2]+d[3]+···+d[i]

適用場景

修改多，查詢少。

二分靠左

int ask_l(int k){
	int r=1,l=n;
	while(r<l){
		int mid=(r+l)/2;
		if(a[mid]>=k) l=mid;
		else r=mid+1;
	} 
	if(a[r]==k) return r-1;
	return -1;
}

二分靠右

int ask_r(int k){
	int r=1,l=n;
	while(r<l){
		int mid=(r+l+1)/2;
		if(a[mid]>k) l=mid-1;
		else r=mid;
	} 
	if(a[r]==k) return r-1;
	return -1;
}

二分查找相關函數 若存在序 a{0,1,3,3,3,5,8};

1. binary_search(a+1,a+n+1,x)
查找單調序列中，在指定區域內[1,n]是否存在目標值x。存在返回true，不存在返回false
例：int k=binary_search(a+1,a+7,3)；//k=1

2. lower_bound(a+1,a+n+1,x)
查找不降序列中，在指定區域內[1,n]大于等于目標值x的第一個元素所在地址。(靠左查找)
例：int pos=lower_bound(a+1,a+7,3)-a;//元素位置在a+2，因此pos=2。

3. upper_bound(a+1,a+n+1,x)
查找不降序列中，在指定區域內[1,n]大于目標值x的第一個元素所在地址。(靠右查找)
例：int pos=lower_bound(a+1,a+7,3)-a;//元素位置在a+5，因此pos=5。

倍增

主要運用于：

LCA

void dfs(int x,int fa){
	f[x][0]=fa;
	dep[x]=dep[fa]+1;
	for(int i=1;i<=20;i++)
		f[x][i]=f[f[x][i-1]][i-1];
	for(int i=head[x];i;i=nxt[i]){
		int y=ver[i];
		if(y==fa) continue;
		dfs(y,x);
	}
}
int lca(int a,int b){
	if(dep[a]<dep[b]) swap(a,b);
	for(int i=20;i>=0;i--){
		if(dep[f[a][i]]>=dep[b])
			a=f[a][i];
	}
	if(a==b) return a;
	for(int i=20;i>=0;i--){
		if(f[a][i]!=f[b][i])
			a=f[a][i],b=f[b][i];
	}
	return f[a][0];
}

DP優化

請轉到 DP動態規劃。

排序

最實用的排序做法

sort: 升序排序

各大排序算法比較