总结 Algorithm 105

水题   or   难题 QAQ

T1 东东的蚂蚱

考查知识点:模拟;

题目描述:

东东爸给东东带回来一只聪明的蚂蚱,据说这个蚂蚱认识英文字母,好神奇的事情哦~~
为了测试这件事情,东东拿来一条长长的纸带,上面有N个格子排成一列,每一个格子中都有一个大写的字母。东东每次把聪明的蚂蚱放在地纸带最前端的外面,聪明的蚂蚱就会一直向前跳,跳到它喜欢的字母的格子中,最后跳出纸带。
经过观察,东东发现蚂蚱只喜欢特定的M个大写字母;并且聪明的蚂蚱的弹跳能力极强,每次跳越的距离为[1,X]区间中的某一个正整数。
现给出一条新的纸带,以及蚂蚱喜欢的特定的字母。东东想知道X的最小值为多少?

输入格式

第一行两个正整数N和M
第二行M个大写字母组成的字符串,为聪明的蚂蚱喜欢的那M个字母(M个字母互不相同)。
第三行为N个大写字母的组成的字符串,表示纸带上每个格子中的字母。

输出格式

一行一个正整数,表示最小的X值。

思路:

开两个字符串,一个存储蚂蚱喜欢的数字,一个存储纸带上的字母,从头到尾O(n)时间扫一遍,记录下相邻两个蚂蚱喜欢的数字之间的最大值,最后注意:要求的是蚂蚱跳跃的最长距离,它最后需要跳出纸带的长度也需要比较;

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int m,n,nmp,ans;
char a[11000];
char f[30];
int tmp[30];
int main()
{
	scanf("%d%d",&n,&m);
	scanf("%s",&f[0]);
	scanf("%s",&a[0]);
	for(int i=0;i<m;i++)
	{
		tmp[f[i]-'A'+1]=1;
	}
	for(int i=0;i<n;i++)
	{
		if(tmp[a[i]-'A'+1]==1)
		{
			ans=max(ans,i+1-nmp);
			nmp=i+1;
		}
	}
	ans=max(ans,n+1-nmp);
	printf("%d",ans);
	return 0;
}

T2 东东被困沼泽地

考查知识点:DP

题目描述

东东和东东爸跑出去野外穿越,结果不想东东被困在了一处沼泽地里。东东爸通过观察这片沼泽地是一个N*M的矩阵A,每一个位置要么是泥沼,要么是坚硬的石头。如果Ai,j <0表示的泥沼,否则就是石头。
初始东东爸在(1,1)位置,并且只能向右和向下走,因为这样才能最快的接近被困在(N,M)位置的东东。每走到一个位置就得到这个位置的值,问如何确定方案,东东爸才能在获得最大的值的情况下救出东东呢?
规定的行走方案由下面3条组成:

  • 每次可以向右走一格。例如:(x,y)->( x,y+1 )
  • 每次可以向下走一格。例如:(x,y)->( x+1,y )
  • 每次可以向右走到当前列编号的整数倍的编号的格子。例如:(x,y)->( x,y*k ),其中k为合法的正整数。

输入格式

第一行两个正整数N和M。
接下来N行,每行M个整数。用来描述矩阵A。其中位置(1,1)和(N,M)的值为0。

输出格式

一行一个正整数,表示东东爸救出东东的情况下获得的最大值。

这道题还是很水的,需要注意的是原本a[i][j]小于0,被f[0][j]或f[i][0]更新为0;这时我们只需要特判一下,这道题就AC了;

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m;
int f[400][400];
int a[400][400];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
                        if(i==1)f[i][j]=f[i][j-1];
			else if(j==1)f[i][j]=f[i-1][j];
			else f[i][j]=max(f[i][j-1],f[i-1][j]);
			for(int k=1;k<=j-1;k++)
			{
				if(j%k==0) f[i][j]=max(f[i][j],f[i][k]);
			}
			f[i][j]+=a[i][j];
		}
	}
	printf("%d",f[n][m]);
	return 0;
}

T3东东爸建机房

考查知识点:并查集or最小生成树

题目描述:

吉林省的信息学奥林匹克竞赛的成绩越来越好,吸引了非常多的有志学生选择学习信息学竞赛。但是现有机房的电脑明显是不够用了,东东爸就建议再建立一个超级大的机房。但是预算却非常有限,逼的东东爸在能省的地方绝对不会多花一分钱。
现在已知一共N个设备,编号为1到N。设备分两种,交换机或者电脑。上网规则如下:

  • 所有的交换机都连了外网。
  • 如果某台电脑i直连了交换机那么电脑i就能上网。
  • 如果电脑i能上网,电脑j连接了电脑i,那么电脑j也能上网。

但是布线的施工方却是个奸商,虽然最后保证了所有的电脑都能上网了,但是布线时布了非常多的没有用的网线,甚至居然有几台电脑都成了环状拓扑结构了。东东爸火冒三丈,要求施工方撤掉尽可能多的网线,还得保证所有的机器都能上网。
怕施工方耍滑头,你能先帮东东爸算算最多能撤销的网线的长度么?

输入格式:

第一行三个正整数N、M和K,表示有N个设备,M条网线,K台交换机。
第二行有K个正整数,表示交换机的编号。
接下来M行三个正整数x,y,z。表示x号设备到y号设备的网线长度为z。

输出格式:

一个整数表示最多能撤销的网线的总长度。

思路:

一道裸的并查集,造一个原点0,(就是外网),把交换机连在上面,然后先将边从小到大排序,再加边枚举,如果加上这条边出现了环,就把它去掉,累计便是答案;

迷之错误:结构体排序时应严格大于或小于!!!否则-50分;

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int n,m,k,ans;
int f[2000];
struct your
{
    int x,y,c;
}a[11000];
bool cmp(your j,your k)
{
    //return j.c<=k.c;
    return j.c<k.c;
}
int find(int x)
{
    if(f[x]==x)return x;
    return f[x]=find(f[x]);
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    for(int i=0;i<=n;i++) f[i]=i;
    for(int i=1;i<=k;i++)
    {
        int tmp;
        scanf("%d",&tmp);
        f[tmp]=0;
    }
    for(int i=1;i<=m;i++)
        scanf("%d%d%d",&a[i].x,&a[i].y,&a[i].c);
    sort(a+1,a+m+1,cmp);
    for(int i=1;i<=m;i++)
    {
        int dx=find(a[i].x);
        int dy=find(a[i].y);
        if(dx==dy) ans+=a[i].c;
        else f[dx]=dy;
    }
    printf("%d",ans);
    return 0;
}

这是一套本来可以AK的题,让我硬生生的写挂了QAQ

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注