六省联考2017 Day2

目录

2018.3.27 Test

时间：7:30~11:50
期望得分：(50+)+0+20=70
实际得分：52+5+20=77

总结

T1 看错一点题，暴力也废了很长时间。
T2 期望DP没写过不敢写，然而50分和期望没有关系，贪心什么的就行。没细看。
T3 建图死活建不出来，没想明白费用流还费了不少时间写费用流。

BZOJ总链接.
洛谷.
LOJ.

T1

题目链接

好像很麻烦，先弃疗。

T2

题目链接

代码倒很短，学学期望再写。

T3 BZOJ.4873.[六省联考2017]寿司餐厅(最小割ISAP 最大权闭合子图)

题目链接

不会建图。。在最大权闭合子图和费用流徘徊，快考完发现费用流不对。。硬是把区间单独考虑了，没考虑与小区间的限制关系。

正解: 最大权闭合子图.
如果想要取一个区间，那么会把这一区间中所有的都取一遍，且一共只取一遍。
即: 选(i,j)(i<j)必选(i+1,j)和(i,j-1)；选(i,i)必选id[i]。
由源点向每个权值为正的区间连权值的边；由每个权值为负的区间向汇点连权值绝对值的边(阻碍割掉连向汇点的一边)；
用每种寿司i直接代表区间(i,i)，根据D[i,i]-id[i]的正负向汇点/源点连边；寿司向id[i]连INF的边，id[i]向汇点连m*id^2的边。
Ans = 正权和 - 最大流

//2240kb	148ms(怎么好像很慢。。)
#include <cstdio>
#include <cctype>
#include <algorithm>
#define gc() getchar()
const int N=1e4+5,M=7e4+5,INF=0x3f3f3f3f;

int n,m,src,des,Enum,cur[N],H[N],nxt[M],fr[M],to[M],cap[M],lev[N],num[N],que[N],pre[N];
int id[105][105],A[105],d[105][105],exist[1005];

inline int read()
{
	int now=0,f=1;register char c=gc();
	for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now*f;
}
inline void AddEdge(int u,int v,int w)
{
	to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w;
	to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=0;
}
bool BFS()
{
	for(int i=src; i<des; ++i) lev[i]=des+1;
	que[0]=des, lev[des]=0; int h=0,t=1;
	while(h<t)
	{
		int x=que[h++];
		for(int i=H[x]; i; i=nxt[i])
			if(lev[to[i]]==des+1 && cap[i^1])
				lev[to[i]]=lev[x]+1, que[t++]=to[i];
	}
	return lev[src]<=des;
}
int Augment()
{
	int mn=INF;
	for(int i=des; i!=src; i=fr[pre[i]])
		mn=std::min(mn,cap[pre[i]]);     
	for(int i=des; i!=src; i=fr[pre[i]])
		cap[pre[i]]-=mn,cap[pre[i]^1]+=mn;
	return mn;
}
long long ISAP()
{
	if(!BFS()) return 0;
	for(int i=src; i<=des; ++i) cur[i]=H[i],++num[lev[i]];
	int x=src; long long res=0;
	while(lev[src]<=des)
	{
		if(x==des) x=src,res+=Augment();
		bool can=0;
		for(int i=cur[x]; i; i=nxt[i])
			if(lev[to[i]]==lev[x]-1 && cap[i])
			{
				can=1, cur[x]=i, pre[x=to[i]]=i;
				break;
			}
		if(!can)
		{
			int mn=des;
			for(int i=H[x]; i; i=nxt[i])
				if(cap[i]) mn=std::min(mn,lev[to[i]]);
			if(!--num[lev[x]]) break;
			++num[lev[x]=mn+1];
			cur[x]=H[x];
			if(x!=src) x=fr[pre[x]];
		}
	}
	return res;
}

int main()
{
	n=read(),m=read(),Enum=1;
	int cnt=n;
	for(int i=1; i<=n; ++i) id[i][i]=i;
	for(int i=1; i<n; ++i)
		for(int j=i+1; j<=n; ++j) id[i][j]=++cnt;
	src=0, des=cnt+n+1;
	for(int i=1; i<=n; ++i)
	{
		A[i]=read();
		if(m && !exist[A[i]]) exist[A[i]]=++cnt,AddEdge(cnt,des,/*m**/A[i]*A[i]);
		if(m) AddEdge(i,exist[A[i]],INF);
	}
	for(int i=1; i<=n; ++i)
		for(int j=i; j<=n; ++j) d[i][j]=read();
	long long res=0;
	for(int t,i=1; i<=n; ++i)
		(t=d[i][i]-A[i])>0 ? res+=t,AddEdge(src,i,t) : AddEdge(i,des,-t);
	for(int i=1; i<n; ++i)
		for(int j=i+1; j<=n; ++j)
		{
			AddEdge(id[i][j],id[i+1][j],INF), AddEdge(id[i][j],id[i][j-1],INF);
			d[i][j]>0 ? res+=d[i][j],AddEdge(src,id[i][j],d[i][j]) : AddEdge(id[i][j],des,-d[i][j]);
		}
	printf("%lld",res-ISAP());

	return 0;
}

考试代码

T1

5k暴力心累（一半复制的）
刚开始想错题意了，判的点不能走。当然挺好改。

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
//#define gc() getchar()
#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)
const int MAXIN=1e6;

int T,X;
char IN[MAXIN],*SS=IN,*TT=IN;

inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}
namespace Subtask1
{
	const int N=9;

	int n,cnt,pos1[1<<9],pos2[1<<9],H[N],Enum,fr[N<<1],to[N<<1],nxt[N<<1],pre[N];
	bool can,vis[N<<1],vis2[N<<1],visp[N],visp2[N];
	
	inline void AddEdge(int u,int v)
	{
		to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum;
		to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum;
	}
	void Pre()
	{
		for(int t,p,i=1; i<(1<<8); ++i)
		{
			t=0, p=cnt+1;
			for(int j=i,l=1; j; j>>=1,++l)
				if(j&1){
					if(++t>2) break;
					if(pos1[p]) pos2[p]=l;
					else pos1[p]=l;
				}
			if(t==2) ++cnt;
			else if(t==1) ++cnt,pos2[p]=pos1[p];
			else pos1[p]=pos2[p]=0;
		}
//		for(int i=1; i<=cnt; ++i) printf("Pre:%d -> %d
",pos1[i],pos2[i]);
	}
	void DFS(int x,int f,int t)
	{
		if(x==t) {can=1; return;}
		for(int i=H[x]; i&&!can; i=nxt[i])
			if(to[i]!=f&&!vis[i]) pre[to[i]]=i,DFS(to[i],x,t);
	}
	void Calc_DFS(int x)
	{
		visp2[x]=1;
		for(int i=H[x]; i; i=nxt[i])
			if(!vis[i]&&!vis2[i]&&!visp[to[i]]&&!visp2[to[i]]) Calc_DFS(to[i]);
	}
	void Solve()
	{
		Pre();
		while(T--)
		{
			n=read(), Enum=0;
			for(int i=1; i<=n; ++i) H[i]=0;
			for(int u,v,i=1; i<n; ++i) u=read(),v=read(),AddEdge(u,v);
			int res=0;
			for(int i=1; i<=cnt; ++i)
			{
				if(pos1[i]>n||pos2[i]>n) continue;
				for(int j=1; j<=Enum; ++j) vis[j]=0;
				for(int j=1; j<=n; ++j) visp[j]=0;
				can=0, DFS(pos1[i],0,pos2[i]);
				int t=pos2[i];
				while(t!=pos1[i]) visp[t]=vis[pre[t]]=1,t=fr[pre[t]];
				visp[pos1[i]]=1;
				for(int ans,j=1; j<=cnt; ++j)
				{
					if(pos1[j]>n||pos2[j]>n) continue;
					can=0, DFS(pos1[j],0,pos2[j]);
					if(!can) continue;
					for(int k=1; k<=Enum; ++k) vis2[k]=0;
					for(int k=1; k<=n; ++k) visp2[k]=0;
					t=pos2[j];
					while(t!=pos1[j]) visp2[t]=vis2[pre[t]]=1,t=fr[pre[t]];
					visp2[pos1[j]]=1;

					ans=0;
					for(int k=1; k<=n; ++k)
						if(!visp[k]&&!visp2[k]) Calc_DFS(k),++ans;
					if(ans>res) res=ans;
				}
			}
			printf("%d
",res);
		}
	}
}
namespace Subtask2
{
	const int N=1003;

	int n,p0,p1,h0,h1,H[N],Enum,fr[N<<1],to[N<<1],nxt[N<<1],pre[N];
	bool can,vis[N<<1],vis2[N<<1],visp[N],visp2[N];

	inline void AddEdge(int u,int v)
	{
		to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum;
		to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum;
	}
	void DFS(int x,int f,int t)
	{
		if(x==t) {can=1; return;}
		for(int i=H[x]; i&&!can; i=nxt[i])
			if(to[i]!=f&&!vis[i]) pre[to[i]]=i,DFS(to[i],x,t);
	}
	void Calc_DFS(int x)
	{
		visp2[x]=1;
		for(int i=H[x]; i; i=nxt[i])
			if(!vis[i]&&!vis2[i]&&!visp[to[i]]&&!visp2[to[i]]) Calc_DFS(to[i]);
	}
	void Solve()
	{
		while(T--)
		{
			n=read(),p0=read(),p1=read(),h0=read(),h1=read(), Enum=0;
			for(int i=1; i<=n; ++i) H[i]=0;
			for(int u,v,i=1; i<n; ++i) u=read(),v=read(),AddEdge(u,v);

			for(int i=1; i<=Enum; ++i) vis[i]=0;
			for(int i=1; i<=n; ++i) visp[i]=0;
			can=0, DFS(p0,0,p1);
			int t=p1;
			while(t!=p0) visp[t]=vis[pre[t]]=1,t=fr[pre[t]];
			visp[p0]=1;

			can=0, DFS(h0,0,h1);
			if(!can) {puts("0"); continue;}
			for(int k=1; k<=Enum; ++k) vis2[k]=0;
			for(int k=1; k<=n; ++k) visp2[k]=0;
			t=h1;
			while(t!=h0) visp2[t]=vis2[pre[t]]=1,t=fr[pre[t]];
			visp2[h0]=1;

			int res=0;
			for(int k=1; k<=n; ++k)
				if(!visp[k]&&!visp2[k]) Calc_DFS(k),++res;
			printf("%d
",res);
		}
	}
}
namespace Subtask3
{
	const int N=1003;

	int n,p0,p1,H[N],Enum,fr[N<<1],to[N<<1],nxt[N<<1],pre[N];
	bool can,vis[N<<1],vis2[N<<1],visp[N],visp2[N];

	inline void AddEdge(int u,int v)
	{
		to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum;
		to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum;
	}
	void DFS(int x,int f,int t)
	{
		if(x==t) {can=1; return;}
		for(int i=H[x]; i&&!can; i=nxt[i])
			if(to[i]!=f&&!vis[i]) pre[to[i]]=i,DFS(to[i],x,t);
	}
	void Calc_DFS(int x)
	{
		visp2[x]=1;
		for(int i=H[x]; i; i=nxt[i])
			if(!vis[i]&&!vis2[i]&&!visp[to[i]]&&!visp2[to[i]]) Calc_DFS(to[i]);
	}
	void Solve()
	{
		while(T--)
		{
			n=read(),p0=read(),p1=read(), Enum=0;
			for(int i=1; i<=n; ++i) H[i]=0;
			for(int u,v,i=1; i<n; ++i) u=read(),v=read(),AddEdge(u,v);

			for(int i=1; i<=Enum; ++i) vis[i]=0;
			for(int i=1; i<=n; ++i) visp[i]=0;
			can=0, DFS(p0,0,p1);
			int t=p1;
			while(t!=p0) visp[t]=vis[pre[t]]=1,t=fr[pre[t]];
			visp[p0]=1;

			int res=0;
			for(int i=1; i<=n; ++i)
				for(int j=1; j<=n; ++j)
				{
					can=0, DFS(i,0,j);
					if(!can) continue;
					for(int k=1; k<=Enum; ++k) vis2[k]=0;
					for(int k=1; k<=n; ++k) visp2[k]=0;
					t=j;
					while(t!=i) visp2[t]=vis2[pre[t]]=1,t=fr[pre[t]];
					visp2[i]=1;

					int ans=0;
					for(int k=1; k<=n; ++k)
						if(!visp[k]&&!visp2[k]) Calc_DFS(k),++ans;
					if(ans>res) res=ans;
				}
			printf("%d
",res);
		}
	}
}

int main()
{
	freopen("treediagram.in","r",stdin);
	freopen("treediagram.out","w",stdout);

	T=read(),X=read();
	if(!X) Subtask1::Solve();
	else if(X==2) Subtask2::Solve();
	else Subtask3::Solve();

	fclose(stdin);fclose(stdout);
	return 0;
}

T2

直接输出0真的可以，还有5分233→_→

#include <cstdio>
#include <cctype>
#define gc() getchar()
#define mod (100003)
const int N=1e3+5;



inline int read()
{
	int now=0;register char c=gc();
	for(;!isdigit(c);c=gc());
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now;
}

int main()
{
	freopen("trennen.in","r",stdin);
	freopen("trennen.out","w",stdout);

	putchar('0');

	fclose(stdin);fclose(stdout);
	return 0;
}

T3

爆搜：

#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=2e4+5,M=3e6+5,INF=0x3f3f3f3f;

int n,m,Ans,Max;
int cnt,tm[35],id[105][105],A[105],l[55555],r[55555],cost[45555],sum[105],d[105][105];
bool vis[7][7];

inline int read()
{
	int now=0,f=1;register char c=gc();
	for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now*f;
}
void DFS(int x,int s)
{
	if(x>cnt)
	{
		memset(tm,0,sizeof tm);
		memset(vis,0,sizeof vis);
		int tmp=0;
		for(int i=1; i<=cnt; ++i)
			if((s>>i-1)&1)
				for(int j=l[i]; j<=r[i]; ++j)
				{
					for(int k=j; k<=r[i]; ++k)
						if(!vis[j][k])
							tmp+=d[j][k], vis[j][k]=1;
					++tm[A[j]];
				}
		for(int i=1; i<=Max; ++i) if(tm[i]) tmp-=m*i+tm[i]*i;
		Ans=std::max(Ans,tmp);
	}
	else DFS(x+1,s), DFS(x+1,s|(1<<x-1));
}

int main()
{
	freopen("sushi.in","r",stdin);
	freopen("sushi.out","w",stdout);

	n=read(),m=read();
	for(int i=1; i<=n; ++i) Max=std::max(Max,A[i]=read()),sum[i]=sum[i-1]+A[i];
	for(int i=1; i<=n; ++i)
		for(int j=i; j<=n; ++j) d[i][j]=read();
	for(int i=1; i<=n; ++i)
		for(int j=i; j<=n; ++j) id[i][j]=++cnt,cost[cnt]=sum[j]-sum[i-1],l[cnt]=i,r[cnt]=j;
	DFS(1,0);
	printf("%d",Ans);
	

	fclose(stdin);fclose(stdout);
	return 0;
}

sb费用流。。（还是由最大流又改成费用流的）

#include <queue>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <algorithm>
#define gc() getchar()
const int N=2e4+5,M=3e6+5,INF=0x3f3f3f3f;

int n,m,src,des,Enum,H[N],nxt[M],fr[M],to[M],cap[M],cost[M],dis[N],pre[N];
int cnt,id[105][105],A[105],sum[105],d[105][105];
bool inq[N];
std::queue<int> q;

inline int read()
{
	int now=0,f=1;register char c=gc();
	for(;!isdigit(c);c=gc()) if(c=='-') f=-1;
	for(;isdigit(c);now=now*10+c-'0',c=gc());
	return now*f;
}
inline void AddEdge(int u,int v,int w,int c)
{
	printf("%d->%d cap:%d c:%d
",u,v,w,c);
	to[++Enum]=v, fr[Enum]=u, nxt[Enum]=H[u], H[u]=Enum, cap[Enum]=w, cost[Enum]=c;
	to[++Enum]=u, fr[Enum]=v, nxt[Enum]=H[v], H[v]=Enum, cap[Enum]=0, cost[Enum]=-c;
}
bool SPFA()
{
	memset(dis,0x3f,sizeof dis);
	dis[src]=0, q.push(src);
	while(!q.empty())
	{
		int x=q.front(); q.pop(),inq[x]=0;
		for(int i=H[x]; i; i=nxt[i])
			if(dis[to[i]]>dis[x]+cost[i] && cap[i])
			{
				dis[to[i]]=dis[x]+cost[i], pre[to[i]]=i;
				if(!inq[to[i]]) q.push(to[i]),inq[to[i]]=1;			
			}
	}
	return dis[des]!=INF;
}
int MCMF()
{
	int mn=INF,res=0;
	for(int i=des; i!=src; i=fr[pre[i]])
		mn=std::min(mn,cap[pre[i]]);
	for(int i=des; i!=src; i=fr[pre[i]])
		cap[pre[i]]-=mn,cap[pre[i]^1]+=mn,res+=cost[pre[i]]*mn;
	for(int i=des; i!=src; i=fr[pre[i]])
		printf("%d<-",i);
	printf("%d flow:%d res:%d
",src,mn,res);
	return res;
}

int main()
{
	freopen("sushi.in","r",stdin);
//	freopen("sushi.out","w",stdout);

	n=read(),m=read(),Enum=1;
	for(int i=1; i<=n; ++i) A[i]=read(),sum[i]=sum[i-1]+A[i];
	for(int i=1; i<=n; ++i)
		for(int j=i; j<=n; ++j)
			d[i][j]=read();
	for(int i=1; i<=n; ++i)
		for(int j=i; j<=n; ++j) id[i][j]=++cnt;
	src=0, des=cnt<<1|1;
	for(int i=1; i<=n; ++i)
		for(int j=i; j<=n; ++j)
		{
			int t=0;
			for(int k=i; k<=j; ++k)
				for(int l=k; l<=j; ++l)
					++t, AddEdge(id[i][j],id[k][l]+cnt,INF,0);
			AddEdge(src,id[i][j],t,sum[j]-sum[i-1]);
		}
	for(int i=1; i<=n; ++i)
		for(int j=i; j<=n; ++j) AddEdge(id[i][j]+cnt,des,1,-d[i][j]);
	long long res=0,ans=1e9;
	while(SPFA()) ans=std::min(ans,res+=MCMF()),printf("%I64d
",res);
	printf("%I64d",-ans);

	fclose(stdin);fclose(stdout);
	return 0;
}
【推广】 免费学中医，健康全家人
原文地址：https://www.cnblogs.com/SovietPower/p/8659922.html