纪中训练 day1 【NOIP普及组】模拟赛D组 解题报告

时间：2021-03-12 09:48:21

☞第一题 逃离洞穴☜

大意

一个无向图，求第一个点和第n个点到所有点的最短路中小于T的个数，并统计有人的点中最短路的最长距离。

思路

首先这题n<=500，O(n³)过不了（虽然我也不知道为什么其他人用floyed过了，反正我老是超时）。用spfa算法，运行两次，分别从1和n出发，取两次的最优解，存到ans数组里，最后访问所有洞穴就可以了。

代码:floyedO(n³) 80分,加输入流可到90分

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 501
#define M 5001
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;int b[N],ans1,ans2,te;
int n,m,k,x,y,z,T,l[N][N];
void read(int &f)//这个东西可以加10分。。。
{
	f=0;char c;bool d=0;
	while (c=getchar(),c<'0'||c>'9') if(c=='-') d=1;f=f*10+c-48;
	while (c=getchar(),c>='0'&&c<='9') f=f*10+c-48;
	if(d) f*=-1;
}
int main()
{
	freopen("escape.in","r",stdin);
	freopen("escape.out","w",stdout);
    memset(l,127/3,sizeof(l));
    read(n);read(m);read(T);
    r(i,1,m)
     {
     	read(x);read(y);read(z);if (x==y) continue;//防止环，虽然题目没说，但还是小心点。
     	l[y][x]=l[x][y]=z;
     }
    read(k);
    r(i,1,k)
     read(te),b[te]++;
    r(k,1,n)
     r(i,1,n)
      r(j,1,n)//floyed
       if(i!=j&&i!=k&&k!=j)
        l[i][j]=min(l[i][j],l[i][k]+l[k][j]);
    l[1][n]=l[n][1]=l[n][n]=l[1][1]=0;//已经在洞穴的话距离为0
    r(i,1,n)
     {
     	te=min(l[i][1],l[i][n]);//求最小值
     	if(te<=T)//满足条件
     	 	ans1+=b[i];
     	if (b[i]) ans2=max(ans2,te);//如果有人，统计最长长度
     }
    printf("%d\n%d",ans1,ans2);//输出
}


代码:spfa O(KE) AC 

#include<cstdio>
#include<iostream>
#include<cstring>
#define N 501
#define M 5001
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;int b[2*N];
struct node{int next,to,w;}a[2*M];//无向图
int n,m,k,x,y,z,tot,fa[N],ans[N],dis[N],u,team[N*2],ans1,ans2,T,te;
int add(int u,int v,int w)//建图
{
	a[++tot].next=fa[u];
	a[tot].to=v;
	a[tot].w=w;
	fa[u]=tot;
}
void spfa(int wh)
{
	memset(dis,0x3f,sizeof(dis));int head=0,tail=1;bool v[N]={0};team[1]=wh;v[wh]=true;dis[wh]=0;//初始化
	do
	{
		head=head%N+1;//循环队列
		u=team[head];v[u]=true;//标记
		for(int i=fa[u];i;i=a[i].next)
			if (dis[a[i].to]>dis[u]+a[i].w)
			{
				dis[a[i].to]=dis[u]+a[i].w;
				if(!v[a[i].to])
				{
					tail=tail%N+1;
					team[tail]=a[i].to;//入队
					v[a[i].to]=true;//标记
				}
			}
		v[u]=false;//标记
	}while(head!=tail);
	r(i,1,n)
	 ans[i]=min(dis[i],ans[i]);//取最优解
}
int main()
{
    freopen("escape.in","r",stdin);
	freopen("escape.out","w",stdout);
    scanf("%d %d %d",&n,&m,&T);r(i,1,n) ans[i]=0x7fffffff;//初始化
    r(i,1,m)
     {
     	scanf("%d %d %d",&x,&y,&z);
     	add(x,y,z);add(y,x,z);//无向图
     }
    scanf("%d",&k);
    r(i,1,k) 
     scanf("%d",&te),b[te]++;
    spfa(1);spfa(n);ans[1]=ans[n]=0;
    r(i,1,n)
     {if (ans[i]<=T)ans1+=b[i];if (b[i])ans2=max(ans[i],ans2);}
    printf("%d\n%d",ans1,ans2);//输出
}


☞第二题 抓捕嫌疑犯☜

大意

有n个人，离小Z第K远的那个（可能有多个）是嫌疑犯，现给定小Z的坐标和这些人的坐标，输出嫌疑犯的坐标。

范围

对于30%的数据，n<=300；

对于60%的数据，n<=3000；

对于100%的数据，n<=30000，坐标范围（-10000，10000）。

思路

排序+去重（虽然看到这个就知道用桶，但是这题数据很大，不能用桶，得手动去重）

代码

#include<cstdio>
#include<cmath>
#include<algorithm>
#define r(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
int qx,qy,n,k,ans,cc;bool ok=true; double aa,bb;
struct node{int x,y;double jl;}a[30001];//结构体不解释
int dx[30001],dy[30001] ;//嫌疑犯坐标
double jl(int x,int y)//取他们离小z有多远
{
	return sqrt(abs(qx-x)*abs(qx-x)+abs(qy-y)*abs(qy-y));
}
bool cmp(node x,node y)//排序
{
	return x.jl>y.jl||x.jl==y.jl&&x.x<y.x||x.jl==y.jl&&x.x==y.x&&x.y<y.y;
}
int main()
{
	freopen("suspect.in","r",stdin);
	freopen("suspect.out","w",stdout);
	scanf("%d %d\n%d %d",&qx,&qy,&n,&k);
	r(i,1,n)
	 {scanf("%d %d",&a[i].x,&a[i].y);a[i].jl=jl(a[i].x,a[i].y);}//输入并计算
	sort(a+1,a+1+n,cmp);cc=0;//排序
    for(int i=1;i<=n;i++) 
     {
     	aa=a[i].jl;
		if (cc==k) {bb=aa;break;}
		if (bb!=aa) {cc++;bb=aa;}//去重工作
     }
	r(j,k,n)
	 if(a[j].jl==bb)
	  {ok=false;ans++;dx[ans]=a[j].x;dy[ans]=a[j].y;}//找嫌疑犯
	 else if (!ok)  break;//小优化
	printf("%d\n",ans) ;
	r(i,1,ans)
	 printf("%d %d\n",dx[i],dy[i])//输出;
}

☞第三题 堆箱子☜

大意

有n种箱子（长方体），它们可以任意旋转，现在堆箱子。上面箱子的长和宽必须大于下面箱子长和宽，问最多能堆多高（假设箱子有无数个）

思路

预处理+排序（按长和宽）+动态规划
动态转移方程： 
if(x[i].a>x[j].a&&x[i].b>x[j].b)//满足要求
	   f[j]=max(f[j],f[i]+x[j].h);//堆或者不堆

代码

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;
int f[601],n,k,a,b,h,ans;
struct node{int a,b,h;}x[601];
bool cmp(node x,node y)//长和宽排
{
	return x.a>y.a||x.a==y.a&&x.b>y.b;
}
void be(int a,int b,int h)//旋转
{
	x[++k].a=a;x[k].b=b;x[k].h=h;
}
int main()
{
	freopen("boxes.in","r",stdin);
	freopen("boxes.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++)
	 {
	 	k=(i-1)*6;scanf("%d %d %d",&a,&b,&h);
	 	be(a,b,h);be(a,h,b);
	 	be(b,a,h);be(b,h,a);
	 	be(h,a,b);be(h,b,a);//六种情况
	 }
	 n*=6;//改变n的值
	sort(x+1,x+1+n,cmp);//排序
	for(int i=1;i<=n;i++) f[i]=x[i].h;//初始化
	for(int i=1;i<n;i++)
	{
	 for(int j=i+1;j<=n;j++)
	  if(x[i].a>x[j].a&&x[i].b>x[j].b)
	   f[j]=max(f[j],f[i]+x[j].h);//动态转移
	   ans=max(f[i],ans);//统计最优解
    }
	printf("%d",ans);
}


☞第四题 能源大亨☜

大意

好吧，没想到最后一题反而最水
有一个长度为n的工厂，一次建造一个工厂，k个工厂每个时间会产生k个能量，有两种工厂，一个占两个一个占一个。问数轮之后，会产生几点能量。

思路

贪心

代码

#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
char c[100001];int n;long long ans,c1,c2;
int main()
{
	freopen("energy.in","r",stdin);
	freopen("energy.out","w",stdout);
	scanf("%d",&n);
	scanf("%s",c);
	for(int i=0;i<strlen(c);i++)
	 {
	 	if(c[i]=='1'&&n)//能量够且是1
	 	 {
	 	 	c1++;n--;
	 	 }
	 	else
	 	if(c[i]=='1'&&!n&&c2)//是1但能量不够，拆掉一个二号电厂
	 	 {
	 	 	c2--;c1++;n++;
	 	 }
	 	else
	 	if(c[i]=='2'&&n>1)//实在不行再建造二号
	 	{
	 		c2++;n-=2;
	 	}
	 	ans+=c1+c2;//累加
	 }
	printf("%lld",ans);//输出
}



标签：

相关文章