有些简单的就不记了。

Day 1

Part 1.上午

手写堆

一种建立二叉树的方法：
设当前节点的编号为 \(i\) ，则其父节点的编号为 \(\frac{i}{2}\) ，其左儿子的编号为 \(2\times i\) ，其右儿子的编号为 \(2 \times i+1\) 。

怎样用二叉树实现堆？
需要保证每个节点储存的值，都不小于它儿子节点储存的值。

//手写大根堆
struct heap{
	int a[N],n;// n 表示当前队列里一共有 n 个数 
	inline int top(){//询问最大值 
		return a[1];
	}
	inline int size(){//询问有多少个数 
		return n;
	}
	void push(int x){//加入一个数 
		n++;
		a[n]=x;
		int p=n;
		while(p!=1){
			int x=p/2;
			if(a[x]<a[p]){
				swap(a[x],a[p]);
				p=x;
			}
			else break;
		}
	}
	void pop(){//删除最大值 
		swap(a[1],a[n]);
		n--;
		int p=1;
		while(p*2<=n){
			int x=p*2;//左儿子 
			if(a[x+1]>a[x]&&x+1<=n) x=x+1;// x 指向当前节点的左右儿子当中的较大值的编号 
			if(a[p]<a[x]){
				swap(a[x],a[p]);
				p=x;
			}
			else break;
		}
	}
};

Part 2.下午

堆 应用

例题 \(1\)

给定 \(n\) 个数 \(a_1 ,a_2,\dots,a_n\)，枚举所有区间，对于每一个区间，求它的中位数。

\(n \le 2000\)

中位数：如果当前区间内的元素个数为奇数个时，中位数就是将该区间内元素排序后的中间数，即 \(a[\left \lfloor n\ {\div}\ 2 \right \rfloor +1]\) ；如果当前区间内的元素个数为偶数个时，中位数就是将该区间内元素排序后的中间两个数的平均值，即 \((a[n\ {\div}\ 2 ]+a[n\ {\div}\ 2+1])\ {\div} 2\)。

考虑用堆来实现。首先，将 \(a_l \dots a_{r\ \div\ 2}\) 放入一个大根堆，将 \(a_{r\ \div\ 2 + 1} \dots a_r\) 的值放入一个小根堆。

考虑插入元素，先将插入的元素放入小根堆，并取出小根堆中的最小值（也就是小根堆的堆顶）放到大根堆里。

如果大根堆内的元素个数与小根堆内的元素个数相同，那么该区间的中位数就是 \((\)大根堆的堆顶元素\(+\)小根堆的堆顶元素\() \ \div 2\)；否则，该区间的中位数就是小根堆的堆顶元素。

时间复杂度 \(O(n^2 \log n)\)

int n,a[2005];
int main(){
    scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int l=1;l<=n;l++){
		priority_queue<int> heap_max;
		priority_queue<int,vector<int>,greater<int> > heap_min;
		heap_max.push(a[l]);// a[l] 为 l~l 区间的中位数
		int mid=a[l];//当前中位数 
		for(int r=l+1;r<=n;r++){// l ~ r 这一段的中位数 
			if(a[r]>mid) heap_min.push(a[r]);
			else heap_max.push(a[r]);
			while(heap_max.size()>heap_min.size()+1){
				int v=heap_max.top();
				heap_max.pop();
				heap_min.push(v);
			}
			while(heap_min.size()>heap_max.size()+1){
				int v=heap_min.top();
				heap_min.pop();
				heap_max.push(v);
			}
			if(heap_max.size()>heap_min.size()) mid=heap_max.top();
			else if(heap_min.size()>heap_max.size()) mid=heap_min.top();
			else mid=(heap_max.top()+heap_min.top())/2; 
		}
		printf("%d\n",mid);
	}
	return 0;
}
//该代码里没有考虑平均数为小数的情况

map

map<下标的类型,元素的类型> mp;

可以把 map 当作数组来使用，但是访问的时间复杂度为 \(\log\) 级别，主要是在数组下标过大、过小或下标类型不是整型的情况下来使用。

STL 函数

sort(a+1,a+1+n); 时间复杂度 \(O(n \log n)\)

reverse(a+1,a+1+n); 时间复杂度 \(O(n)\)

unique(a+1,a+1+n); 去重，必须先把当前数组排序后再去重。时间复杂度 \(O(n)\)，加上排序为 \(O(n \log n)\)。

int x=unique(a+1,a+1+n)-a-1; 表示当前数组去重后剩余元素个数。

random_shuffle(a+1,a+1+n); 将当前数组内的元素随机打乱，时间复杂度 \(O(n)\)。

归并排序

时间复杂度 \(O(n \log n)\)

void merge_sort(int l,int r){
    if(l==r) return;
    int mid=(l+r)/2;
    merge_sort(l,mid);
    merge_sort(mid+1,r);
    int p=l,q=mid+1;// p 左边第一个数的下标 , q 右边第一个数的下标
    for(int i=l;i<=r;i++){
    	if(p>mid){//左边的数取完了 
        	t[i]=a[q];
        	q++;
		}
		else if(q>r){//右边的数取完了 
        	t[i]=a[p];
        	p++;
		}
        else if(a[p]<a[q]){//左边较小 
        	t[i]=a[p];
        	p++;
		}
        else{//右边较小 
        	t[i]=a[q];
        	q++;
		}
    }
    for(int i=l;i<=r;i++) a[i]=t[i];
}

例题 \(1\) P1908 逆序对

利用归并排序。可以发现，当右边的 \(a_x\) 小于左边的 \(a_y\) ，那么 \(a_x\) 与 \(a_{mid-y+1},\dots,a_{mid}\) 都分别为逆序对。

const int N=5e5+5;
int n,a[N],t[N];
int merge_sort(int l,int r){
    if(l==r) return 0;
    int mid=(l+r)/2,res=0;
    res=res+merge_sort(l,mid);
    res=res+merge_sort(mid+1,r);
    int p=l,q=mid+1;
    for(int i=l;i<=r;i++){
    	if(p>mid){
        	t[i]=a[q];
        	q++;
		}
		else if(q>r){
        	t[i]=a[p];
        	p++;
		}
        else if(a[p]<=a[q]){
        	t[i]=a[p];
        	p++;
		}
        else{ 
        	t[i]=a[q];
        	q++;
        	res=res+(mid-p+1);
		}
    }
    for(int i=l;i<=r;i++) a[i]=t[i];
    return res;
}
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    printf("%lld",merge_sort(1,n));
    return 0;
}

前缀和

例题 \(1\)

给定 \(n\) 个数 \(a_1 ,a_2,\dots,a_n\)，有 \(m\) 次操作，每次操作给定 \(l,r\) 和 \(v\)，将 \(a_l,a_{l+1},\dots,a_r\) 都加上 \(v\)。最后输出 \(a_1 ,a_2,\dots,a_n\) 的值。

const int N=1e5+5;
int n,m,a[N],sum[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&m);
	while(m--){
		int l,r,v;
        scanf("%d%d%d",&l,&r,&v);
		sum[l]=sum[l]+v;
		sum[r]=sum[r]-v;
	}
	for(int i=1;i<=n;i++) sum[i]=sum[i]-sum[i-1];
	for(int i=1;i<=n;i++) printf("%d ",a[i]+sum[i]);
	return 0;
}

Day 2

Part 1.上午

倍增

用来预处理数组，对于 \(f_{i,j}\)，表示从 \(a_i\) 开始的 \(2^j\) 个数的最大值，也就是 \(\max(a_i,a_{i+1},\dots,a_{i+2^j-1})\)。

\(f_{i,0}=a_i\)，\(f_{i,j}=\max(f_{i,j-1},f_{i+2^j,j-1})\)

const int N=1e5+5;
int n,a[N],f[N][20];//f 数组的第二维 2^20 肯定是大于 10^5 的
int main(){
    scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		f[i][0]=a[i];
	}
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
	return 0;
}

例题 \(1\) P3865 【模板】ST 表

const int N=1e5+5;
int n,m,a[N],f[N][20],x[N];//x 数组代表长度为 i 的区间用两个长度为2^x[i]的区间能够覆盖
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		f[i][0]=a[i];
	}
	x[1]=0;
	for(int i=2;i<=n;i++) x[i]=x[i>>1]+1;// +1 将其长度翻倍 
	for(int j=1;(1<<j)<=n;j++){
		for(int i=1;i+(1<<j)-1<=n;i++) f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1]);
	}
    scanf("%d",&m);
	while(m--){
		int l,r;
        scanf("%d%d",&l,&r);
        int sz=r-l+1,j=x[sz];
		printf("%d\n",max(f[l][j],f[r-(1<<j)+1][j]));
	}
	return 0;
}

二分

例题 \(1\)

给定 \(n\) 个数 \(a_1 ,a_2,\dots,a_n\)，保证 \(a_1 \le a_2 \le \dots \le a_n\)，有 \(m\) 次操作，每次操作给定一个数 \(x\)，询问 \(x\) 是否出现过。

int n,m,a[100005];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	while(m--){
		int x,l=0,r=n;
        scanf("%d",&x);
		while(l+1!=r){
			int mid=(l+r)>>1;
			if(x<=a[mid]) r=mid;
			else l=mid;
		}
		if(a[r]==x) puts("Yes");
		else puts("No");
	} 
	return 0;
}

例题 \(2\) P2969 [USACO09DEC] Music Notes S

使用前缀和来维护每段音阶敲击的次数，也就是 \(sum_i=\sum_{j=1}^i b_j\)，对于每次询问，需要二分来找到在满足 \(sum_i \ge T+1\) 的情况下，\(sum_i\) 的最小值。

const int N=5e4+5;
int n,q,b[N],sum[N];
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++){
        scanf("%d",&b[i]);
        sum[i]=sum[i-1]+b[i];
    }
    while(q--){
        int t,l=0,r=n;
        scanf("%d",&t);
		while(l+1!=r){
			int mid=(l+r)>>1;
			if(sum[mid]>=t+1) r=mid;
			else l=mid;
		}
        printf("%d\n",r);
    }
    return 0;
}

例题 \(3\) Drying

有 \(n\) 件衣服，每件衣服都有一定的含水量，每分钟每件衣服的含水量会减少 \(1\)。有一个吹风机，每分钟只能对一个衣服使用吹风机，且这分钟过完了，衣服的含水量会减少 \(k\)，求最少要多少分钟能让所有衣服的含水量都为非正数。

int n,k,a[100005]; 
inline bool check(int x){//能否在 x 分钟把所有衣服弄干 
	int sum=0;
	for(int i=1;i<=n;i++){
		if(a[i]>x) sum=sum+(a[i]-x-1)/x+1;
	}
	return sum<=x;
}
int main(){
    scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	scanf("%d",&k);
	sort(a+1,a+1+n);
	int l=0,r=a[n];
	while(l+1!=r){
		int mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid;
	}
	printf("%d",r);
	return 0;
}

例题 \(4\) P1873 [COCI 2011/2012 #5] EKO / 砍树

int n,m,a[10000005]; 
inline bool check(int x){
	int sum=0;
	for(int i=1;i<=n;i++){
		if(a[i]>x) sum=sum+(a[i]-x);
	} 
	return sum>=m;
}
signed main(){
    scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	sort(a+1,a+1+n);
	int l=0,r=INT_MAX;
	while(l+1!=r){
		int mid=(l+r)>>1;
		if(check(mid)) l=mid;
		else r=mid;
	}
	printf("%lld",l);
	return 0;
}

例题 \(5\)​​ P2985 [USACO10FEB] Chocolate Eating S

例题 \(6\)​ P1824 进击的奶牛

矩阵乘法

在第一个矩阵的列数等于第二个矩阵的行数的情况下，矩阵乘法成立。

结果矩阵的行数等于第一个矩阵的行数，列数等于第二个矩阵的列数。结果矩阵中的 \((i,j)\) 等于第一个矩阵的第 \(i\) 行和第二个矩阵的第 \(j\) 列对应位置相乘。

时间复杂度 \(O(n^3)\)

struct martix{
	int n,m;//行数 列数 
	int a[5][5];
	martix(){
		n=m=0;
		memset(a,0,sizeof(a));
	}
};
martix operator*(const martix &m1,const martix &m2){
	martix m3;
	m3.n=m1.n;
	m3.m=m2.m;
	for(int i=1;i<=m3.n;i++){
		for(int j=1;j<=m3.m;j++){
			for(int k=1;k<=m1.m;k++) m3.a[i][j]=m3.a[i][j]+m1.a[i][k]*m2.a[k][j];
		}
	}
	return m3;
}

矩阵快速幂

struct martix{
	int n,m,a[5][5];
	martix(){
		n=m=2;
		memset(a,0,sizeof(a));
	}
}mx;
martix operator*(const martix &m1,const martix &m2){
	martix m3;
	m3.n=m1.n;
	m3.m=m2.m;
	for(int i=1;i<=m3.n;i++){
		for(int j=1;j<=m3.m;j++){
			for(int k=1;k<=m1.m;k++) m3.a[i][j]=(m3.a[i][j]+m1.a[i][k]*m2.a[k][j])%mod;
		}
	}
	return m3;
}
martix ksm(martix a,int b){
	martix res;
	res.a[1][1]=res.a[1][2]=1;
	while(b){
		if(b&1) res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}

例题 \(1\) P3390 【模板】矩阵快速幂

const int mod=1e9+7;
int n,k;
struct martix{
	int a[105][105];
	martix(){
		memset(a,0,sizeof(a));
	}
}mx,res;
martix operator*(const martix &m1,const martix &m2){
	martix m3;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
			for(int k=1;k<=n;k++) m3.a[i][j]=(m3.a[i][j]+m1.a[i][k]*m2.a[k][j])%mod;
		}
	}
	return m3;
}
signed main(){
    scanf("%lld%lld",&n,&k);
	for(int i=1;i<=n;i++){
        res.a[i][i]=1;
        for(int j=1;j<=n;j++) scanf("%lld",&mx.a[i][j]);
    }
    while(k){
		if(k&1) res=res*mx;
		mx=mx*mx;
		k>>=1;
	}
	for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) printf("%lld ",res.a[i][j]);
        printf("\n");
    }
	return 0;
}

例题 \(2\) P1962 斐波那契数列

可以发现 \(n\)​ 的数据范围很大，所以用矩阵快速幂优化。

注意要特判 \(k=1\) 的情况

const int mod=1e9+7;
struct martix{
	int n,m,a[5][5];
	martix(){
		n=m=2;
		memset(a,0,sizeof(a));
	}
}mx;
martix operator*(const martix &m1,const martix &m2){
	martix m3;
	m3.n=m1.n;
	m3.m=m2.m;
	for(int i=1;i<=m3.n;i++){
		for(int j=1;j<=m3.m;j++){
			for(int k=1;k<=m1.m;k++) m3.a[i][j]=(m3.a[i][j]+m1.a[i][k]*m2.a[k][j])%mod;
		}
	}
	return m3;
}
martix ksm(martix a,int b){
	martix res;
	res.a[1][1]=res.a[1][2]=1;
	while(b){
		if(b&1) res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
int k;
signed main(){
	scanf("%d",&k);
	if(k==1){
	    puts("1");
	    return 0;
	}
	mx.a[1][1]=mx.a[1][2]=mx.a[2][1]=1;
	printf("%lld",ksm(mx,k-2).a[1][1]);
	return 0;
}

例题 \(3\) P4159 [SCOI2009] 迷路

先从边权只有 \(0\) 和 \(1\) 的情况考虑，设 \(f_t[i,j]\) 为从 \(i\) 点到 \(j\) 点花费时间为 \(t\) 的方案数，那么可得 \(f_t[i,j]=\sum_{k=1}^n f_{t-1}[i,k] \cdot f_1[k,j]\)，也就是 \(f_t=f_{t-1} \cdot f_1\) ，依据矩阵乘法的结合律，所以 \(f_t=f_1^t\)。

所以，答案为 \(f_T[1,n]\)。

const int mod=2009;
int n,T;
struct martix{
	int a[105][105];
	martix(){
		memset(a,0,sizeof(a));
	}
}f;
martix operator*(const martix &m1,const martix &m2){
	martix m3;
	for(int i=1;i<=n*9;i++){
		for(int j=1;j<=n*9;j++){
			for(int k=1;k<=n*9;k++) m3.a[i][j]=(m3.a[i][j]+m1.a[i][k]*m2.a[k][j])%mod;
		}
	}
	return m3;
}
martix ksm(martix a,int b){
	martix res=f;
	while(b){
		if(b&1) res=res*a;
		a=a*a;
		b>>=1;
	}
	return res;
}
int main(){
    scanf("%d%d",&n,&T);
    for(int i=1;i<=n;i++){
        for(int j=1;j<=8;j++) f.a[i+j*n][i+(j-1)*n]=1;
        for(int j=1;j<=n;j++){
            char ch=getchar();
            if(!isdigit(ch)) ch=getchar();
            int nw=ch-'0';
            f.a[i][j+n*(nw-1)]=1;
        }
    }
    printf("%d",ksm(f,T-1).a[1][n]);
    return 0;
}

Part 2.下午

贪心

贪心的核心是排序。做法通常是以小见大，从 \(n=2\) 时的情况下做。

例题 \(1\) P1080 [NOIP2012 提高组] 国王游戏

只考虑如何排序

首先考虑 \(n=2\) ，假设国王为 \(p_0\) ，第一个大臣为 \(p_1\) ，第二个大臣为 \(p_2\) ，那么只需要考虑 \(2\) 种情况：第一种情况是 \(p_1\) 站在 \(p_2\) 前面，第二种情况是 \(p_2\) 站在 \(p_1\) 前面。

在第一种情况下，\(p_1\) 获得的金币为 \(\frac{p_0l}{p_1r}\) ，\(p_2\) 获得的金币为 \(\frac{p_0l \cdot p_1l}{p_2r}\)，答案对 \(\frac{p_0l}{p_1r}\) 和 \(\frac{p_0l \cdot p_1l}{p_2r}\) 取 \(\max\) 。

在第二种情况下，\(p_2\) 获得的金币为 \(\frac{p_0l}{p_2r}\) ，\(p_1\) 获得的金币为 \(\frac{p_0l \cdot p_2l}{p_1r}\)，答案对 \(\frac{p_0l}{p_2r}\) 和 \(\frac{p_0l \cdot p_2l}{p_1r}\) 取 \(\max\) 。

对 \(\max(\frac{p_0l}{p_2r},\frac{p_0l \cdot p_2l}{p_1r})\) 和 \(\max(\frac{p_0l}{p_1r},\frac{p_0l \cdot p_1l}{p_2r})\) 取 \(\min\) ，谁小谁在前面。

struct person{
    int l,r;
}a[N];
inline bool cmp(person x,person y){
    int v1=max(a[0].l/x.r,a[0].l*x.l/x.r);
    int v2=max(a[0].l/y.r,a[0].l*y.l/y.r);
    if(v1<v2) return true;
    return false;
}

考虑对 cmp 函数进行化简。显然，较大值不可能是 \(\frac{p_0l}{p_1r}\) 和 \(\frac{p_0l}{p_2r}\)，那么就可以化简为 \(\min(\frac{p_0l \cdot p_1l}{p_2r},\frac{p_0l \cdot p_2l}{p_1r})\) 。约去 \(p_0l\) ，接着交叉相乘，可化简为 \(\min(p_1l \cdot p_1r,p_2l \cdot p_2r)\)。

struct person{
    int l,r;
}a[N];
inline bool cmp(person x,person y){
    if(x.l*x.r<y.l*y.r) return true;
    return false;
}

例题 \(2\)

山洞的体积为 \(v\) ，第 \(i\) 个物品放在山洞里会占据 \(a_i\) 的空间，在搬运过程中至少需要 \(b_i\) 的空间，问能不能把所有物品都放下？

同样从 \(n=2\) 开始考虑，有 \(2\) 种情况，第一种情况是先搬 \(a\) 再搬 \(b\) ，第二种情况是先搬 \(b\) 再搬 \(a\) 。

在第一种情况下，所需要的最大体积为 \(\max(b_1,a_1,a_1+b_2,a_1+a_2)\)

在第二种情况下，所需要的最大体积为 \(\max(b_2,a_2,a_2+b_1,a_1+a_2)\)

最后对 \(\max(b_1,a_1,a_1+b_2,a_1+a_2)\) 和 \(\max(b_2,a_2,a_2+b_1,a_1+a_2)\) 取 \(\min\) 。

struct node{
    int a,b;
}a[N];
inline bool cmp(node x,node y){
    int v1=max(x.b,max(x.a,max(y.b+x.a,x.a+y.a)));//x y
    int v2=max(y.b,max(y.a,max(x.b+y.a,x.a+y.a)));//y x
    if(v1<v2) return true;
    return false;
}

考虑对 cmp 函数进行化简。显然，最大值肯定不会是 \(a_1,b_1,a_2,b_2\)。两边同时都有 \(a_1+a_2\) ，消掉。然后把 \(a_1+b_2\) 和 \(a_2+b_1\) 转化为 \(a_1-b_1\) 和 \(a_2-b_2\) 。

struct node{
    int a,b;
}a[N];
inline bool cmp(node x,node y){
    if(x.a-x.b<y.a-y.b) return true;
    return false;
}

例题 \(3\)​ P1315 [NOIP2011 提高组] 观光公交

搜索

\(\mathrm{BFS:}\) 求最优解问题，且是求最小步数，每走一步代价为 1。

\(\mathrm{DFS:}\) 除上外，其它都使用 \(\mathrm{DFS}\)

BFS

例题 \(1\)

在一个 \(n\) 行 \(m\) 列的网格图中，给定一个起点和一个终点，求沿网格线走且不经过障碍物的情况下，从起点到终点的最小值。

const int N=5005;
int n,m,a[N][N],sx,sy,tx,ty;// n 行数；m 列数
int step[N][N];//step[i,j] 表示从起点到 (i,j) 需要多少步 
int dx[4]={-1,1,0,0},dy[4]={0,0,-1,1};
int main(){
    scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);//a[i,j] 为 1 时表示障碍物 
	}
    scanf("%d%d",&sx,&sy);//起点坐标 
	scanf("%d%d",&tx,&ty);//终点坐标
	memset(step,-1,sizeof(step));
	step[sx][sy]=0;
	queue<pair<int,int> > q;//存能够向外进行拓展 step 的点
	q.push(make_pair(sx,sy));
	while(!q.empty()){
		int x=q.front().first,y=q.front().second;//当前点为 (x,y) 
		q.pop();
		for(int i=0;i<4;i++){
			int nx=dx[i]+x,ny=dy[i]+y;//从 (x,y) 走到了 (nx,ny) 
			if(nx>=1&&nx<=n&&ny>=1&&ny<=m&&a[nx][ny]!=1&&step[nx][ny]==-1){
				q.push(make_pair(nx,ny));
				step[nx][ny]=step[x][y]+1;
			}
		} 
	}
	printf("%d",step[tx][ty]);
	return 0;
}

DFS

例题 \(2\)

给定 \(n\) 个数 \(a_1 ,a_2,\dots,a_n\)，选 \(m\) 个数，求选中的 \(m\) 个数的最大值。

const int N=1e5+5;
int n,m,a[N],res=INT_MIN;
void dfs(int nw,int num,int sum){
	//当前要看第 nw 个数选不选
	//当前已经选了 num 个数
	//已经选了的数的和是 sum
	if(nw>n){//选完
		if(num==m) res=max(res,sum); 
		return;
	}
	dfs(nw+1,num,sum);//不选 
	dfs(nw+1,num+1,sum+a[nw]);//选 
} 
int main(){
    scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	dfs(1,0,0);
	printf("%d",res);
	return 0;
}

时间复杂度 \(O(2^n)\)

考虑优化上面的代码。

剪枝优化

可行性剪枝：有一些不合法的答案，舍弃。

最优性剪枝：继续搜索答案不会更优，舍弃。

下面是例题 \(2\) 的可行性剪枝 & 最优性剪枝优化

void dfs(int nw,int num,int sum){
	//当前要看第 nw 个数选不选
	//当前已经选了 num 个数
	//已经选了的数的和是 sum
	if(num>m) return;//可行性剪枝 1：已经选了超过 m 个数 
	if(num+n-nw+1<m) return;//可行性剪枝 2：把剩下所有的东西都选上，加上当前的，仍然到不了 m
	if(sum+s[n]-s[nw-1]<=res) return;//最优性剪枝
	if(nw>n){//选完
		if(num==m) res=max(res,sum); 
		return;
	}
	dfs(nw+1,num,sum);//不选 
	dfs(nw+1,num+1,sum+a[nw]);//选 
} 

卡时优化

用一个计时器，当快要 \(\mathrm{TLE}\) 时，将当前搜索到的最优解输出。

头文件：#include<ctime>

//clock()程序运行了多少时间 
if(1000*clock()>(时限*1000)*CLOCKS_PER_SEC){
	printf("%d",result);
	exit(0);
} 

注：卡时的时候，要注意留足够的时间来输出。

改变搜索顺序优化

出题人有可能会构造某些数据，使得最优性剪枝无效。

使用 random_shuffle 来打乱搜索顺序

下面是例题 \(2\) 的改变搜索顺序优化

const int N=1e5+5;
int n,m,a[N],res=INT_MIN;
void dfs(int nw,int num,int sum){
	//当前要看第 nw 个数选不选
	//当前已经选了 num 个数
	//已经选了的数的和是 sum
	if(nw>n){//选完
		if(num==m) res=max(res,sum); 
		return;
	}
	dfs(nw+1,num,sum);//不选 
	dfs(nw+1,num+1,sum+a[nw]);//选 
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	random_shuffle(a+1,a+1+n);
	dfs(1,0,0);
	printf("%d",res);
	return 0;
}

Day 3

Part 1.上午

搜索 应用

例题 \(1\)

给定一个大小为 \(n \times n\) 的棋盘，求放置 \(n\) 个皇后，使任意两个皇后之间互相不能攻击到，求有多少种满足条件的方案

int n,cnt,pos[15];//pos[i] 代表第 i 行的皇后放在了第 pos[i] 列 
void dfs(int nw){//现在放第 nw 行的皇后 
	if(nw>n){
		cnt++;
		return;
	}
	for(int j=1;j<=n;j++){
		bool flag=true;
		for(int i=1;i<nw;i++){//枚举第 i 行的皇后 
			if(pos[i]==j||abs(nw-i)==abs(j-pos[i])) flag=false;
		} 
		if(flag){
			pos[nw]=j;
			dfs(nw+1);
		}
	}
}
int main(){
	scanf("%d",&n);
	dfs(1);
	printf("%d",cnt);
	return 0;
} 

考虑优化。

用 \(col_i\) 表示第 \(i\) 列上有没有皇后。对每条斜线进行编号，显然每条斜线上也只能有一个皇后，那么就和处理列的方法相同，但是需要判两次。

右上到左下斜线编号规律：\(行+列-1=该斜线编号\)

左上到右下斜线编号规律：\(列-行+n=该斜线编号\)

int n,cnt;
bool col[15];//col[i] 第 i 列上是否有皇后 
bool xie1[50];//从左上到右下斜线上是否有皇后 
bool xie2[50];//从右上到左下斜线上是否有皇后 
void dfs(int nw){//现在放第 nw 行的皇后 
	if(nw>n){
		cnt++;
		return;
	}
	for(int j=1;j<=n;j++){//第 nw 行皇后放在第 j 列上 
		int idx1=j-nw+n;//左上到右下斜线编号 
		int idx2=nw+j-1;//右上到左下斜线编号
		if(!col[j]&&!xie1[idx1]&&!xie2[idx2]){
			col[j]=xie1[idx1]=xie2[idx2]=true;
			dfs(nw+1);
			col[j]=xie1[idx1]=xie2[idx2]=false;
		}
	}
}

对称优化

假设给定的 \(n\) 都是偶数，怎样优化？

显然，这个问题可以左右翻转，那么就可以只搜一半，搜完答案乘 \(2\) 即可。

int n,cnt;
bool col[15];//col[i] 第 i 列上是否有皇后 
bool xie1[50];//从左上到右下斜线上是否有皇后 
bool xie2[50];//从右上到左下斜线上是否有皇后 
void dfs(int nw){//现在放第 nw 行的皇后 
	if(nw>n){
		cnt++;
		return;
	}
	int up=n;
	if(nw==1) up>>=1; 
	for(int j=1;j<=up;j++){//第 nw 行皇后放在第 j 列上 
		int idx1=j-nw+n;//左上到右下斜线编号 
		int idx2=nw+j-1;//右上到左下斜线编号
		if(!col[j]&&!xie1[idx1]&&!xie2[idx2]){
			col[j]=xie1[idx1]=xie2[idx2]=true;
			dfs(nw+1);
			col[j]=xie1[idx1]=xie2[idx2]=false;
		}
	}
}
int main(){
	scanf("%d",&n);
	dfs(1);
	printf("%d",cnt*2);
	return 0;
} 

假设给定的 \(n\) 都是奇数，怎样优化？

\(1 \dots (n-1)/2\) 列和 \((n-1)/2+2 \dots n\) 列相互对称，那么分别用 \(res1\) 和 \(res2\) 来统计 \(1 \dots (n-1)/2\) 列和第 \((n-1)/2+1\) 列的答案，最终答案为 \(res1 \times 2 +res2\)​ 。

状态压缩优化

用二进制数来表示第 \(i\) 列有没有皇后，\(1\) 表示有，\(0\) 表示没有，也就是和 \(true\) 和 \(false\)​ 等价。

int n,cnt;
void dfs(int nw,int s1,int s2,int s3){
//现在放第 nw 行的皇后 
// s1 代表每列上有没有皇后
// s2 代表每条从左上到右下的斜线上有没有皇后
// s3 代表每条从右上到左下的斜线上有没有皇后 
	if(nw>=n){
		cnt++;
		return;
	}
	int s=s1|s2|s3;
	for(int j=0;j<n;j++){//第 nw 行皇后放在第 j 列上 
//		if(((s1>>j)&1)==0&&((s2>>j)&1)==0&&((s3>>j)&1)==0)
		if(((s>>j)&1)==0){//在 s 第 j 个位置上没有皇后 
			dfs(nw+1,s1|(1<<j),(s2|(1<<j))<<1,(s3|(1<<j))>>1);
			//将 s1,s2,s3 的第 j 位染色成 1 
		}
	}
}
int main(){
	scanf("%d",&n);
	dfs(0,0,0,0);
	printf("%d",cnt);
	return 0;
} 

双向\(\mathrm{BFS}\)

分别从起点和终点 \(\mathrm{BFS}\)，需要维护两个队列，用数组记录当前的搜索情况，从两个方向拓展的节点打不同的标记。当某点被两种标记同时标记时，也就代表着该点被两个 \(\mathrm{BFS}\) 搜索到，结束。

例题 \(2\)​​ P1379 八数码难题

双向 \(\mathrm{BFS}\)

例题 \(3\)​ P1074 [NOIP2009 提高组] 靶形数独

例题 \(4\)​ P1312 [NOIP2011 提高组] Mayan 游戏

Part 2.下午

图论概念

度

一个顶点的度是指与该顶点相关联的边的条数，顶点 \(v\) 的度
记作 \(d(v)\) 。

在有向图中，度分为入度和出度

入度指的是从该图中除当前点外的点向当前点连的边的条数。

出度指的是从当前点向除当前点外的其它点连的边的条数。

环

如果一条路径的起点和终点都是同一个点，那么称之为环。

如果一条边的起点和终点都是同一个点，那么称之为自环。

除起点以外，不经过重复的点和边的环，称之为简单环。

简单路径

不走重复的点的路径，称之为简单路径。

树

无向、无环并且连通的图。

如果一棵树有 \(n\) 个点，那么这棵树有 \(n-1\)​​ 条边。

有向树分为外向树和内向树

如果一棵树由源点向外连边，那么称这棵树为外向树。反之，则称这棵树为内向树。

森林

无向、无环且不连通的图，称之为森林（每个连通块都是一棵树，多棵树组成了森林）

章鱼图（基环树）

有且只有一个环，从章鱼图环上的点向外延申，那一定是一棵树。如果用一个环把几棵树的顶点连接起来，那么称之为章鱼图，也称基环树。

如果一棵基环树有 \(n\) 个点，那么这棵基环树有 \(m\) 条边，删一条边就变成了一棵树。

在一棵树中，随意加一条边，那么就形成了环，也就是变成了基环树。

\(\mathrm{DAG}\) （有向无环图）

有向且无环，有向树和无向树在本质上也是一个有向无环图。

二分图

能够把所有点分为两个部分，使得这张图中的所有边都是从第一部分连向第二部分，在每一部分内部无边。

有奇环的图一定不是二分图。（奇环是指在一个环上有奇数个点的环）

图论实现

\(\mathrm{vector}\) 存图

//优点：省内存
//缺点：慢
vector<pair<int,int> >g[N];
// g[i] 所有以 i 作为起点的边 
// g[i][j] 以 i 为起点的第 j 条边 
// g[i][j].first 以 i 为起点的第 j 条边的终点 
// g[i][j].second 以 i 为起点的第 j 条边的长度 
void add_edge(int u,int v,int w){
	g[u].push_back(make_pair(v,w));
}

for(int i=1;i<=n;i++){//枚举从 i 号点出发的所有边 
	for(int j=0;j<g[i].size();j++){// g[i].size() 代表从 i 出发有几条边 
		int e=g[i][j].first,d=g[i][j].second;
		//代表当前的边，是从 i 开始的第 j 条边，终点为 e，长度为 d 
	}
}

二分图判定（染色法）

const int N=1e5+5;
int n,m,col[N];//col[i]==0 代表没有染色，否则代表第 i 个点染的颜色 
vector<int>g[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
        scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	for(int i=1;i<=n;i++){
		if(col[i]!=0) continue;
		col[i]=1;
		queue<int> q;//可以改变周围颜色的点
		q.push(i);
		while(!q.empty()){
			int u=q.front();
			q.pop();
			for(int j=0;j<(int)g[u].size();j++){
				int k=g[u][j];//当前边是从 i->j 的一条边
				if(col[k]==0){
					col[k]=3-col[u];
					q.push(k);
				}
				else{
					if(col[k]==col[u]){
						puts("No");
						exit(0);
					}
				}
			}
		}
	} 
	puts("Yes");
	return 0;
}

拓扑排序

将一张有向无环图中的所有点排序，保证排完序后，有向无环图中的所有边都是从左向右连，答案不唯一。

const int N=1e5+5;
int n,m;// n 个点 m 条边
int in[N];// in[i] 代表第 i 个点的入度
int res[N];//所有入度为 0 的点 
vector<int>g[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int u,v;
        scanf("%d%d",&u,&v);
		g[u].push_back(v);
		in[v]++; 
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(in[i]==0) res[++cnt]=i;
	}
	for(int i=1;i<=n;i++){//当前要去除拓扑排序的结果中的第 i 个点 
		int p=res[i];
		for(int j=0;j<(int)g[p].size();j++){
			int q=g[p][j];
			in[q]--;
			if(in[q]==0) res[++cnt]=q;
		}
	}
	for(int i=1;i<=n;i++) printf("%d ",res[i]);
	return 0;
}

例题 \(1\) B3644 【模板】拓扑排序 / 家谱树

const int N=1e5+5;
int n,m,in[N];// in[i] 代表第 i 个点的入度
int res[N];//所有入度为 0 的点 
vector<int>g[N];
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		while(1){
			int v;
            scanf("%d",&v);
			if(v==0) break;
			g[i].push_back(v);
			in[v]++;
		} 
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(in[i]==0) res[++cnt]=i;
	}
	for(int i=1;i<=n;i++){
		int p=res[i];
		for(int j=0;j<(int)g[p].size();j++){
			int q=g[p][j];
			in[q]--;
			if(in[q]==0) res[++cnt]=q;
		}
	} 
	for(int i=1;i<=n;i++) printf("%d ",res[i]);
	return 0;
}

最近公共祖先（\(\mathrm{LCA}\)）

祖先：从点 \(i\) 到根节点的路径上的所有点都是点 \(i\) 的祖先（也包含 \(i\) 本身），它的祖先个数就是它的深度。

倍增求 \(\mathrm{LCA}\)

用 \(f[i,j]\) 表示从 \(i\) 点向根节点方向走 \(2^j\) 步会走到哪里。\(2^j\) 步可以分割成先走 \(2^{j-1}\) 步，再走 \(2^{j-1}\) 步，第一次走显然是 \(f[i,j-1]\)，第二次走是在第一次的基础上走，那么就是 \(f[f[i,j-1],j-1]\)。

\(f[i,0]\) 会走到 \(i\)​​ 的父亲。

时间复杂度 \(O(\log n)\)

例题 \(1\) P3379 【模板】最近公共祖先（LCA）

const int N=5e5+5;
int n,m,s,depth[N];// depth 数组代表每个节点的深度
int f[N][20];// f[i][j] 代表从 i 向上走 2^j 步会走到哪里 
vector<int>g[N];
void dfs(int i,int j){//当前要搜索的是第 i 个点，是从 i 的父亲 j 走到 i  
	f[i][0]=j;
	for(int k=1;k<20;k++) f[i][k]=f[f[i][k-1]][k-1];
	depth[i]=depth[j]+1;
	for(int k=0;k<(int)g[i].size();k++){
		int l=g[i][k];//i->l
		if(l!=j) dfs(l,i);
	}
}
int lca(int p1,int p2){//求 p1 和 p2 的 lca 
	// 1. 把 p1 和 p2 两个点的深度调整成一样的
	if(depth[p1]<depth[p2]) swap(p1,p2);
	for(int i=19;i>=0;i--){
		if(depth[f[p1][i]]>=depth[p2]) p1=f[p1][i];
	}
	if(p1==p2) return p1;
	// 2. 跳到 LCA
	for(int i=19;i>=0;i--){
		if(f[p1][i]!=f[p2][i]){
			p1=f[p1][i];
			p2=f[p2][i];
		}
	}
	return f[p1][0];
}
int main(){
    scanf("%d%d%d",&n,&m,&s);
	for(int i=1;i<n;i++){
		int u,v;
        scanf("%d%d",&u,&v);
		g[u].push_back(v);
		g[v].push_back(u);
	}
	dfs(s,0);//节点 s 为根 
	while(m--){
		int u,v;
        scanf("%d%d",&u,&v);
		printf("%d\n",lca(u,v));
	}
	return 0;
}

例题 \(2\)

给定一棵树，\(n\) 个点，\(m\) 条边，每条边有边权。每次询问给定两个点 \(i\) 和 \(j\)，询问从 \(i\) 到 \(j\) 路径的边权最大值。

在原有基础上，添加 \(fe[i,j]\) 来表示从 \(i\) 点向根节点方向走 \(2^j\) 步所经过的所有边的最大值。

int depth[N];//代表每个节点的深度
int f[N][20];// f[i][j] 代表从 i 向上走 2^j 步会走到哪里 
int fe[N][20];// fe[i][j] 代表从 i 向上走 2^j 步经过的所有边的最大值 
vector<pair<int,int> >g[N];
void dfs(int i,int j,int d){
//当前要搜索的是第 i 个点，是从 i 的父亲 j 走到 i，从父亲 j 到 i 的边的长度为 d 
	f[i][0]=j;
	for(int k=1;k<20;k++) f[i][k]=f[f[i][k-1]][k-1];
	fe[i][0]=d;
	for(int k=1;k<20;k++) fe[i][k]=max(fe[i][k-1],fe[f[i][k-1]][k-1]);
	depth[i]=depth[j]+1;
	for(int k=0;k<(int)g[i].size();k++){
		int l=g[i][k].first;//i->l
		int d=g[i][k].second;
		if(l!=j) dfs(l,i,d);
	}
}
int lca(int p1,int p2){//求 p1 和 p2 的路径上的最大值 
	int ans=0; 
	// 1. 把 p1 和 p2 两个点的深度调整成一样的
	if(depth[p1]<depth[p2]) swap(p1,p2);
	for(int i=19;i>=0;i--){
		if(depth[f[p1][i]]>=depth[p2]){
			ans=max(ans,fe[p1][i]);
			p1=f[p1][i];
		}
	}
	if(p1==p2) return ans;
	// 2. 跳到 LCA
	for(int i=19;i>=0;i--){
		if(f[p1][i]!=f[p2][i]){
			ans=max(ans,max(fe[p1][i],fe[p2][i]));
			p1=f[p1][i];
			p2=f[p2][i];
		}
	}
	ans=max(ans,max(fe[p1][0],fe[p2][0]));
	return ans;
}

Day 4

Part 1.上午

最短路

三角不等式

用 \(dist[i,j]\) 表示从 \(i\) 到 \(j\) 的最短路。那么 \(dist[i,j] \le dist[i,k]+dist[k,j]\)​。

\(\mathrm{Floyd}\)

例题 \(1\)​ B3647 【模板】Floyd

int n,m,dis[105][105],u,v,w;
int main(){
    memset(dis,0x3f,sizeof(dis));
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&u,&v,&w);
        dis[u][v]=dis[v][u]=w;
    }
    for(int i=1;i<=n;i++) dis[i][i]=0;
    for(int k=1;k<=n;k++){
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) printf("%d ",dis[i][j]);
        printf("\n");
    }
	return 0;
}

\(\mathrm{Dijkstra}\)

时间复杂度 \(O(n^2+m)\)

// dist[i] 代表从 s 到 i 的最短路
// vis[i] 表示 i 的最短路有没有求出来
vector<pair<int,int> >g[N];
void dijkstra(int s){//起点为 s 
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	for(int i=1;i<=n;i++){//O(n^2+m)
		//选一个 dist 值最小的点
		int p=0;
		for(int j=1;j<=n;j++){//O(n^2)
			if(!vis[j]&&(p==0||dist[j]<dist[p])) p=j;
		} 
		vis[p]=true;
		//用这个点去做松弛操作
		for(int j=0;j<(int)g[p].size();j++){//O(m) 
			int q=g[p][j].first,d=g[p][j].second;//这是一条从 p 到 q 长度为 d 的边
			if(dist[q]>dist[p]+d) dist[q]=dist[p]+d; 
		}
	}
} 

\(\mathrm{Dijkstra}\)​ 堆优化

时间复杂度：

\(\mathrm{STL}\) 堆：\(O((n+m) \log (n+m))\)

手写堆：\(O((n+m) \log n)\)

斐波那契堆：\(O(m+n\log n)\)

// dist[i] 代表从 s 到 i 的最短路
// vis[i] 表示 i 的最短路有没有求出来
vector<pair<int,int> >g[N];
void dijkstra(int s){//起点为 s 
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	priority_queue<pair<int,int> >heap;// first 用来存距离的相反数 ，second 用来存点的编号 
	// pair 优先比较 first 的大小 
	for(int i=1;i<=n;i++) heap.push(make_pair(-dist[i],i));
	for(int i=1;i<=n;i++){//O((n+m)log(n+m))
		//选一个 dist 值最小的点
		while(vis[heap.top().second]) heap.pop();
		int p=heap.top().second;
		heap.pop();
		vis[p]=true;
		//用这个点去做松弛操作
		for(int j=0;j<(int)g[p].size();j++){//O(m) 
			int q=g[p][j].first,d=g[p][j].second;//这是一条从 p 到 q 长度为 d 的边
			if(dist[q]>dist[p]+d){
				dist[q]=dist[p]+d;
				heap.push(make_pair(-dist[q],q));
			}
		}
	}
}

另一种写法

vector<pair<int,int> >g[N];
void dijkstra(int s){
	memset(dist,0x3f,sizeof(dist));
	priority_queue<pair<int,int> >q;
	q.push(make_pair(0,s));
	dist[s]=0;
	while(!q.empty()){
		int tp=q.top().second;
		q.pop();
		if(vis[tp]) continue;
		vis[tp]=true;
		for(int i=0;i<(int)g[tp].size();i++){
			int v=g[tp][i].first,w=g[tp][i].second;
			if(dist[v]>dist[tp]+w){
				dist[v]=dist[tp]+w;
				if(!vis[v]) q.push(make_pair(-dist[v],v));
			}
		}
	}
}

\(\mathrm{Bellman -Ford}\)

int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&u[i],&v[i],&w[i]);
	memset(dist,0x3f,sizeof(dist));
	dist[1]=0;
	for(int i=1;i<n;i++){//O(nm)
		for(int j=1;j<=m;j++) dist[v[j]]=min(dist[v[j]],dist[u[j]]+w[j]);
	}
	return 0;
}

\(\mathrm{SPFA}\)​

时间复杂度

一般 \(O(km)\)。因为 \(k\) 的范围基本在 \(100\) 到 \(200\) 之间，可以看作 \(O(m)\)

最坏 \(O(nm)\)

// dist[i]：从 s 到 i 的最短路
// vis[i]：i 在不在队列里
void spfa(int s){//起点为 s 
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	queue<int> q;//用来存可能改变其它点最短路的点
	vis[s]=true;
	q.push(s);
	while(!q.empty()){
		int p=q.front();
		q.pop();
		vis[p]=false;
		for(int i=0;i<(int)g[p].size();i++){
			int e=g[p][i].first,d=g[p][i].second;
            //从 p 到 e 长度为 d 的边
			if(dist[e]+dist[p]+d){
				dist[e]=dist[p]+d;
				if(!vis[e]){
					q.push(e);
					vis[e]=true;
				}
			}
		}
	}
} 

\(\mathrm{SPFA}\) 优化一般为改变搜索顺序。

差分约束

例题 \(1\)

给定 \(n\) 个变量 \(x_1,x_2, \dots ,x_n\) 和\(m\) 个不等式，每个不等式的形式均为 \(x_i-x_j \le y\)。求满足所有不等式的情况下，求 \(x_n-x_1\) 的最大值。

对于任意不等式 \(x_i - x_j \le y\)。将三角不等式转化为 \(dist[i]-dist[j] \le d\) 。那么对于不等式 \(x_i - x_j \le y\) ，就是从 \(j\) 向 \(i\) 连一条边权为 \(y\) 的边。

对于求 \(x_n-x_1\) 的最大值，令 \(x_1=0\) ，也就是 \(dist[1]=0\)，那么\(dist[n]\) 的值也就是 \(x_n\)​ 。

例题 \(2\)​​ P5960 【模板】差分约束

例题 \(3\)​​ P3275 [SCOI2011] 糖果

这道题最终答案求的是某个 \(x_i\) 的最小值，而不是像差分约束的 \(x_i-x_j\) 的最小值。

求 \(x_i\) 的最小值等价于求 \(x_i-0\) 的最小值，设 \(x_0=0\) ，那么这个问题就变成了 \(x_i-x_0\) 的最小值。建一个超级源点 \(x_0\) ，向 \(x_1 \dots x_n\) 连边，跑最长路。

例题 \(4\)

给定 \(N \times N\) 的矩阵，每次可以将某一行或某一列随便乘以一个数（可以是小数，但是必须为正数），问能否使得所有数的都在 \([l,r]\) 之间。

根据题意，显然有不等式 \(l \le a_{i,j} \cdot b_i \cdot c_j \le r\)，转化一下，对于整个不等式都 \(\log\) 一下，$ \log l \le \log a_{i,j}+\log b_i +\log c_j \le \log r$，这样就符合差分约束的不等式形式，很容易建图。

判断有无解就是建图后判断有没有负环。

那么怎样判负环？显然是 \(\mathrm{SPFA}\)​ 。

方法 \(1\)：卡时

// dist[i]：从 s 到 i 的最短路
// vis[i]：i 在不在队列里
void spfa(int s){//起点为 s 
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	queue<int> q;//用来存可能改变其它点最短路的点
	vis[s]=true;
	q.push(s);
	while(!q.empty()){
		if(clock*1000>=900*CLOCKS_PER_SEC){
			大概率有负环;
			exit(0); 
		}
		int p=q.front();
		q.pop();
		vis[p]=false;
		for(int i=0;i<(int)g[p].size();i++){
			int e=g[p][i].first,d=g[p][i].second;
            //从 p 到 e 长度为 d 的边
			if(dist[e]+dist[p]+d){
				dist[e]=dist[p]+d;
				if(!vis[e]){
					q.push(e);
					vis[e]=true;
				}
			}
		}
	}
} 

方法 \(2\)：

// dist[i]：从 s 到 i 的最短路
// vis[i]：i 在不在队列里
// cnt[i]：i 被加入队列的次数 
void spfa(int s){//起点为 s 
	memset(dist,0x3f,sizeof(dist));
	dist[s]=0;
	queue<int> q;//用来存可能改变其它点最短路的点
	vis[s]=true;
	q.push(s);
	while(!q.empty()){
		int p=q.front();
		if(cnt[p]>n){
			有负环;
			return; 
		}
		q.pop();
		vis[p]=false;
		for(int i=0;i<(int)g[p].size();i++){
			int e=g[p][i].first,d=g[p][i].second;
            //从 p 到 e 长度为 d 的边
			if(dist[e]+dist[p]+d){
				dist[e]=dist[p]+d;
				if(!vis[e]){
					q.push(e);
					vis[e]=true;
					cnt[e]++;
				}
			}
		}
	}
} 

但是方法 \(2\) 很容易超时，考试时最好还是用卡时。

Part 2.下午

最小生成树

\(\mathrm{Kruscal}\)

先把所有边按照边权从小到大排序，然后依次从小到大加进去，如果构成了环就删除，最后把组成最小生成树的边的边权求和。

判环使用并查集。如果两个点在并查集中不断走，最终到同一个点，那么这两个点就在同一个连通块中。

时间复杂度 \(O(m \log m)\)

例题 \(1\) ：P3366 【模板】最小生成树

const int N=5e5+5;
int n,m,fa[N];// fa[i]  i 点在并查集里的箭头指向谁
inline int find(int x){//点 x 沿着并查集箭头最后会走到哪里 
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
struct edge{
	int u,v,w;
}e[N];// e[i] 代表第 i 条边是在 u 和 v 之间长度为 w 的边 
inline bool cmp(edge x,edge y){
	return x.w<y.w;
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	int ans=0;//生成树大小
	for(int i=1;i<=m;i++){//O(m)
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)!=find(v)){
			ans=ans+w;
			fa[find(u)]=find(v);
		}
	} 
	printf("%d",ans);
	return 0;
}

例题 \(2\) HDU4786 Fibonacci Tree

给定 \(n\) 个点 \(m\) 条边，每条边是黑色或白色，问是否存在某一棵生成树，使得白色边的数量是斐波那契数列中的某一项。如果存在，输出 \(Yes\) ，否则输出 \(No\) 。

\(n,m \le 10^5\)

假设白色边的边权为 \(0\) ，黑色边的边权为 \(1\) 。

先求最小生成树，假设用了 \(x\) 条白边，那么代表着最多使用 \(x\) 条白边。

再求最大生成树，假设用了 \(y\) 条白边，那么代表着最少使用 \(y\) 条白边。

只需要判断是否有 \(y \le fibonacci_i \le x\) ，是就输出 \(Yes\)，否则输出 \(No\) 。

次小生成树

在最小生成树的基础上，删一条树边，加一条非树边。

const int N=5e5+5;
int n,m,fa[N];// fa[i]  i 点在并查集里的箭头指向谁
inline int find(int x){//点 x 沿着并查集箭头最后会走到哪里 
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
struct edge{
	int u,v,w;
	bool on_tree;
}e[N];// e[i] 代表第 i 条边是在 u 和 v 之间长度为 w 的边 
inline bool cmp(edge x,edge y){
	return x.w<y.w;
} 
int depth[N];// depth 数组代表每个节点的深度
int f[N][20];// f[i][j] 代表从 i 向上走 2^j 步会走到哪里 
int fe[N][20];// fe[i][j] 代表从 i 向上走 2^j 步经过的所有边的最大值 
vector<pair<int,int> >g[N];
void dfs(int i,int j,int d){
//当前要搜索的是第 i 个点，是从 i 的父亲 j 走到 i，从父亲 j 到 i 的边的长度为 d 
	f[i][0]=j;
	for(int k=1;k<20;k++) f[i][k]=f[f[i][k-1]][k-1];
	fe[i][0]=d;
	for(int k=1;k<20;k++) fe[i][k]=max(fe[i][k-1],fe[f[i][k-1]][k-1]);
	depth[i]=depth[j]+1;
	for(int k=0;k<(int)g[i].size();k++){
		int l=g[i][k].first;//i->l
		int d=g[i][k].second;
		if(l!=j) dfs(l,i,d);
	}
}
int get_max(int p1,int p2){//求 p1 和 p2 的路径上的最大值 
	int ans=0; 
	// 1. 把 p1 和 p2 两个点的深度调整成一样的
	if(depth[p1]<depth[p2]) swap(p1,p2);
	for(int i=19;i>=0;i--){
		if(depth[f[p1][i]]>=depth[p2]){
			ans=max(ans,fe[p1][i]);
			p1=f[p1][i];
		}
	}
	if(p1==p2) return ans;
	// 2. 跳到 LCA
	for(int i=19;i>=0;i--){
		if(f[p1][i]!=f[p2][i]){
			ans=max(ans,max(fe[p1][i],fe[p2][i]));
			p1=f[p1][i];
			p2=f[p2][i];
		}
	}
	ans=max(ans,max(fe[p1][0],fe[p2][0]));
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	int ans=0;//生成树大小
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)!=find(v)){
			ans=ans+w;
			fa[find(u)]=find(v);
			g[u].push_back(make_pair(v,w));
			g[v].push_back(make_pair(u,w));
			e[i].on_tree=true;
		}
		else e[i].on_tree=false;
	} 
	dfs(1,0,0);
	int res=0x3f3f3f3f;
	for(int i=1;i<=m;i++){
		if(!e[i].on_tree){
			int u=e[i].u,v=e[i].v,w=e[i].w;
			res=min(res,ans-get_max(u,v)+w);
		} 
	}
	printf("%d",res);
	return 0;
}

例题 \(1\) P4180 [BJWC2010] 严格次小生成树

WA on #4

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<vector>
#include<climits>
#define int long long
using namespace std;
const int N=5e5+5;
int n,m,fa[N];
inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
struct edge{
	int u,v,w;
	bool on_tree;
}e[N];
inline bool cmp(edge x,edge y){
	return x.w<y.w;
} 
int depth[N],f[N][25],fe[N][25];
vector<pair<int,int> >g[N];
void dfs(int i,int j,int d){
	f[i][0]=j;
	for(int k=1;k<=20;k++) f[i][k]=f[f[i][k-1]][k-1];
	fe[i][0]=d;
	for(int k=1;k<=20;k++) fe[i][k]=max(fe[i][k-1],fe[f[i][k-1]][k-1]);
	depth[i]=depth[j]+1;
	for(int k=0;k<g[i].size();k++){
		int l=g[i][k].first;
		int d=g[i][k].second;
		if(l!=j) dfs(l,i,d);
	}
}
int get_max(int p1,int p2){
	int ans=0;
	if(depth[p1]<depth[p2]) swap(p1,p2);
	for(int i=20;i>=0;i--){
		if(depth[f[p1][i]]>=depth[p2]){
			ans=max(ans,fe[p1][i]);
			p1=f[p1][i];
		}
	}
	if(p1==p2) return ans;
	for(int i=20;i>=0;i--){
		if(f[p1][i]!=f[p2][i]){
			ans=max(ans,max(fe[p1][i],fe[p2][i]));
			p1=f[p1][i];
			p2=f[p2][i];
		}
	}
	ans=max(ans,max(fe[p1][0],fe[p2][0]));
	return ans;
}
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	int ans=0;
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(u==v) continue;
		if(find(u)!=find(v)){
			ans=ans+w;
			fa[find(u)]=find(v);
			g[u].push_back(make_pair(v,w));
			g[v].push_back(make_pair(u,w));
			e[i].on_tree=true;
		}
		else e[i].on_tree=false;
	}
	dfs(1,0,0);
	int res=LONG_LONG_MAX;
	for(int i=1;i<=m;i++){
		if(!e[i].on_tree){
			int u=e[i].u,v=e[i].v,w=e[i].w;
			if(u==v) continue;
			res=min(res,ans-get_max(u,v)+w);
		} 
	}
	printf("%lld",res);
	return 0;
}
/*
hack

in:
7 15
6 3 35
1 6 44
3 2 22
2 7 57
5 1 57
5 6 65
5 3 44
7 4 57
7 2 44
7 1 44
4 5 44
4 5 44
2 3 65
1 7 44
1 2 44

out:
242
*/

例题 \(2\) P1967 [NOIP2013 提高组] 货车运输

最优走法一定是沿着最大生成树走。

const int N=5e5+5;
int n,m,q,fa[N];
bool vis[N];
inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
struct edge{
	int u,v,w;
}e[N];
inline bool cmp(edge x,edge y){
	return x.w>y.w;
} 
int depth[N],f[N][25],fe[N][25];
vector<pair<int,int> >g[N];
void dfs(int i,int j,int d){
	vis[i]=true;
	f[i][0]=j;
	for(int k=1;k<=20;k++) f[i][k]=f[f[i][k-1]][k-1];
	fe[i][0]=d;
	for(int k=1;k<=20;k++) fe[i][k]=min(fe[i][k-1],fe[f[i][k-1]][k-1]);
	depth[i]=depth[j]+1;
	for(int k=0;k<(int)g[i].size();k++){
		int l=g[i][k].first;
		int d=g[i][k].second;
		if(l!=j) dfs(l,i,d);
	}
}
int lca(int p1,int p2){
	if(find(p1)!=find(p2)) return -1;
	int ans=INT_MAX;
	if(depth[p1]<depth[p2]) swap(p1,p2);
	for(int i=20;i>=0;i--){
		if(depth[f[p1][i]]>=depth[p2]){
			ans=min(ans,fe[p1][i]);
			p1=f[p1][i];
		}
	}
	if(p1==p2) return ans;
	for(int i=20;i>=0;i--){
		if(f[p1][i]!=f[p2][i]){
			ans=min(ans,min(fe[p1][i],fe[p2][i]));
			p1=f[p1][i];
			p2=f[p2][i];
		}
	}
	ans=min(ans,min(fe[p1][0],fe[p2][0]));
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)!=find(v)){
			fa[find(u)]=find(v);
			g[u].push_back(make_pair(v,w));
			g[v].push_back(make_pair(u,w));
		}
	}
	for(int i=1;i<=n;i++) if(!vis[i]) dfs(i,0,0);
	scanf("%d",&q);
	while(q--){
		int x,y;
		scanf("%d%d",&x,&y);
		printf("%d\n",lca(x,y));
	}
	return 0;
}

例题 \(3\) P3280 [SCOI2013] 摩托车交易

最优走法一定是沿着最大生成树走。

由题意知，只需要求卖黄金的量。假设当走到 \(i\) 点时原来有 \(w\) 些黄金，在这个点可以买 \(x\) 些黄金， 策略为把 \(x\) 些黄金全部买入，这样当前的黄金数量就变成了\(x+w\) 。接下来到点 \(j\) ，通过在最大生成树上倍增，可以求出最小限重 \(y\) ，意味着从 \(i\) 点到 \(j\) 点最多携带数量为 \(y\) 的黄金，那么到 \(j\) 点时所携带的黄金数量为 \(\min(x+w,y)\)​ 。

显然，最终策略是：在买点全买，在卖点全卖。

#define int long long
const int N=5e5+5;
int n,m,q,val[N],b[N],fa[N],nw;
inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
struct edge{
	int u,v,w;
}e[N<<1];
inline bool cmp(edge x,edge y){
	return x.w>y.w;
} 
int depth[N],f[N][25],fe[N][25];
vector<pair<int,int> >g[N];
void dfs(int i,int j,int d){
	f[i][0]=j;
	for(int k=1;k<=20;k++) f[i][k]=f[f[i][k-1]][k-1];
	fe[i][0]=d;
	for(int k=1;k<=20;k++) fe[i][k]=min(fe[i][k-1],fe[f[i][k-1]][k-1]);
	depth[i]=depth[j]+1;
	for(int k=0;k<(int)g[i].size();k++){
		int l=g[i][k].first;
		int d=g[i][k].second;
		if(l!=j) dfs(l,i,d);
	}
}
int get_min(int p1,int p2){
	int ans=LONG_LONG_MAX;
	if(depth[p1]<depth[p2]) swap(p1,p2);
	for(int i=20;i>=0;i--){
		if(depth[f[p1][i]]>=depth[p2]){
			ans=min(ans,fe[p1][i]);
			p1=f[p1][i];
		}
	}
	if(p1==p2) return ans;
	for(int i=20;i>=0;i--){
		if(f[p1][i]!=f[p2][i]){
			ans=min(ans,min(fe[p1][i],fe[p2][i]));
			p1=f[p1][i];
			p2=f[p2][i];
		}
	}
	ans=min(ans,min(fe[p1][0],fe[p2][0]));
	return ans;
}
inline int max(int a,int b){
    return a>b?a:b;
}
inline int min(int a,int b){
    return a>b?b:a;
}
signed main(){
	scanf("%lld%lld%lld",&n,&m,&q);
	for(int i=1;i<=n;i++) scanf("%lld",&val[i]);
	for(int i=1;i<=n;i++) scanf("%lld",&b[i]);
	for(int i=1;i<=m;i++) scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);
	for(int i=m+1;i<=m+q;i++){
		scanf("%lld",&e[i].u);
		e[i].v=n+1,e[i].w=LONG_LONG_MAX;
	}
	sort(e+1,e+1+m+q,cmp);
	for(int i=1;i<=n+1;i++) fa[i]=i;
	for(int i=1;i<=m+q;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)!=find(v)){
			fa[find(u)]=find(v);
			g[u].push_back(make_pair(v,w));
			g[v].push_back(make_pair(u,w));
		}
	}
	dfs(1,0,0);
	val[n+1]=val[n];
	for(int i=1;i<=n;i++){
		if(b[val[i]]>0) nw=min(get_min(val[i],val[i+1]),nw+b[val[i]]);
		else{
			printf("%lld\n",min(nw,-b[val[i]]));
			nw=min(get_min(val[i],val[i+1]),nw-min(nw,-b[val[i]]));
		}
	}
	return 0;
}

例题 \(4\) Cheap Robot

给定一个 \(n\) 个点的无向连通带权图和 \(k\) 个充电中心，共有 \(q\) 次询问，每次询问要求机器人从 \(p\) 走到 \(q\) ，问每次机器人电池容量最少是多少。

\(n,m,k,q \le 10^5\)，保证起点和终点都能充电。

建一个超级源点为发电站，向每个充电中心都连一条长度为 \(0\) 的边，从发电站跑一遍到所有点的最短路，这时求出的 \(dist[i]\) 就是第 \(i\) 号点到发电站的最短距离，也就是到第 \(i\) 个点到距离它最近的充电中心的距离。

假设当前机器人在 \(i\) 号点，电池容量为 \(c\) ，剩余电量为 \(x\) ，点 \(x\) 的取值范围是 \(dist[i] \le x \le c-dist[i]\) 。\(i\) 点的下一个点为 \(j\) ，长度为 \(d\) ，这时的剩余电量为 \(x-d\) ，剩余电量的取值范围是 \(dist[j] \le x-d \le c-dist[j]\) 。上面两个不等式可以转化为 \(dist[i] -d\le c-dist[j]\) ，也就是 \(dist[i]+dist[j]-d \le c\)。

那么问题就转化成了 求从 \(p\) 到 \(q\) 之间的最短路上的边权最大值最小。那么最优方案就是按照最小生成树走，然后倍增求 \(\mathrm{LCA}\) 即可。

#define int long long
const int N=5e5+5;
int n,m,k,q,fa[N],dist[N];
bool vis[N];
inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
struct edge{
	int u,v,w;
}e[N<<1];
inline bool cmp(edge x,edge y){
	return x.w<y.w;
} 
int depth[N],f[N][25],fe[N][25];
vector<pair<int,int> >g[N],ed[N];
void dfs(int i,int j,int d){
	f[i][0]=j;
	for(int k=1;k<=20;k++) f[i][k]=f[f[i][k-1]][k-1];
	fe[i][0]=d;
	for(int k=1;k<=20;k++) fe[i][k]=max(fe[i][k-1],fe[f[i][k-1]][k-1]);
	depth[i]=depth[j]+1;
	for(int k=0;k<(int)g[i].size();k++){
		int l=g[i][k].first;
		int d=g[i][k].second;
		if(l!=j) dfs(l,i,d);
	}
}
int get_max(int p1,int p2){
	int ans=0;
	if(depth[p1]<depth[p2]) swap(p1,p2);
	for(int i=20;i>=0;i--){
		if(depth[f[p1][i]]>=depth[p2]){
			ans=max(ans,fe[p1][i]);
			p1=f[p1][i];
		}
	}
	if(p1==p2) return ans;
	for(int i=20;i>=0;i--){
		if(f[p1][i]!=f[p2][i]){
			ans=max(ans,max(fe[p1][i],fe[p2][i]));
			p1=f[p1][i];
			p2=f[p2][i];
		}
	}
	ans=max(ans,max(fe[p1][0],fe[p2][0]));
	return ans;
}
void dijkstra(int s){
	memset(dist,0x3f,sizeof(dist));
	priority_queue<pair<int,int> >q;
	q.push(make_pair(0,s));
	dist[s]=0;
	while(!q.empty()){
		int tp=q.top().second;
		q.pop();
		if(vis[tp]) continue;
		vis[tp]=true;
		for(int i=0;i<(int)ed[tp].size();i++){
			int v=ed[tp][i].first,w=ed[tp][i].second;
			if(dist[v]>dist[tp]+w){
				dist[v]=dist[tp]+w;
				if(!vis[v]) q.push(make_pair(-dist[v],v));
			}
		}
	}
}
signed main(){
	scanf("%lld%lld%lld%lld",&n,&m,&k,&q);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&e[i].u,&e[i].v,&e[i].w);
		int u=e[i].u,v=e[i].v,w=e[i].w;
		ed[u].push_back(make_pair(v,w));
		ed[v].push_back(make_pair(u,w));
	}
	for(int i=1;i<=k;i++){
		ed[0].push_back(make_pair(i,0));
		ed[i].push_back(make_pair(0,0));
	} 
	dijkstra(0);
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		e[i].w=dist[u]+dist[v]+w;
	}
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)!=find(v)){
			fa[find(u)]=find(v);
			g[u].push_back(make_pair(v,w));
			g[v].push_back(make_pair(u,w));
		}
	}
	dfs(1,0,0);
	while(q--){
		int u,v;
		scanf("%lld%lld",&u,&v);
		printf("%lld\n",get_max(u,v)); 
	}
	return 0;
}

次小生成树优化

假设读入的边是排好序的，将复杂度降为 \(O(n+m)\)​ 。

可以发现，非树边显然有序，所以添加一条非树边的枚举次序也是从小到大枚举。假设最小的非树边为 \(d_1\) ，那么用 \(d_1\) 可以替换的这 \(x\) 条边用其它非树边来替换显然是没有用 \(d_1\) 替换更优。用并查集将这 \(x\) 条边 \(merge\) 在一起。这样每条边只需要判断 \(1\)​ 次。

const int N=5e5+5;
int n,m,fa[N];// fa[i]  i 点在并查集里的箭头指向谁
inline int find(int x){//点 x 沿着并查集箭头最后会走到哪里 
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
}
struct edge{
	int u,v,w;
	bool on_tree;
}e[N];// e[i] 代表第 i 条边是在 u 和 v 之间长度为 w 的边 
inline bool cmp(edge x,edge y){
	return x.w<y.w;
} 
int depth[N];// depth 数组代表每个节点的深度
int f[N];// f[i] 代表 i 的父亲 
int fe[N];// fe[i] 代表 i 到它父亲节点的边长 
vector<pair<int,int> >g[N];
void dfs(int i,int j,int d){
//当前要搜索的是第 i 个点，是从 i 的父亲 j 走到 i，从父亲 j 到 i 的边的长度为 d 
	f[i]=j;
	fe[i]=d;
	depth[i]=depth[j]+1;
	for(int k=0;k<(int)g[i].size();k++){
		int l=g[i][k].first;//i->l
		int d=g[i][k].second;
		if(l!=j) dfs(l,i,d);
	}
}
int get_max(int p1,int p2){//求 p1 和 p2 的路径上的最大值 
	int ans=0; 
	p1=find(p1),p2=find(p2);
	while(p1!=p2){
		if(depth[p1]<depth[p2]) swap(p1,p2);
		ans=max(ans,fe[p1]);
		fa[find(p1)]=find(fa[p1]);
		p1=find(p1);
	}
	return ans;
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++) scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
	sort(e+1,e+1+m,cmp);
	for(int i=1;i<=n;i++) fa[i]=i;
	int ans=0;//生成树大小
	for(int i=1;i<=m;i++){
		int u=e[i].u,v=e[i].v,w=e[i].w;
		if(find(u)!=find(v)){
			ans=ans+w;
			fa[find(u)]=find(v);
			g[u].push_back(make_pair(v,w));
			g[v].push_back(make_pair(u,w));
			e[i].on_tree=true;
		}
		else e[i].on_tree=false;
	} 
	dfs(1,0,0);
	int res=0x3f3f3f3f;
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++){
		if(!e[i].on_tree){
			int u=e[i].u,v=e[i].v,w=e[i].w;
			res=min(res,ans-get_max(u,v)+w);
		} 
	}
	printf("%d",res);
	return 0;
}

并查集维护连通性

上面对次小生成树的优化就是用了这种方法。

例题 \(1\) BZOJ2054 疯狂的馒头

给定 \(n\) 个数 \(a_1,a_2, \dots, a_n\) ，有 \(m\) 次操作，每次操作给定 \(l,r\) 和 \(v\) ，将 \(a_l,a_{l+1}, \dots, a_r\) 的值全部赋值为 \(v\) ，最后输出 \(a_1,a_2, \dots, a_n\) 的值。

\(n,m \le 10^6\)

使用并查集求解。对于每次被赋值的区间，从 \(l\) 到 \(r\) \(merge\) 一下，那么后面如果赋值经过该块时，暴力赋值就会从块首 \(l\) 跳到 \(r\) ，然后继续暴力赋值。这样就保证了每个元素只会被赋值一次，时间复杂度 \(O(m+n)\) 。

int n,m,fa[N],a[N];
inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
} 
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=1;i<=m;i++) scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].v);
	for(int i=m;i>=1;i--){
		int l=q[i].l,r=q[i].r,v=q[i].v;//将区间 l ~ r 染色成 v 
		for(int j=l;j<=r;j++){
			j=find(j);
			if(j<=r){
				fa[find(j)]=find(r);
				if(!a[j]) a[j]=v;
			} 
		}
	}
	for(int i=1;i<=n;i++) printf("%d\n",a[i]);
	return 0;
}

例题 \(2\) P2391 白雪皑皑

等同于例题 \(1\)

const int N=1e6+5;
int n,m,p,q,fa[N],a[N];
inline int find(int x){
	if(fa[x]==x) return x;
	return fa[x]=find(fa[x]);
} 
int main(){
	scanf("%d%d%d%d",&n,&m,&p,&q);
	for(int i=1;i<=n;i++) fa[i]=i;
	for(int i=m;i>=1;i--){
		int l=(i*p+q)%n+1,r=(i*q+p)%n+1,v=i;
		if(l>r) swap(l,r);
		for(int j=l;j<=r;j++){
			j=find(j);
			if(j<=r){
				fa[find(j)]=find(r);
				if(!a[j]) a[j]=v;
			} 
		}
	}
	for(int i=1;i<=n;i++) printf("%d\n",a[i]);
	return 0;
}

Day 5

Part 1.上午

二分图匹配

匈牙利算法

最坏情况下，时间复杂度 \(O(n \times 边数)\)。

例题 \(1\) P3386 【模板】二分图最大匹配 & B3605 [图论与代数结构 401] 二分图匹配

const int N=5e4+5;
int n,m,k,cnt,result[N];// result[i] 表示右边第 i 个点和左边的第 result[i] 个点匹配 
vector<int> g[N];// g[i] 代表左边的第 i 个点的第 j 条边连向谁 
bool vis[N];// vis[i] 表示右边第 i 个点在这一轮中有没有被请求过匹配
bool dfs(int i){//让左边第 i 个点尝试匹配，返回是否成功 
	for(int k=0;k<(int)g[i].size();k++){
		int j=g[i][k];
		if(!vis[j]){
			vis[j]=true;
			if(!result[j]||dfs(result[j])){
				result[j]=i;
				return true;
			}
		} 
	} 
	return false;
}
int main(){
	scanf("%d%d%d",&n,&m,&k);
	for(int i=1;i<=k;i++){
		int p1,p2;
		scanf("%d%d",&p1,&p2);
		g[p1].push_back(p2);
	}
	for(int i=1;i<=n;i++){
		memset(vis,false,sizeof(vis));
		if(dfs(i)) cnt++;//左边第 i 个点匹配成功，答案+1 
	}
	printf("%d",cnt);
	return 0; 
} 

例题 \(2\) TYVJ1035 棋盘覆盖

给定一个 \(n\) 行 \(m\) 列的方格图。每个方格都有三种可能的状态，标记为 \(\mathrm{X}\) 的为障碍物，其余点被染成黑或白。现在有一些小方块，大小为 \(1 \times 2\)，保证这个方块中的两个方格一黑一白，且可以任意旋转。要求放置小方块时黑对黑、白对白，且任意两个小方块不能重叠，求最多放置多少个小方块。

把小方块看作一条边。把所有黑方格放在左边，白方格放在右边。如果一个黑方格和一个白方格相邻，那么就在它们之间连一条边。然后对二分图求最大匹配即可。

例题 \(3\) HDU5093 Battle ships

给定一个 \(n\) 行 \(m\) 列的方格图，其中有一些障碍物。有一个人，他所能看见的范围是上下左右没有被障碍物遮挡住的。求最多放几个人，使得他们互相看不见。

把每个人看作一条边。显然，每个被障碍物隔开的小行都只能放置一个人，同理，每个被障碍物隔开的小列也都只能放置一个人。把所有小行放在左边，把所有小列放在右边。如果一个小行和一个小列有交点，那么就在它们之间连一条边（在交点上放置一个人）。然后对二分图求最大匹配即可。

例题 \(4\) HDU2819 Swap

给定一个 \(0/1\) 矩阵，问能否通过交换方格图的两行两列，使得对角线上的元素都为 \(1\)。

\(n,m \le 100\)

把每一行的编号放在左边，把每一列的编号放在右边。如果它们的交点为 \(1\)​ ，就在它们之间连一条边。然后对二分图求最大匹配即可。

强连通分量

在有向图中，要找到若干个点和若干条边，使得找出的这些点能够互相走到其它点。这些点组成的这张图称之为强连通分量。

\(\mathrm{Tarjan}\)

先对这张有向图跑一遍 \(\mathrm{DFS}\) ，要求每个点只走一次。那么按照每个点被 \(\mathrm{DFS}\) 到的顺序可以构成一棵树。实际上，找强连通分量就是在找环。和生成树同理，把构成树的边称为树边，其它边成为非数边。显然，按照被 \(\mathrm{DFS}\) 到的顺序所构成的树并不存在环，那么就只能在树上添加非树边来组成环。也就是要找能组成环的非树边。

那什么样的非树边能构成环？

如果从当前点连出一条边连到了自己的祖先，那么称该边为回边。

如果一条非树边是回边，那么就能构成环。

如果从当前点连出一条边到一个既非它子孙、也非它祖先的点，那么称该边为横叉边。

横叉边不能构成环，但是一些横叉边可以扩大环。

vector<int> g[N];
int cnt;//有几个强连通分量
int belong[N];// belong[i] 代表第 i 个点属于哪个强连通分量 
int num;//当前已经 dfs 了 num 个点 
int dfn[N];// dfn[i] 代表第 i 个点是第几个被 dfs 到的 
int low[N];// low[i] 代表从 i 点出发，沿着 回边 、树边 或者 能扩大环的横叉边 走，能走到的所有点中 dfn 最小的是多少 
stack<int> s;//栈用来存储 "被 dfs 过，但还没有求出强连通分量的点" 
bool instack[N];// instack[i] 代表第 i 个点是否在栈里面 
void dfs(int i){//当前搜索到了第 i 个点 
	num++;
	dfn[i]=low[i]=num;
	s.push(i);
	instack[i]=true;
	for(int k=0;k<(int)g[i].size();k++){
		int j=g[i][k];//从第 i 个点连出的第 k 条边连到了第 j 个点
		if(dfn[j]==0){//第 j 个点没有被 dfs 过（树边） 
			dfs(j);
			low[i]=min(low[i],low[j]);
		} 
		else{//（非树边） 
			//这是一条 回边 或 能扩大环的横叉边 
			if(instack[j]) low[i]=min(low[i],dfn[j]); 
		}
	}
	if(dfn[i]==low[i]){
		cnt++;//多了一个强连通分量 
		while(s.top()!=i){
			belong[s.top()]=cnt;
			instack[s.top()]=false;
			s.pop();
		} 
		s.pop();
		instack[i]=false;
		belong[i]=cnt; 
	}
}

例题 \(1\) B3609 [图论与代数结构 701] 强连通分量

const int N=1e5+5;
int n,m,belong[N],cnt,num,dfn[N],low[N];
bool instack[N],flag[N];
vector<int> g[N],blong[N];
stack<int> s;
void dfs(int i){
	num++;
	dfn[i]=low[i]=num;
	s.push(i);
	instack[i]=true;
	for(int k=0;k<(int)g[i].size();k++){
		int j=g[i][k];
		if(dfn[j]==0){ 
			dfs(j);
			low[i]=min(low[i],low[j]);
		} 
		else if(instack[j]) low[i]=min(low[i],dfn[j]); 
	}
	if(dfn[i]==low[i]){
		cnt++;
		while(s.top()!=i){
			belong[s.top()]=cnt;
			blong[cnt].push_back(s.top());
			instack[s.top()]=false;
			s.pop();
		} 
		s.pop();
		instack[i]=false;
		belong[i]=cnt;
		blong[cnt].push_back(i);
	}
}
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;i++){
		int p1,p2;
		scanf("%d%d",&p1,&p2);
		g[p1].push_back(p2);
	}
	for(int i=1;i<=n;i++) if(dfn[i]==0) dfs(i);
	printf("%d\n",cnt);
	for(int i=1;i<=cnt;i++) sort(blong[i].begin(),blong[i].end());
	for(int i=1;i<=n;i++){
		bool ck=true;
		for(int j=0;j<(int)blong[belong[i]].size();j++){
			if(flag[blong[belong[i]][j]]){
				ck=false;
				continue;
			}
			flag[blong[belong[i]][j]]=true;
			printf("%d ",blong[belong[i]][j]);
		}
		if(ck) printf("\n");
	}
	return 0;
}

\(\mathrm{2-SAT}\)

给定 \(n\) 个变量 \(x_1,x_2, \dots,x_n\)，每个变量的取值只有两种\(\mathrm{true}\) 和 \(\mathrm{false}\) 。除此之外，还有 \(m\) 个关系式（布尔表达式），问能否从 \(x_1 \dots x_n\) 中找到一些值，使这 \(m\)​ 个表达式的值都成立。

\(\mathrm{2-SAT}\) 问题与强连通分量的关系？

对于每个 \(x_i\) ，建 \(\mathrm{true}\) 和 \(\mathrm{false}\) 两个点，通过已知 \(x_i\) 的值和给出的关系式，来推导出 \(x_j\) 的值，并连接表示 \(x_i\) 值的点和表示 \(x_j\)​​ 值的点（有向边），然后根据推导关系建图，跑强连通分量

当 \(x_i\) 的 \(\mathrm{true}\) 和 \(\mathrm{false}\)​ 两种值在同一个强连通分量里时，无解。

例题 \(1\) Piece it together

给定一个 \(n\) 行 \(m\) 列的方格图。每个方格都有三种可能的状态，标记为 \(\mathrm{X}\) 的为障碍物，其余点被染成黑或白。现在有一些 \(L\)​ 型小方块，保证一黑两白，且可以任意旋转。要求放置小方块时黑对黑、白对白，且任意两个小方块不能重叠，问能否把除障碍物外的其它格子放满。

首先，先找出黑格子。有黑格子的地方肯定要放置一个小方块，假设不考虑障碍物的影响，一共有四种放置小方块的方式。

怎样把四种摆放方式转化成两种？

把白格子的取值拆成上下和左右两种，用两个变量表示，每一种不同的取值组合都会组成不同的 \(L\)​ 型，这样就转化成了只有两种取值。

例题 \(2\) The Ministers' Major Mess

给定 \(n\) 个人和 \(m\) 个提案，每个人会对不超过 \(4\) 个提案进行投票，可以投赞成和反对，每提案可能被通过或者否决（和票数没关系），要求每个人投票的结果有一半以上是和提案的结果是相吻合的。问对于每个提案是否一定被通过或者否决。

\(m \le 500\)

变量是每个人投票的 \(4\) 提案，取值是通过或否决。

怎样建边？

假设这个人对提案 \(1\) 和提案 \(2\) 都投了赞成，那么提案 \(1\) 和提案 \(2\) 都需要通过，从提案 \(1\) 和提案 \(2\) 的否决向通过连边。如果提案 \(3\) 也投了赞成，那就可能会有一个提案被否决。假设提案 \(1\) 被否决，那么提案 \(2\) 和提案 \(3\) 都必须通过，所以从提案 \(1\) 的否决向提案 \(2\) 和提案 \(3\) 的通过连边。提案 \(2\) 被否决和提案 \(3\)​ 被否决也是如此。同理，投了 \(4\) 个提案也是如此。

如果一个提案不满足，那么就从这个提案的不满足向其它提案的满足连边。

最后跑一遍强连通分量即可。

Part 2.下午

动态规划基础

斐波那契数列

\(f_i=f_{i-1}+f_{i-2}\)

\(f_i\) : 斐波那契数列第 \(i\)​ 项的值，也就是状态。

\(f_i=f_{i-1}+f_{i-2}\) ：描述状态与状态的关系，也就是状态转移方程。

\(f_0=0,f_1=1\)​​ ：初始化条件（边界条件），特殊情况下的状态。

写法 \(1\) ，用别的状态求当前的状态

int main(){
	scanf("%d",&n);
	f[0]=0,f[1]=1;
	for(int i=2;i<=n;i++) f[i]=f[i-1]+f[i-2];
	printf("%d",f[n]);
	return 0;
}

写法 \(2\) ，用当前的状态求别的状态

int main(){
	scanf("%d",&n);
	f[0]=0,f[1]=1;
	for(int i=0;i<=n;i++){
		f[i+1]=f[i+1]+f[i];
		f[i+2]=f[i+2]+f[i];
	}
	printf("%d",f[n]);
	return 0;
}

写法 \(3\) ，记忆化搜索（常用于博弈DP）

int f[N];// f[i] 表示斐波那契数列第 i 项的值 
bool g[i];// g[i] 表示斐波那契数列第 i 项是否被求出来 
int dfs(int n){
	if(n==0) return 0;
	if(n==1) return 1;
	if(g[n]) return f[n];
	g[n]=true;
	return f[n]=dfs(n-1)+dfs(n-2);
}
int main(){
	scanf("%d",&n);
	printf("%d",dfs(n));
	return 0;
}

例题 \(2\)

给定一个 \(n\) 行 \(m\) 列的方格图，起点为 \((1,1)\) ，终点为 \((n,m)\) 。每个点都有一个点权，每次移动可以向右或者向下走。求从起点到终点的路径上的点的点权之和最大值。

在不断移动中发生变化的值有位置和点权和。

那么状态就是 \(f[i,j]=点权和\)，代表走到 \((i,j)\)​ 时，能获得最大点权和是多少。

据上可得， \(\mathrm{DP}\)​ 题首先要找变化的量，由变化的量可得出状态。

写法 \(1\) ，用别的状态求当前的状态

int n,m;// n 行 m 列
int a[N][N];// a[i][j] 表示 (i,j) 的点权值 
int f[N][N];// f[i][j] 表示走到 (i,j) 时能获得的最大点权和是多少
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	}
	f[1][1]=a[1][1];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) f[i][j]=max(f[i][j-1],f[i-1][j])+a[i][j];//取上面和左面的最大值再加上当前点的点权，就是从起点到当前的所经过路径的点权最大值 
	}
	printf("%d",f[n][m]);
	return 0;
} 

写法 \(2\) ，用当前的状态求别的状态

int n,m;// n 行 m 列
int a[N][N];// a[i][j] 表示 (i,j) 的点权值 
int f[N][N];// f[i][j] 表示走到 (i,j) 时能获得的最大点权和是多少
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++) scanf("%d",&a[i][j]);
	}
	f[1][1]=a[1][1];
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			f[i+1][j]=max(f[i+1][j],f[i][j]+a[i+1][j]);
			f[i][j+1]=max(f[i][j+1],f[i][j]+a[i][j+1]);
		}
	}
	printf("%d",f[n][m]);
	return 0;
} 

例题 \(3\) P1216 [USACO1.5] [IOI1994]数字三角形 Number Triangles

给定一个 \(n\) 行的树，第 \(i\) 行有 \(i\) 个数。起点为 \((1,1)\) ，每次移动可以向下或向右下走，最终必然会走到第 \(n\) 行。问从起点开始，走到第 \(n\)​ 行的任意一个点所经过路径的点权和最大是多少。

在不断移动中发生变化的值有位置和点权和。

那么状态就是 \(f[i,j]=点权和\)，代表走到 \((i,j)\)​ 时，能获得最大点权和是多少。

显然，这个问题可以转化成从第 \(n\) 行向 \((1,1)\) 移动，对第 \(n\) 行的每个数初始化即可。

时间复杂度 \(O(n^2)\)​ 。

int n,a[N][N];// a[i][j] 表示 (i,j) 的点权值 
int f[N][N];// f[i][j] 表示走到 (i,j) 时能获得的最大点权和是多少
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++) scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=n;i++) f[n][i]=a[n][i];
	for(int i=n-1;i>=1;i--){
		for(int j=1;j<=i;j++) f[i][j]=max(f[i+1][j],f[i+1][j+1])+a[i][j];
	}
	printf("%d",f[1][1]);
	return 0;
} 

例题 \(4\)

给定一个 \(n\) 行的树，第 \(i\) 行有 \(i\) 个数。起点为 \((1,1)\) ，每次移动可以向下或向右下走，最终必然会走到第 \(n\) 行。问从起点开始，走到第 \(n\) 行的任意一个点所经过路径的点权和\(\mathrm{mod} \ 100\)​ 之后最大是多少。

用 \(f[i,j]\) 表示走到 \((i,j)\) 时点权和 \(\mathrm{mod}\ 100\) 的最大值时多少。

但是，如上描述状态没有最优子结构。

状态加维度优化

如果出现了没有最优子结构的情况，那就是状态设计的不够多。多加一个维度，把和也当作状态。那么用 \(f[i,j][k]\) 表示走到 \((i,j)\) 所经过路径的点权和 \(\mathrm{mod}\ 100=k\) 是否可能。

int n,m;// n 行 m 列
int a[N][N];// a[i][j] 表示 (i,j) 的点权值 
bool f[N][N][N];// f[i][j][k] 表示走到 (i,j) 点权和 %100 = k 是否可能
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		for(int j=1;j<=i;j++) scanf("%d",&a[i][j]);
	}
	for(int i=1;i<=n;i++) f[n][i][a[n][i]%100]=true;
	for(int i=n;i>=2;i--){
		for(int j=1;j<=i;j++){
			for(int k=0;k<100;k++){
				if(f[i][j][k]){
					f[i-1][j-1][(k+a[i-1][j-1])%100]=true;
					f[i-1][j][(k+a[i-1][j])%100]=true;
				}
			}
		}
	}
	int ans=-1;
	for(int i=0;i<100;i++){
		if(f[1][1][i]) ans=i;
	}
	printf("%d",ans);
	return 0;
} 

最长上升子序列 \((\mathrm{LIS})\)

例题 \(1\) B3637 最长上升子序列

变化的值有 选数的个数 和 选到的位置 ，那么状态 \(f[i]\) 表示最后一个选的数是 \(a[i]\)​ 的情况下最多能选几个数。

const int N=5005;
int n,a[N];
int f[N];//以 a[i] 作为最后一个数的时候最多能选几个数
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){//求 f[i] 
		for(int j=1;j<i;j++){//倒数第二个数是 a[j] 
			if(a[j]<a[i]) f[i]=max(f[i],f[j]);
		} 
		f[i]=f[i]+1;
	}
	int ans=-1;
	for(int i=1;i<=n;i++) ans=max(ans,f[i]);
	printf("%d",ans);
	return 0;
} 

例题 \(2\)

给定 \(n\) 个数 \(a_1,a_2,\dots,a_n\)​，求它们的最长上升子序列的长度和任意一种方案。

const int N=5005;
int n,a[N];
int f[N];//以 a[i] 作为最后一个数的时候最多能选几个数
int g[N];// g[i] 表示状态 f[i] 是由状态 f[g[i]] 转移过来的 
void print(int p){//输出当前最后一个数是 a[p] 那组解 
	if(p==0) return;
	print(g[p]);
	printf("%d ",a[p]);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++){//求 f[i] 
		for(int j=1;j<i;j++){//倒数第二个数是 a[j] 
			if(a[j]<a[i]){
				if(f[j]>f[i]){
					f[i]=f[j];
					g[i]=j;
				} 
			}
		} 
		f[i]=f[i]+1;
	}
	int p=1;
	for(int i=2;i<=n;i++){
		if(f[i]>f[p]) p=i;
	} 
	printf("%d\n",f[p]);
	print(p);
	return 0;
} 

例题 \(3\)

给定 \(n\) 个数 \(a_1,a_2,\dots,a_n\)​，求它们的最长上升子序列有多少种最优解。

const int N=5005;
int n,a[N];
int f[N];//以 a[i] 作为最后一个数的时候最多能选几个数
int h[N];// h[i] 表示状态 f[i] 有多少种最优解
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) h[i]=1; 
	for(int i=1;i<=n;i++){//求 f[i] 
		for(int j=1;j<i;j++){//倒数第二个数是 a[j] 
			if(a[j]<a[i]){
				if(f[j]>f[i]){
					f[i]=f[j];
					h[i]=h[j]
				} 
				else if(f[j]==f[i]) h[i]=h[i]+h[j];
			}
		} 
		f[i]=f[i]+1;
	}
	int p=1,ans=0;
	for(int i=2;i<=n;i++){
		if(f[i]>f[p]) p=i;
	} 
	for(int i=1;i<=n;i++){
		if(f[i]==f[p]) ans=ans+h[i];
	}
	printf("%d",ans);
	return 0;
} 

例题 \(4\)​ P1020 [NOIP1999 提高组] 导弹拦截

消除冗余状态优化

例题 \(1\)

给定一些格子 \(a_0,a_1,\dots,a_n\) 。有 \(4\) 种卡片，第 \(i\) 种卡片的数量记作 \(b_i\) 。每使用卡片 \(b_i\) 就可以向右跳 \(i\) 步。求 \(a_0 \dots a_n\) 的和最大是多少。

变化的值有 位置 、卡片的数量 和 走过位置的和 。那么有 \(f[位置][数量]=和\)​ 。

\(f[i][c_1][c_2][c_3][c_4]\) 表示走到 \(i\) 时用了每种卡片分别用了 \(c_1,c_2,c_3,c_4\)​ 张的和最大是多少。

考虑优化成四维，显然有等式 \(i=c_1+2\cdot c_2+3 \cdot c_3+4 \cdot c_4\) 。所以只需要知道四个维度，就可以得出第五个维度的值。删去第一个维度。

强化版 P1541 [NOIP2010 提高组] 乌龟棋

用一个桶来记录每种牌有多少种，之后同例题 \(1\) 。

const int N=355,M=125;
int n,m,a[N],b[N],f[M][M][M][M];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=m;i++){
		int x;
		scanf("%d",&x);
		b[x]++;
	} 
	f[0][0][0][0]=a[1];
	for(int c1=0;c1<=b[1];c1++){
		for(int c2=0;c2<=b[2];c2++){
			for(int c3=0;c3<=b[3];c3++){
				for(int c4=0;c4<=b[4];c4++){
					int i=1+c1+2*c2+3*c3+4*c4,maxn=INT_MIN;
					if(c1!=0) maxn=max(maxn,f[c1-1][c2][c3][c4]+a[i]);
					if(c2!=0) maxn=max(maxn,f[c1][c2-1][c3][c4]+a[i]);
					if(c3!=0) maxn=max(maxn,f[c1][c2][c3-1][c4]+a[i]);
					if(c4!=0) maxn=max(maxn,f[c1][c2][c3][c4-1]+a[i]);
					f[c1][c2][c3][c4]=max(f[c1][c2][c3][c4],maxn);
				}
			}
		}
	} 
	printf("%d",f[b[1]][b[2]][b[3]][b[4]]);
	return 0;
}

排列 DP

\(n\) 个数的排列有 \(n!\) 种方案

例题 \(1\)

给定 \(n\) 个数 \(1,2,\dots ,n\) 。对于每种排列，每个 \(i\) 出现且只能出现一次。求 $1 \dots n $ 的所有排列中，逆序对的个数为偶数的有多少种排列。

排列 DP 转移方法：把所有数从小到大或从大到小插入。

对于例题 \(1\) ，在插入的过程中，变化的值有 插入数的个数 和 逆序对的数量 。

设 \(f[i,j]\) 表示已经插入了 \(1 \dots i\) ，此时逆序对个数为 \(j\) 的方案数。

考虑转移，下一个插入的数是 \(i+1\)，当前的状态是 \(f[i,j]\) 。显然，可以将 \(a_{i+1}\) 插入到任意两个数之间。枚举 \(i+1\) 插入的位置 \(k\) ，逆序对个数增加 \(i-k\) 个，\(f[i+1][j+i-k]+=f[i][j]\) 。

时间复杂度 \(O(n^4)\)

int n,f[N][N];// 1-i 已经插入，此时有 j 个逆序对的方案数
int main(){
	scanf("%d",&n);
	f[1][0]=1;
	for(int i=1;i<n;i++){
		for(int j=0;j<=i*(i-1)/2;j++){// i 个数形成的逆序对个数最多是 i*(i-1)/2 个 
			// 插入 i+1
			for(int k=0;k<=i;k++){// i+1 插入到第 k 个位置 
				f[i+1][j+i-k]=f[i+1][j+i-k]+f[i][j];
			} 
		}
	}
	int ans=0;
	for(int j=0;j<=n*(n-1)/2;j+=2) ans=ans+f[n][j];
	printf("%d",ans);
	return 0;
} 

考虑优化。因为问的是逆序对个数为偶数的排列有几个，所以只需要知道排列的逆序对个数是奇数还是偶数即可，不需要知道有多少种。

这样时间复杂度就被优化成了 \(O(n^2)\)

int n,f[N][N];// 1-i 已经插入
// j=0,偶数个
// j=1,及数个 
int main(){
	scanf("%d",&n);
	f[1][0]=1;
	for(int i=1;i<=n;i++){
		for(int j=0;j<2;j++){// i 个数形成的逆序对个数最多是 i*(i-1)/2 个 
			// 插入 i+1
			for(int k=0;k<=i;k++){// i+1 插入到第 k 个位置 
				f[i+1][(j+i-k)%2]=f[i+1][(j+i-k)%2]+f[i][j];
			} 
		}
	}
	int ans=f[n][0];
	printf("%d",ans);
	return 0;
} 

继续优化，显然只需要知道新增的逆序对个数是奇数还是偶数，不需要知道新增的具体数量。只算出 \(i-k\) 中偶数的个数和奇数的个数即可。

时间复杂度 \(O(n)\) 。

这道题的答案是 \(\frac{n!}{2}\) ，也就是在 \(n!\) 种排列中，逆序对个数为奇数的排列和逆序对个数为偶数的排列数量相等。

例题 \(2\) P1521 求逆序对

这道题与 例题 \(1\) 同理。

const int N=5005,mod=10000;
int n,k,f[N][N];
int main(){
	scanf("%d%d",&n,&k);
	f[1][0]=1;
	for(int i=1;i<n;i++){
		for(int j=0;j<=i*(i-1)/2;j++){
			for(int k_=0;k_<=i;k_++) f[i+1][j+i-k_]=(f[i+1][j+i-k_]+f[i][j])%mod;
		}
	}
	printf("%d",f[n][k]);
	return 0;
} 

例题 \(3\) Practice Coding Problem 弱化版

给定一个 \(n\) 个数的排列 \(1,2,\dots,n\) ，定义该排列的激动值为 ”有多少个数比它前面的数都大“ 。求 $1 \dots n $ 有多少个排列的激动值为 \(k\)​ 。

在插入的过程中不断变化的值有 已经插入的数的数量 和 激动值 。从大到小插入，假设当前已经插入了 \(i\) 个数，下一个插入的是 \(i-1\) ，只有将 \(i-1\) 插入到最前面，激动值\(+1\) 。

int n,k;
int f[N][N];// f[i][j] 代表 i~n 已经插入激动值为 j 的方案数
int main(){
	scanf("%d%d",&n,&k);
	f[n][1]=1;
	for(int i=n;i>=2;i--){
		for(int j=1;j<=n;j++){//接下来插入 i-1 这个数 
			f[i-1][j+1]=f[i-1][j+1]+f[i][j];//插入到最前面
			f[i-1][j]=f[i-1][j]+f[i][j]*(n-i+1);//不插入到最前面 
		}
	}
	printf("%d",f[1][k]);
	return 0;
} 

Day 6

Part 1.上午

背包 DP

01-背包问题

例题 \(1\)

给定 \(n\) 个物品，背包的体积为 \(m\) 。第 \(i\) 个物品价值为 \(w_i\) ，体积为 \(v_i\) 。求在所选物品的体积不超过背包的体积的情况下能获得价值最多是多少。

在装物品的过程中变化的值为 当前物品的编号 、所选物品的体积 和 所选物品的价值。

\(f[i,j]\) 代表已经考虑了前 \(i\) 个物品、用掉了 \(j\) 的体积所能获得的最大价值。

考虑转移，每个物品都有两种情况，要么选要么不选。

如果第 \(i+1\) 个物品不选：\(f[i+1,j]=\max(f[i+1,j],f[i,j])\)

如果第 \(i+1\) 个物品要选：\(f[i+1,j+v_{i+1}]=\max(f[i,j]+w_{i+1},f[i+1,j+v_{i+1}])\)

时间复杂度 \(O(nm)\) 。

int n,m,v[N],w[N];// v[i] 表示第 i 个物品的体积，w[i] 表示第 i 个物品的价值 
int f[N][N];// f[i][j] 代表前 i 个物品已经考虑完，用掉了 j 的体积所能获得的最大价值
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); 
	for(int i=0;i<n;i++){
		for(int j=0;j<=m;j++){//考虑第 i+1 个物品 
			f[i+1][j]=max(f[i+1][j],f[i][j]);//不选
			f[i+1][j+v[i+1]]=max(f[i+1][j+v[i+1]],f[i][j]+w[i+1]);//要选 
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
	printf("%d",ans);// f[n][m]
	return 0;
}

完全背包问题

例题 \(1\)

给定 \(n\) 种物品，背包的体积为 \(m\) ，每种物品有无穷个。第 \(i\) 种物品价值为 \(w_i\) ，体积为 \(v_i\)​ 。求在所选物品的体积不超过背包的体积的情况下能获得价值最多是多少。

在 01-背包问题 的基础上，再加一层循环来枚举第 \(i\)​ 种物品选多少个。

时间复杂度 \(O(nm^2)\) 。

int n,m,v[N],w[N];// v[i] 表示第 i 种物品的体积，w[i] 表示第 i 种物品的价值 
int f[N][N];// f[i][j] 代表前 i 种物品已经考虑完，用掉了 j 的体积所能获得的最大价值
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); 
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){//要求状态 f[i][j] 用别的状态求当前状态 
			for(int k=0;k*v[i]<=j;k++){
				//第 i 种物品选 k 个 
				f[i][j]=max(f[i][j],f[i-1][j-k*v[i]+k*w[i]);
			}
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
	printf("%d",ans);
	return 0;
}

优化成 \(O(nm)\) ，（物品数量 \(\cdot\) 体积最大值）

int n,m,v[N],w[N];// v[i] 表示第 i 个物品的体积，w[i] 表示第 i 个物品的价值 
int f[N][N];// f[i][j] 代表前 i 个物品已经考虑完，用掉了 j 的体积所能获得的最大价值
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]); 
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){//要求状态 f[i][j] 用别的状态求当前状态 
			f[i][j]=f[i-1][j];//上 
			if(j>=v[i]) f[i][j]=max(f[i][j],f[j-v[i]]+w[i]);//左 
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
	printf("%d",ans);
	return 0;
}

例题 \(2\)​ P1616 疯狂的采药

滚动数组优化

#define int long long
using namespace std;
const int N=1e7+5;
int n,m,f[N],v[N],w[N];
signed main(){
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=m;i++) scanf("%lld%lld",&v[i],&w[i]);
	for(int i=1;i<=m;i++){
		for(int j=v[i];j<=n;j++) f[j]=max(f[j],f[j-v[i]]+w[i]);
	}
	printf("%lld",f[n]);
	return 0;
}

多重背包问题

例题 \(1\)

给定 \(n\) 种物品，背包的体积为 \(m\) 。第 \(i\) 种物品价值为 \(w_i\) ，体积为 \(v_i\)​ ，个数为 \(k_i\)​​。求在所选物品的体积不超过背包的体积的情况下能获得价值最多是多少。

时间复杂度 \(O(nm^2)\)

int n,m,v[N],w[N],z[i];// v[i] 表示第 i 种物品的体积，w[i] 表示第 i 种物品的价值，z[i] 表示第 i 种物品的个数 
int f[N][N];// f[i][j] 代表前 i 种物品已经考虑完，用掉了 j 的体积所能获得的最大价值
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&z[i]); 
	for(int i=1;i<=n;i++){
		for(int j=0;j<=m;j++){//要求状态 f[i][j] 用别的状态求当前状态 
			for(int k=0;k*v[i]<=j&&k<=z[i];k++){
				//第 i 种物品选 k 个 
				f[i][j]=max(f[i][j],f[i-1][j-k*v[i]+k*w[i]);
			}
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
	printf("%d",ans);
	return 0;
}

可以把这个题转化成 01-背包 来做。

二进制拆分优化

时间复杂度 \(O(n \log n \times m)\)

int n,m,v[N],w[N],z[N];// v[i] 表示第 i 种物品的体积，w[i] 表示第 i 种物品的价值，z[i] 表示第 i 种物品的个数 
int f[N][N];// f[i][j] 代表前 i 个物品已经考虑完，用掉了 j 的体积所能获得的最大价值
int main(){
	scanf("%d%d",&n,&m);
	int cnt=0;//代表拆分后的新的物品的个数 
	for(int i=1;i<=n;i++){
		int v_,w_,k_;
		scanf("%d%d%d",&v_,&w_,&k_);
		int x=1;
		while(k_>=x){//要拆一个 x 个第 i 种物品的组合出来 
			cnt++;
			v[cnt]=v_*x;
			w[cnt]=w_*x;
			k_=k_-x;
			x<<=1;
		}
		if(k_!=0){
			cnt++;
			v[cnt]=v_*k_;
			w[cnt]=w_*k_;
		} 
	}
	n=cnt;
	for(int i=0;i<n;i++){
		for(int j=0;j<=m;j++){//考虑第 i+1 个物品 
			f[i+1][j]=max(f[i+1][j],f[i][j]);//不选
			f[i+1][j+v[i+1]]=max(f[i+1][j+v[i+1]],f[i][j]+w[i+1]);//要选 
		}
	}
	int ans=0;
	for(int i=0;i<=m;i++) ans=max(ans,f[n][i]);
	printf("%d",ans);// f[n][m]
	return 0;
}

例题 \(2\) P1776 宝物筛选

const int N=1e5+5;
int n,m,v[N],w[N],z[N],f[N];
int main(){
	scanf("%d%d",&n,&m);
	int cnt=0;
	for(int i=1;i<=n;i++){
		int v_,w_,k_;
		scanf("%d%d%d",&v_,&w_,&k_);
		int x=1;
		while(k_>=x){
			cnt++;
			v[cnt]=v_*x;
			w[cnt]=w_*x;
			k_=k_-x;
			x<<=1;
		}
		if(k_!=0){
			cnt++;
			v[cnt]=v_*k_;
			w[cnt]=w_*k_;
		} 
	}
	n=cnt;
	for(int i=1;i<=n;i++){
		for(int j=m;j>=w[i];j--) f[j]=max(f[j],f[j-w[i]]+v[i]); 
	}
	printf("%d",f[m]);
	return 0;
}

区间 DP

第一类

例题 \(1\)​ P1775 石子合并（弱化版）

\(f[l,r]\) 表示把 \(a_l \dots a_r\) 合并成一堆的最小代价，\(f[i,i]=0\) 。

状态转移方程：\(f[l,r]=\min_{l \le k < r}(f[l,k],f[k+1,r]+sum[r]-sum[l-1])\)

const int N=305;
int n,a[N],sum[N];
int f[N][N];// f[l][r] 表示把第 l 堆到第 r 堆石子合并成一堆的最小代价
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) sum[i]=sum[i-1]+a[i];
	memset(f,0x3f,sizeof(f));
	for(int i=1;i<=n;i++) f[i][i]=0;
	for(int len=2;len<=n;len++){//当前要处理长度为 len 的区间 
		for(int l=1,r=len;r<=n;l++,r++){
			for(int k=l;k<r;k++) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+sum[r]-sum[l-1]);
		}
	} 
	printf("%d",f[1][n]);
	return 0;
}

例题 \(2\)​​ P1880 [NOI1995] 石子合并

区间 \(\mathrm{DP}\) 环的处理方法：把数组复制一遍，跑两遍区间 \(\mathrm{DP}\)​

时间复杂度 \(O(n^3)\) 。

const int N=215;
int n,a[N],sum[N];
int f_max[N][N];// f_max[l][r] 表示把第 l 堆到第 r 堆石子合并成一堆的最大代价
int f_min[N][N];// f_min[l][r] 表示把第 l 堆到第 r 堆石子合并成一堆的最小代价
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) a[i+n]=a[i];
	for(int i=1;i<=2*n;i++) sum[i]=sum[i-1]+a[i];
	memset(f_min,0x3f,sizeof(f_min));
	for(int i=1;i<=2*n;i++) f_min[i][i]=f_max[i][i]=0;
	for(int len=2;len<=n;len++){//当前要处理长度为 len 的区间 
		for(int l=1,r=len;r<=2*n;l++,r++){
			for(int k=l;k<r;k++){
				f_min[l][r]=min(f_min[l][r],f_min[l][k]+f_min[k+1][r]+sum[r]-sum[l-1]);
				f_max[l][r]=max(f_max[l][r],f_max[l][k]+f_max[k+1][r]+sum[r]-sum[l-1]);
			}
		}
	} 
	int minn=INT_MAX,maxn=INT_MIN;
	for(int i=1;i<=n;i++){
		minn=min(minn,f_min[i][i+n-1]);//a[i] a[i+1] ~ a[n] a[1] a[2] ~ a[i-1]
		maxn=max(maxn,f_max[i][i+n-1]);//a[i] a[i+1] ~ a[n] a[1] a[2] ~ a[i-1]
	}
	printf("%d\n%d",minn,maxn);
	return 0;
}

例题 \(3\) P1063 [NOIP2006 提高组] 能量项链

const int N=305;
int n,a[N],f[N][N],maxn=INT_MIN;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
	for(int i=1;i<=n;i++) a[i+n]=a[i];
    for(int i=2;i<(n<<1);i++){
        for(int j=i-1;(i-j)<n&&j>=1;j--){
            for(int k=j;k<i;k++) f[j][i]=max(f[j][i],f[j][k]+f[k+1][i]+a[i+1]*a[j]*a[k+1]);
			maxn=max(maxn,f[j][i]);
        }
    }
    printf("%d",maxn);
    return 0;
}

第二类

例题 \(1\) HDU4632 Palindrome subsequence

给定一个字符串，求该字符串中回文子序列的数量。

注：两个回文子序列只要位置不同就算做不同的回文子序列

\(f[l,r]\) 表示字符 \(l \dots r\) 区间内回文子序列的数量。

状态转移方程：\(f[l,r]=f[l,r-1]+f[l+1,r]-f[l+1,r-1]+(s_l==s_r?f[l+1,r-1]+1:0)\)

char s[10005];
int f[N][N];// f[l][r] 表示 s[l] ~ s[r] 有多少个回文子序列 
int main(){
	scanf("%s",s+1);
	int sz=strlen(s+1);
	for(int i=1;i<=sz;i++) f[i][i]=1;
	for(int len=2;len<=n;len++){
		for(int l=1,r=len;r<=n;l++,r++){
			f[l][r]=f[l][r-1]+f[l+1][r]-f[l+1][r-1];//s[l] s[r] 不同时选 
			if(s[l]==s[r]) f[l][r]=f[l][r]+f[l+1][r-1]+1;//s[l] s[r] 同时选 
		}
	}
	printf("%d",f[1][n]);
	return 0;
} 

总结

状态： \(f[l,r]\) 表示从 \(l\) 到 \(r\) 这段区间的所求的某种值

转移：第一类区间 \(\mathrm{DP}\) 的特征是对相邻的值做出操作，转移方法是枚举一个分界点 \(k\) ，用 \(f[l,k]\) 和 \(f[k+1,r]\) 的值来得到 \(f[l,r]\) 的值；第二类区间 \(\mathrm{DP}\) 的特征是找子序列，转移方法分为两种情况：1. \(l\) 和 \(r\) 不同时选，选 \(l\) 是 \(f[l,r-1]\)，选 \(r\) 是 \(f[l+1,r]\) ；2. \(l\) 和 \(r\) 同时选，\(f[l+1,r-1]\) 。

POJ2955

从一个括号序列里

POJ1651