月度归档： 2022年1月

2022/1/17

T1：表达式

T2：SPFA/BFS

T3：树形dp

T4：线段树

总结：今天打挂了，T4算错时间复杂度，T2算错空间复杂度，以为能A，T1T3对考点不熟……

题外话：关于李嘉文同学，我希望他能早日改正他不正确的行为，同时，我也希望所有地精改邪归正，所有不是地精的同学洁身自好，总之，大家都别地

2022/1/15总结

T1：1365. 无限序列，水题，还是提一嘴吧

我们设S(0)=0,S(1)=1,S(2)=10容易发现S(2)=S(1)#S(0)（此处#为拼接符号）显然S(3)=S(2)#S(1)……S(n)=S(n-1)#S(n-2)，所以我们发现，S(n)的长度=Fn+1 ; S(n)中一的个数为Fn-1递归求解即可

T2：1366. 删数：DP， 有手就行

T3：1367. 俄罗斯方块：依题意模拟即可

T4：1368. 燃烧木棍 我们把$$\sqrt2$$的木棍从中间分成两段，然后连边跑最短路

统计答案：我们设木棍左边$$t1$$时刻烧着，右边$$t1$$时刻烧着$$t1<t2$$每端燃烧的速度时$$v$$

则燃烧时间$$burn~time=t1+(t2-t1)+\frac{vt-(t2-t1)v}{2v}=\frac{t+t1+t2}{2}$$

网络流一日通（待更）

#1：最大流(EK算法)

这个算法很简单，就是 BFS 找增广路，然后对其进行 增广

找？我们就从源点一直 BFS 走来走去，碰到汇点就停，然后增广（每一条路都要增广）。我们在 BFS 的时候就注意一下流量合不合法就可以了。

增广？其实就是按照我们找的增广路在重新走一遍。走的时候把这条路的能够成的最大流量减一减，然后给答案加上最小流量就可以了。注意在增广的同时建反向边，一遍给程序一个反悔的机会（消化自OI-WIKI）

CODE：以USACO 4.2.1 Drainage Ditches草地排水为例

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#define min(x,y) x<y?x:y
using namespace std;
const int inf=0x7fffffff;
int res[205][205];
bool vis[205];
int pre[205];
int n,m;
bool bfs(int s,int t)
{
	int p;
	queue <int> q;
	memset(pre,-1,sizeof(pre));
	memset(vis,false,sizeof(vis)); 
	pre[s]=s;
	vis[s]=true;
	q.push(s);
	while(!q.empty())
	{
		p=q.front();
		q.pop();
		for(int i=1;i<=n;i++)
		{
			if(res[p][i]>0&&!vis[i])
			{
				pre[i]=p;
				vis[i]=true;
				if(i==t)return true;
				q.push(i); 
			}
		}
	}
	return false;
}
int EK(int s,int t)
{
	int f=0,d,i;
	while(bfs(s,t))
	{
		d=inf;
		for(i=t;i!=s;i=pre[i])
			d=d<res[pre[i]][i]? d:res[pre[i]][i];
		for(i=t;i!=s;i=pre[i])
		{
			res[pre[i]][i]-=d;
			res[i][pre[i]]+=d;
		}
	   f+=d;
	}
	return f;
}
int main()
{
	scanf("%d%d",&m,&n);
	int u,v,w;
    memset(res,0,sizeof(res));
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		res[u][v]+=w;
	}
	printf("%d\n",EK(1,n));
	return 0;
}

#2：最大流(DINIC算法)

#2-1Dinic：现将图分层，然后dfs增广

CODE：以USACO 4.2.1 Drainage Ditches草地排水为例

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x7fffffff;
int cnt=2;
int head[505];
int next[505];
int to[505];
int f[505];
int d[505];
void link(int u,int v,int w)
{
	to[cnt]=v;
	f[cnt]=w;
	next[cnt]=head[u];
	head[u]=cnt++;
}
queue <int> q;
bool bfs(int s,int t)
{
	while(!q.empty())q.pop();
	memset(d,0,sizeof(d));
	d[s]=1;q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=next[i])
		{
			if(f[i]>0&&!d[to[i]])
			{
				d[to[i]]=d[u]+1;
				q.push(to[i]);
			}
		}
	}
	while(!q.empty())q.pop();
	if(!d[t])return false;
	return true;
}
int dfs(int k,int t,int flow)
{
	if(k==t)return flow;
	for(int i=head[k];i;i=next[i])
	{
		if((d[to[i]]==d[k]+1)&&(f[i]!=0))
		{
			int dt=dfs(to[i],t,min(flow,f[i]));
			if(dt>0)
			{
				f[i]-=dt;
				f[i^1]+=dt;
				return dt;
			}
		}
	}
	return 0;
}
int dinic(int s,int t)
{
	int ans=0;
	while(bfs(s,t))
	{
		while(int d=dfs(s,t,inf))
			ans+=d;
	}
	return ans;
}
int main()
{
	int m,n;
	scanf("%d%d",&m,&n);
	int u,v,w;
	for(int i=0;i<m;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		link(u,v,w);link(v,u,0);
	}
	printf("%d\n",dinic(1,n));
	return 0;
}

#2-2多路增广：在dfs时，记一个used为当前剩余容量，没留完就继续流。

CODE：以USACO 4.2.1 Drainag Ditches 草地排水（数据加强）为例

DFS：部分

int dfs(int k,int t,int flow)
{
	if(k==t)return flow;
	int used=flow;
	for(int i=head[k];i&&used;i=next[i])
	{
		int y=to[i];
		if(d[y]==d[k]+1&&f[i])
		{
			int dt=dfs(y,t,min(used,f[i]));
			if(!dt) d[y]=0;
			used-=dt,f[i]-=dt,f[i^1]+=dt;
		}
	}
	return flow-used;
}

#2-3当前弧优化：先复制一遍head到cur中，然后每次从cur枚举，把枚举过的边删掉

CODE：以USACO 4.2.1 Drainage Ditches(数据加强)草地排水为例（同时加两个优化）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x7fffffff;
int cnt=2;
int m,n;
int head[2000005];
int cur[2000005];
int next[2000005];
int to[2000005];
int f[2000005];
int d[2000005];
void link(int u,int v,int w)
{
	to[cnt]=v;
	f[cnt]=w;
	next[cnt]=head[u];
	head[u]=cnt++;
}
bool bfs(int s,int t)
{
	queue <int> q;
	for(int i=1;i<=n;i++)
	{
		cur[i]=head[i];
		d[i]=0;
	}
	d[s]=1;q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		for(int i=head[u];i;i=next[i])
		{
			if(f[i]>0&&!d[to[i]])
			{
				d[to[i]]=d[u]+1;
				q.push(to[i]);
			}
		}
	}
	if(!d[t])return false;
	return true;
}
int dfs(int k,int t,int flow)
{
	if(k==t)return flow;
	int used=flow;
	for(int i=cur[k];i&&used;i=next[i])
	{
		cur[k]=i;
		int y=to[i];
		if(d[y]==d[k]+1&&f[i])
		{
			int dt=dfs(y,t,min(used,f[i]));
			if(!dt) d[y]=0;
			used-=dt,f[i]-=dt,f[i^1]+=dt;
		}
	}
	return flow-used;
}
int dinic(int s,int t)
{
	int ans=0;
	while(bfs(s,t))
	{
		while(int d=dfs(s,t,inf))
			ans+=d;
	}
	return ans;
}
int main()
{
	scanf("%d%d",&n,&m);
	int u,v,w;
	for(int i=1;i<=n;i++)
	{
		scanf("%d%d%d",&u,&v,&w);
		link(u,v,w);link(v,u,0);
	}
	printf("%d\n",dinic(1,m));
	return 0;
}

#3：最小割

#3-1：最大流最小割定理：最大流的值等于最小割的容量

#3-2：证明本蒟还不会，以下内容转自OI WIKI：

定理：f(s,t)max=f(s,t)min

对于任意一个可行流f(s,t)的割 (S,T)，我们可以得到：f(s,t)=出边的总流量－入边的总流量≤出边的总流量=c(s,t)

如果我们求出了最大流 f，那么残余网络中一定不存在s到t的增广路经，也就是s的出边一定是满流，s的入边一定是零流，于是有：f(s,t)=出边的总流量－入边的总流量≤出边的总流量=c(s,t)

结合前面的不等式，我们可以知道此时f已经达到最大。

#3-3：方案（转自OI WIKI）：

我们可以通过从源点s开始 DFS，每次走残量大于0的边，找到所有S点集内的点。

CODE：（转自OI WIKI）

void dfs(int u) {
  vis[u] = 1;
  for (int i = lnk[u]; i; i = nxt[i]) {
    int v = ter[i];
    if (!vis[v] && val[i]) dfs(v);
  }
}

#4：费用流(SSP算法)

SSP算法=把EK/DINIC的BFS换成SPFA
模板代码：(EK)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
using namespace std;
const int inf=0x7fffffff;
int cnt=2;
int head[2000005];
int nt[2000005];
int to[2000005];
int f[2000005];
int c[2000005];
int d[2000005];
int dis[2000005];
int vis[2000005];
int pre[2000005];
void link(int u,int v,int w,int z)
{
	to[cnt]=v;
	f[cnt]=w;
	c[cnt]=z; 
	nt[cnt]=head[u];
	head[u]=cnt++;
}
bool spfa(int s,int t)
{
	queue <int> q;
	memset(dis,0x3f,sizeof(dis));
	memset(pre,-1,sizeof(pre));
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int now=q.front();
		vis[now]=0;
		q.pop();
		for(int i=head[now];i;i=nt[i])
		{
			int go=to[i],fw=f[i];
			if(fw>0&&dis[go]>dis[now]+c[i])
			{
				dis[go]=dis[now]+c[i];
				pre[go]=i^1;
				if(!vis[go])
				{
					vis[go]=1;
					q.push(go);
				}
			}
		}
	}
	return pre[t]!=-1;
}
void EK(int s,int t,int &maxflow,int &mincost)
{
	maxflow=mincost=0;
	while(spfa(s,t))
	{
		int ll=inf;
		for(int i=pre[t];i!=-1;i=pre[to[i]])
		{
			ll=min(ll,f[i^1]);
		}
		for(int i=pre[t];i!=-1;i=pre[to[i]])
		{
			f[i]+=ll;
			f[i^1]-=ll;
		}
		maxflow+=ll;
		mincost+=ll*dis[t];
	}
}
int main()
{
	int m,n,s,t,ans1,ans2;
	scanf("%d%d%d%d",&n,&m,&s,&t);
	int u,v,w,z;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d%d",&u,&v,&w,&z);
		link(u,v,w,z);link(v,u,0,-z);
	}
	EK(s,t,ans1,ans2);
	printf("%d %d",ans1,ans2); 
	return 0;
}

2022/1/14总结

T1:3499. 【NOIP2013模拟联考15】人类基因组(genes)

将基因断环成列，维护rmq（单调队列，st表，笛卡尔树，线段树……）

T2:1339. 矿泉水 (Standard IO)

这题写起来有点复杂，先把（n+1 ~ 4）的水转化成废水即喜好值为9，价格为0，我们设f[i,j,k,l,u]表示第i天，j天内要喝第1种水，k天内要喝第2种水，l天内要喝第3种水，u天内要喝第4种水

上伪代码：

 for(i=0~m-1,j=1~a[1],k=1~a[2],l=1~a[3],u=1~a[4])
{
    不喝水 : f[i][j][k][l][u]->f[i+1][j-1][k-1][l-1][u-1]
    喝水 : f[i][j][k][l][u]->f[i][...a[?]...]
    记录答案 : if can : day=i，money=max{f[i][j][k][l][u]}
}

T3：1341. 失眠 (Standard IO)
设S1=（i，j，k）的个数（a[i]<a[j] and a[k]<a[j])
设S2=（i，j，k）的个数（a[i]<a[j] and a[j]<a[k])
设S3=（i，j，k）的个数（a[i]<a[j] and a[j]<a[k])

S2,S3很好求，所以求出S2，S3，得到S1=S3-S2

QBFNB！用cdq分治A了此题

T4：3739. 匹配(match)

跑出一个最二分图最大权匹配，逐一验证每条边即可