NOIP2017提高组模拟赛 9 （总结）

时间：2021-04-17 03:56:05

NOIP2017提高组模拟赛 9 （总结）##

第一题 星星

	天空中有N(1≤N≤400)颗星，每颗星有一个唯一的坐标(x,y),(1≤x,y ≤N)。请计算可以覆盖至少K(1≤K≤N)颗星的矩形的最小面积。矩形的边必须平行于X轴或Y轴，长度必须为正整数。星如果在矩形的边上，也认为它是属于矩形内的。

　　思路：枚举矩形左上角的x，以及在x轴上的长度（矩形的长），然后单调的往下扫。

#include<cstdio>

#include<algorithm>

#include<cmath>

#define imax(a,b) ((a>b)?(a):(b))

#define imin(a,b) ((a<b)?(a):(b))

typedef long long ll;

using namespace std;

int n,ne,ans;

int sum[410][410];

bool d[410][410];

int main()

{

	freopen("a.in","r",stdin);

	freopen("a.out","w",stdout);

	scanf("%d%d",&n,&ne);

	ans=n*n;

	for(int i=1;i<=n;i++)

	{

		int a,b;

		scanf("%d%d",&a,&b); d[a][b]=1;

	}

	for(int i=1;i<=n;i++)

	{

		sum[i][0]=0;

		for(int j=1;j<=n;j++) sum[i][j]=sum[i][j-1]+(d[i][j]?1:0);

	}

	for(int ll=1;ll<=n;ll++)

	{

		for(int i=1;i<=n-ll+1;i++)

		{

			int fr=1,la=1,ss=sum[fr][i+ll-1]-sum[fr][i-1];

			while(la<=n)

			{

				while(ss<ne)

				{

					la++; ss+=sum[la][i+ll-1]-sum[la][i-1];

					if(la>n) break;

				}

				if(la>n) break;

				ans=imin(ans,(la-fr+1)*ll);

				ss-=sum[fr][i+ll-1]-sum[fr][i-1]; fr++;

			}

		}

	}

	printf("%d\n",ans);

	return 0;

}

第二题 战争

	X国和Y国是死对头，X国有N个炮台, Y国有M个基地和K个发电站，炮台、基地、发电站所在的位置的坐标都是整数。Y国的每个发电站能对距离其L以内（包括L）的基地供电。X国的每个炮台都可以发射无限次，每次发射可以击毁一个基地或者一个发电站，消耗的能量为两者距离的平方，这里的距离是欧几里德距离。X国决定要摧毁Y国的所有基地，我们说Y国的某个基地被摧毁的条件是：基地本身被直接摧毁或者对其供电的所有发电站被击。

	问X国摧毁Y国所有基地需要消耗的总能量最小是多少。

	提示：点（X1,Y1）和点（X2,Y2）的欧几里德距离是：

	dis = sqrt((X2-X1)*(X2-X1)+(Y2-Y1)*(Y2-Y1)).

　　经典的网络流01模型，直接构图，跑一次dinic就行了。

　　S向各个基地基地bi连边，代价为距离基地bi最近的炮台之间的距离。

　　各个电厂向T连边，代价为距离电厂ci最近的炮台之间的距离。

　　若电厂ci可以供电给基地dj，那么基地dj连向电厂ci，代价为∞。

　　图的S到T的最小割即为answer。

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#define imax(a,b) ((a>b)?(a):(b))

#define imin(a,b) ((a<b)?(a):(b))

typedef long long ll;

using namespace std;

const int N=50;

const int M=15000;

const int oo=1e9;

struct data { int x,y; } ad[N+10],bd[N+10],cd[N+10];

int to[M],h[M],ne[M],val[M],tt,S,T;

int vis[M],lev[M],q[M];

int an,bn,cn,L,bfstime;

void read(int n,data* A)

{

	for(int i=1;i<=n;i++) scanf("%d",&A[i].x);

	for(int i=1;i<=n;i++) scanf("%d",&A[i].y);

}

void add(int a,int b,int c)

{

	to[++tt]=b; ne[tt]=h[a]; val[tt]=c; h[a]=tt;

	to[++tt]=a; ne[tt]=h[b]; val[tt]=0; h[b]=tt;

}

int dis(data A,data B) { return ((A.x-B.x)*(A.x-B.x)+(A.y-B.y)*(A.y-B.y)); }

void init()

{

	scanf("%d%d%d%d",&an,&bn,&cn,&L);

	read(an,ad); read(bn,bd); read(cn,cd);

	tt=1; S=110; T=111;

	for(int i=1;i<=bn;i++)

	{

		int dd=oo;

		for(int j=1;j<=an;j++) dd=imin(dd,dis(ad[j],bd[i]));

		add(S,i,dd);

	}

	for(int i=1;i<=cn;i++)

	{

		int dd=oo;

		for(int j=1;j<=an;j++) dd=imin(dd,dis(ad[j],cd[i]));

		add(50+i,T,dd);

	}

	int ml=L*L;

	for(int i=1;i<=bn;i++)

	{

		for(int j=1;j<=cn;j++)

		if(dis(bd[i],cd[j])<=ml) add(i,50+j,oo);

	}

}

bool bfs()

{

	lev[S]=1; vis[S]=++bfstime;

	int he=1,ta=1; q[1]=S;

	while(he<=ta)

	{

		int u=q[he++];

		for(int p=h[u];p;p=ne[p])

		{

			int v=to[p];

			if(vis[v]==bfstime || !val[p]) continue;

			q[++ta]=v; vis[v]=bfstime; lev[v]=lev[u]+1;

		}

	}

	return (vis[T]==bfstime);

}

int dfs(int now,int maxf)

{

	int ret=0,t=0;

	if(!maxf || now==T) return maxf;

	for(int p=h[now];p;p=ne[p])

	{

		int v=to[p];

		if(lev[v]!=lev[now]+1 || !val[p]) continue;

		t=dfs(v,imin(maxf,val[p]));

		ret+=t; maxf-=t;

		val[p]-=t; val[p^1]+=t;

	}

	if(!maxf) lev[now]=-1;

	return ret;

}

int dinic()

{

	int ret=0;

	while(bfs()) ret+=dfs(S,oo);

	return ret;

}

int main()

{

	freopen("b.in","r",stdin);

	freopen("b.out","w",stdout);

	init();

	printf("%d\n",dinic());

	return 0;

}

第三题 染色树

	一棵共含有X个结点的树，结点编号1至X，根结点编号是1。有Y种不同的颜色，颜色编号从1至Y。

	现在给每个结点都染上一种颜色，整颗树染色后满足：

	1、对于编号是i的颜色，整颗树当中，至少有一个结点被染成了颜色i。

	2、根结点必须被染成1号颜色，而且整颗树当中，恰好要有Z个结点被染成1号颜色。

	染色过程结束后，现在要计算染色的总代价，总代价等于每一条边的代价之和，那么怎么计算一条边的代价呢？

	不妨设结点a与结点b之间有一条边，该边的权重是W。

	1、如果结点a和结点b最终被染成不同的颜色，那么a与b之间的那条边的代价等于0。

	2、如果结点a和结点b最终被染成相同的颜色，那么a与b之间的那条边的代价等于W。

	现在的问题是：在满足上述要求的前提下，染色树最小的总代价是多少？如果无法完成染色的任务，输出-1。

　　显然的，这是一道树形DP题（DP做的有点多-_-||），X,Y,Z好像都很大。直接做无疑是超时的。

　　那么想考虑一下，answer=-1的情况。每个节点都可以是任意颜色（只是会有代价而已），唯一不满足的情况就是Z>X-Y+1（极限情况）。

　　这是一棵树（这很重要），那么只需要两种颜色就可以使整棵树的任意x和x的父亲的颜色不同。

　　又多了一个颜色1恰好为Z的限制条件，那么也只需要3种颜色就行了（多余的颜色是没任何作用的）。

　　时间复杂度：O（9N³）

#include<cstdio>

#include<algorithm>

#include<cmath>

#define imax(a,b) ((a>b)?(a):(b))

#define imin(a,b) ((a<b)?(a):(b))

typedef long long ll;

using namespace std;

const int oo=1e9;

const int M=700;

int X,Y,Z,ans;

int to[M],ne[M],h[M],val[M],tt;

int f[302][4][302];

void add(int a,int b,int c)

{

	to[++tt]=b; ne[tt]=h[a]; h[a]=tt; val[tt]=c;

	to[++tt]=a; ne[tt]=h[b]; h[b]=tt; val[tt]=c;

}

void dfs(int x,int fa)

{

	for(int i=1;i<=Y;i++)

	{

		for(int j=0;j<=Z;j++) f[x][i][j]=oo;

		if(i==1) f[x][i][1]=0; else f[x][i][0]=0;

	}

	for(int p=h[x];p;p=ne[p])

	{

		int v=to[p];

		if(v==fa) continue;

		dfs(v,x);

		for(int i=1;i<=Y;i++)

		for(int j=Z;j>=0;j--)

		{

			int bes=oo;

			for(int g=1;g<=Y;g++) bes=imin(bes,f[v][g][0]+(i==g?val[p]:0));

			f[x][i][j]=imin(oo,f[x][i][j]+bes);

			for(int k=1;k<=j;k++)

			{

				int yu=oo;

				for(int g=1;g<=Y;g++) yu=imin(yu,f[v][g][k]+(i==g?val[p]:0));

				f[x][i][j]=imin(f[x][i][j],f[x][i][j-k]+yu);

			}

		}

	}

}

int main()

{

	freopen("c.in","r",stdin);

	freopen("c.out","w",stdout);

	scanf("%d%d%d",&X,&Y,&Z); tt=1;

	if(Z>X-Y+1) printf("-1\n"); else

{

	Y=imin(Y,3);

	for(int i=1;i<X;i++) { int a,b,c; scanf("%d%d%d",&a,&b,&c); add(a,b,c); }

	dfs(1,1);

	printf("%d\n",f[1][1][Z]);

}

	return 0;

}

　　终于拿了一次AK了（虽然这次的题目有点水……）。

相关文章