2018.10.17考试

2018.10.17考试总结

1、咒语

(curse.pas/c/cpp)

【题目描述】

亮亮梦到自己来到了魔法城堡, 但一扇巨大的石门阻拦了他通向城堡内的路。正当他沮丧之际,突然发现门上有一处机关,机关上有一张很长的纸条。亮亮拿起纸条的一端,只见上面写着打开机关的方法: “打开机关需要念动符咒,咒语是一串长为 L 的由 0 和 1 组成的字符串。在这张长纸条上列了 n 个长为 L 的字符串,正确的咒语即是在纷繁的 2^L 种字符串中,与这些纸条上的字符串相异度之和最小,并且在满足这一条件下,0 的个数最多的字符串。两个字符串的相异度定义为对应位置不相等的字符对的个数。如‘011’和‘001’的相异度为 1,因为它们有且只有第二个位置上的字符不相等。 ”亮亮拉起纸条,只觉得纸条似乎永远也拉不完。这上面有着数以万计的字符串,而每一个字符串的长度也或百或千,以人力看来是无法得到正确的咒语。你能帮帮他,让他得以进入魔法城堡,一窥其中的奥秘吗?

【输入格式】

第一行为一个数字 N 。
接下来的 N 行, 每行为一个长为 L 的 01 字符串。 数据保证 N 个字符串等长。

【输出格式】

只有一行,是一个长为 L 的字符串 S,即为正确的咒语。

【样例输入】

4
01011
01001
01101
10111

【样例输出】

01001

【数据规模】

对于 20%的数据,N<=5;
对于 60%的数据,N<=100;
对于 100%的数据,1<=N<=1000,1<=L<=1000。

简单题,见下

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char s[1010][1010];
int n,k0,k1;
int main()
{
	freopen("curse.in","r",stdin);
	freopen("curse.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;++i)
		scanf(" %s",s[i]);
	int len=strlen(s[1]);
	for(int i=0;i<len;++i)
	{
		k0=0,k1=0;
		for(int j=1;j<=n;++j)
		{
			if(s[j][i]=='1')k1++;
			else k0++;
		}
		if(k0>=k1)printf("0");
		else printf("1");
	}
	return 0;
}

2、神光

(light.pas/c/cpp)

【题目描述】

亮亮成功地念出了咒语,石门缓缓地自动移开,一道道绚丽的神光从城堡内激射而出。亮亮好奇而又兴奋地走入了城堡中,迎面有一座极长的魔法阵。魔法阵可以看作一条直线,它被均匀地分成了 1 000 000 000 个位置,一个位置可以看成是一个格子。有些位置上筑有法坛,一共 N 座。亮亮只有破了眼前的魔法阵,才能继续前进,而欲破法阵,必须毁掉所有的法坛。亮亮身前有两根法杖:一根颜色血红,能发红色神光,光芒可以笼罩连续 L个位置并摧毁这 L 个位置上所有的法坛,最多使用 R 次;另一根颜色碧绿,能发绿色神光,光芒可以笼罩连续 2L 个位置,并摧毁这 2L 个位置上所有的法坛,最多使用 G 次。法杖的神奇之处在于,L 的值必须由亮亮事先设定好,并且一经设定,便无法更改。亮亮需要在规定的次数下摧毁所有法坛,并且使得 L 最小。

【输入格式】

第一行三个整数 N, R, G。
第 i (2<=i<=n+1) 行一个整数(A_i) ,表示第 i 座法坛的位置。

【输出格式】

只有一个整数,表示 L 的最小值。

【样例输入】

3 1 1
22
1
7

【样例输出】

4

【样例解释】

亮亮将 L 设为 4,并用红色神光笼罩 21-24 位置,用绿色神光笼罩 1-8 位置。

【数据规模】

对于 50%的数据,N <= 100;
对于 100%的数据,1 <= N <= 2000,1 <= R, G,(A_i)<= 1,000,000,000。

二分加dp
1.R+G>=N时 输出1
2.先把(A_i)从小到大排序,然后二分枚举L的长度,对于每一个L,先预处理在b[i]表示第i点使用红法杖最远到达的点和c[i]表示第i点使用绿法杖最远到达的点,f[i][j]表示使用i个红法杖和使用j个绿法杖所能到达的最远点,可得f[i][j]=max(b[f[i-1][j]+1],c[f[i][j-1]+1])。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,r,g,a[2010],b[2010],c[2010],f[2010][2010];
bool ss(int L)
{
	memset(b,0,sizeof(b));
	memset(c,0,sizeof(c));
	memset(f,0,sizeof(f));
	for(int i=1;i<=n;++i)
		for(int j=i;j<=n;++j)
		{
			if(a[j]-a[i]+1<=L)b[i]=j;
			if(a[j]-a[i]+1<=L*2)c[i]=j;
		}
	b[n+1]=c[n+1]=n;
	for(int i=0;i<=r;++i)
		for(int j=0;j<=g;++j)
		{
			if(i!=0)f[i][j]=max(f[i][j],b[f[i-1][j]+1]);
			if(j!=0)f[i][j]=max(f[i][j],c[f[i][j-1]+1]);
		}
	if(f[r][g]==n)return 1;
	return 0;
}
int main()
{
	freopen("light.in","r",stdin);
	freopen("light.out","w",stdout);
	scanf("%d%d%d",&n,&r,&g);
	for(int i=1;i<=n;++i)
		scanf("%d",&a[i]);
	if(r+g>=n)
	{
		printf("1
");
		return 0;
	}
	sort(a+1,a+1+n);
	a[0]=0;
	int ll=1,rr=a[n]-a[1]+1,ans;
	while(ll<=rr)
	{
		int mid=(ll+rr)>>1;
		if(ss(mid))rr=mid-1,ans=mid;
		else ll=mid+1;
	}
	printf("%d",ans);
	return 0;
}

3、迷宫

(maze.pas/c/cpp)

【题目描述】

破了魔法阵后,亮亮进入了一座迷宫。这座迷宫叫做“梦境迷宫” ,亮亮只有走出这座迷宫,才能从睡梦中醒来。
梦境迷宫可以用无向图来表示。它共有 n 个点和 m 条双向道路,每条道路都有边权,表示通过这条道路所需的时间,且每条道路可以多次经过。亮亮位于一号点,而出口则是 n 号点。原本,亮亮该找到一条最短路,快速冲出迷宫,然而,梦境迷宫的特殊之处在于,如果沿着最短路到达出口,亮亮就会永远陷入梦境。因此,亮亮必须寻找一条次短路。次短路的长度须严格大于最短路(可以有多条)的长度,同时又不大于所有除最短路外的道路的长度。你的任务,就是编写一个程序,帮助亮亮找到通向出口的次短路。

【输入格式】

第一行有两个整数 n、m,表示迷宫内共有 n 个点,m 条边。
接下来 m 行,每行三个整数 x、y、z,表示结点 x 和 y 之间连有一条边权为z 的无向边。

【输出格式】

一个整数,表示次短路的长度。

【样例输入】

4 4
1 2 2
2 4 4
2 3 3
3 4 4

【样例输出】

9

【样例解释】

最短路:1 -> 2 -> 4 (长度为 2+4=6)
次短路:1 -> 2 -> 3 -> 4 (长度为 2+3+4=9)

【数据规模】

对于 100%的数据,1 <= n <= 5000,1 <= m <= 100,000。
对于 100%的数据,1 <= z <= 5000,z 表示无向边的边长。

严格次短路,从点1和点n,分别求一个最短路,枚举每一条边,求点1和点n到该路径两端的最短距离,每次进行比较比最短路长且比其他路径短的距离长度。

90分(不知道为啥分这么高的,求最短路,枚举最短路径上每一条路消失,再求最短路)

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define int long long
using namespace std;
struct Edge
{
	int u,v,w,nxt;
}e[200010];
int head[200010],tot,n,m,dis[5010],vis[5010],hee[5010],haa[5010],hhh=0x7fffffff;;
void add(int u,int v,int w)
{
	e[++tot].u=u;
	e[tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}
int spfa()
{
	queue<int>q;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				hee[v]=i;
				haa[v]=u;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return dis[n];
}
int spfa2()
{
	queue<int>q;
	memset(dis,0x3f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	dis[1]=0;
	q.push(1);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
	return dis[n];
}
signed main()
{
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	cin>>n>>m;
	for(int i=1,u,v,w;i<=m;++i)
	{
		cin>>u>>v>>w;
		add(u,v,w);
		add(v,u,w);
		hhh=min(hhh,w);
	}
	hhh*=2;
	int k=spfa();
	int zd=0x3f3f3f3f;
	int v=n,sd;
	while(v!=1)
	{
		sd=hee[v];
		int cc=e[sd].w;
		e[sd].w=0x3f3f3f3f;
		zd=min(spfa2(),zd);
		e[sd].w=cc;
		v=haa[v];
	}
	if(zd==k)zd+=hhh;
	cout<<zd<<"
";
	return 0;
}

正解

#include<iostream>
#include<queue>
#include<cstring>
#include<cstdio>
using namespace std;
const int N=5010;
const int INF=0x3f3f3f3f;
struct Edge
{
	int v,w,nxt;
}e[200100];
int dis1[N],dis2[N],n,m,tot,head[N];
bool vis[N];
void add(int u,int v,int w)
{
	e[++tot].v=v;
	e[tot].w=w;
	e[tot].nxt=head[u];
	head[u]=tot;
}
void spfa(int s,int *dis)
{
	queue<int>q;
	memset(vis,0,sizeof(vis));
	dis[s]=0;
	vis[s]=1;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
		q.pop();
		vis[u]=0;
		for(int i=head[u];i;i=e[i].nxt)
		{
			int v=e[i].v;
			if(dis[v]>dis[u]+e[i].w)
			{
				dis[v]=dis[u]+e[i].w;
				if(!vis[v])
				{
					vis[v]=1;
					q.push(v);
				}
			}
		}
	}
}
int main()
{
	freopen("maze.in","r",stdin);
	freopen("maze.out","w",stdout);
	scanf("%d%d",&n,&m);
	memset(dis1,0x3f,sizeof(dis1));
	memset(dis2,0x3f,sizeof(dis2));
	for(int i=1,u,v,w;i<=m;++i)
	{
		scanf("%d%d%d",&u,&v,&w);
		add(u,v,w);
		add(v,u,w);
	}
	spfa(1,dis1);
	spfa(n,dis2);
	int ans=INF,tmp;
	for(int i=1;i<=n;i++)
		for(int j=head[i];j;j=e[j].nxt)
		{
			tmp=dis1[i]+dis2[e[j].v]+e[j].w;
			if(tmp>dis1[n]&&ans>tmp) ans=tmp;
		}
	printf("%d
",ans);
	return 0;
}
原文地址:https://www.cnblogs.com/axma/p/9805184.html