背景

通过学校老师的指引，我在清明节仅仅3天的假期内，上了长达18个小时的课程。

课程

虽然有一点点的累，但还是学到真本事的。

Day1

第一天，介绍是说上数据结构。本来我是认为会先将想栈、队列、链表等简单并可以用 STL的数据结构，但一上来，就讲了树。

另附：给我们讲课的是 mrsrz。

树的遍历：

太简单了，有深搜序，广搜序，拓扑序。

就不一一说明了。

线段树

线段树在上学期，Underage_potato大佬为吾辈讲了一番，但听是听懂了，但似乎我好像不会大代码。

但到了现在，我似乎可以独自打代码了，现鄙人将自己丑陋的代码向大众展示一番。

#include<bits/stdc++.h>
using namespace std;
int n,m,x,y,k,a[100005];
struct nod{
	int l,r;
	int dat;
	long long sum,add;
}t[400000];

void build(int p,int l,int r){
	t[p].l=l;
	t[p].r=r;
	if(l==r){
		t[p].sum=a[l];
		t[p].dat=a[l];
		return;
	}
	int mid=(l+r)/2;
	build(p*2,l,mid);
	build(p*2+1,mid+1,r);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat);
}
//建树 
void cg(int p,int x,int v){
	if(t[p].l==t[p].r){
		t[p].dat=v;
		return ;
	}
	int mid=(t[p].l+t[p].r)/2;
	if(x<=mid)cg(p*2,x,v);
	else cg(p*2+1,x,v);
	t[p].dat=max(t[p*2].dat,t[p*2+1].dat); 
}
//单点修改
void pushdown(int p){
	if(t[p].add){
		t[p*2].sum+=t[p].add*(t[p*2].r-t[p*2].l+1);
		t[p*2+1].sum+=t[p].add*(t[p*2+1].r-t[p*2+1].l+1);
		t[p*2].add+=t[p].add;
		t[p*2+1].add+=t[p].add;
		t[p].add=0;
	}
}
//lazy tag的下传 
void cg2(int p,int l,int r,int d){
	if(l<=t[p].l&&r>=t[p].r){
		t[p].sum+=(long long)d*(t[p].r-t[p].l+1);
		t[p].add+=d;
		return ;
	}
	pushdown(p);
	int mid=(t[p].l+t[p].r)/2;
	long long val=0;
	if(l<=mid)cg2(p*2,l,r,d);
	if(r>mid)cg2(p*2+1,l,r,d);
	t[p].sum=t[p*2].sum+t[p*2+1].sum;
}
//区间修改 
int ask(int p,int l,int r){
	if(l<=t[p].l&&r>=t[p].r)return  t[p].sum;
	pushdown(p);
	int mid=(t[p].l+t[p].r)/2;
	int val=0;
	if(l<=mid)val+=ask(p*2,l,r);
	if(r>mid)val+=ask(p*2+1,l,r);
	return val;
} 
//区间查询
int main() {
	cin>>n>>m;
	for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	while(m--){
		int f;
		cin>>f>>x>>y;
		if(f==1){
			cin>>k;
			cg2(1,x,y,k);
		}else{
			cout<<ask(1,x,y)<<"\n";
		}
	}
	return 0;
}

线段树与2分相结合：

#include<bits/stdc++.h>
using namespace std;
int c[10000],n;
void add(int i,int x){for(;i<=n;i+=i&-i)c[i]+=x;}
int ask(int i){int x=0;for(;i>0;i-=i&-i)x+=c[i];return x;}
int kth(int k){
	int =1,r=n;l=mid+1;
	   
	while(l<r){
		int mid=(l+r)>>1;
		if(a[mid]<k)k-=a[mid],
		else r=mid;
	} 
}
int main(){	
	return 0;
}

树状数组

树状数组是一个与线段树极为相似的东西。

现将老师奉献的两行（一行单点增加，一行区间查询）代码置于此处。

void add(int i,int x){for(;i<=n;i+=i&-i)c[i]+=x;}
int ask(int i){int x=0;for(;i>0;i-=i&-i)x+=c[i];return x;}

st表

在课上，老师还讲了一个求区间最值的东西，叫做 ST表。

查询只需 \(O(1)\) 的复杂度，但有较为复杂的预处理。

void ST_pwork(){
	for(int i=1;i<=n;i++)f[i][0]=a[i];
	int t=log(n)/log(2)+1;
	for(int j=1;j<t;j++)
	    for(int i=1;i<=n-(1<<j);i++)
	        f[i][j]=max(f[i][j-1],f[i+(1<<(j-1))][j-1])
}
void ST_ask(int l,int r){
	int k=log(r-l+1)/log(2);
	return max(f[l][k],f[r-(1<<k)+1][k]);
}

树链刨分

就不讲了。

Day2

Day2 讲了DP，我将背包DP全部听懂。

背包DP

01背包

我们可以将动态方程表现为 \(f[i][j][k]=1/0\)表示选到第 \(i\) 个背包容量为 \(j\) 总价格为 \(k\) 的状态是否存在。

但由于复杂度太大，所以我们可以将其改造成 \(f[i][j]=k\) 表示为选到第 \(i\) 个,背包容量为 \(j\) 最大总价格为 \(k\) 或\(f[i][j]=k\) 表示为选到第 \(i\) 个，最大总价格为\(j\)，背包容量为 \(k\) 。

但打完代码后我们会发现 \(i\) 的状态是只有 \(i\) 和 \(i-1\) 的所以也可以省。

动态转移方程就变成了 \(f[j]=max(f[j],f[j-v[i]]+w[i])\) 。

int f[1000000];
	memset(f,0xcf,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++)
	    for(int j=m;j>=v[i];j--)
	        f[j]=max(f[j],f[j-v[i]]+w[i]);
	int ans=0;;
	for(int j=0;j<=m;j++)
		ans=max(ans,f[j]);

完全背包

物品不在是 只有一个，变成了有无数个。

int f[1000000];
	memset(f,0xcf,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++)
	    for(int j=v[i];j<=m;j++)
	        f[j]=max(f[j],f[j-v[i]]+w[i]);
	int ans=0;;
	for(int j=0;j<=m;j++)
		ans=max(ans,f[j]);

易发现就是将 01背包的 \(j\) 的循环顺序调换了。

多重背包

int f[1000000];
	memset(f,0xcf,sizeof(f));
	f[0]=0;
	for(int i=1;i<=n;i++)
	    for(int j=1;j<=c[i];j++)
	        for(int k=m;k>=v[i];k--)    
				f[k]=max(f[k],f[j-v[i]]+w[i]);
	int ans=0;
	for(int j=0;j<=m;j++)
		ans=max(ans,f[j]);

易发现就是 01背包加了数量限制。