比赛总结

113 阅读 0 评论 75 点赞

我是靠谱客的博主默默枫叶，这篇文章主要介绍比赛总结，现在分享给大家，希望可以做个参考。

比赛总结•
今天的比赛都感觉能做，只是拿几分的问题

第一题：谷仓的安保(passwd)
(File IO): input:passwd.in output:passwd.out

时间限制: 1000 ms 空间限制: 262144 KB

题目描述
Farmer John给谷仓安装了一个新的安全系统，并且要给牛群中的每一个奶牛分配一个有效的密码。一个有效的密码由L(3 <= L <= 15)个小写字母(来自传统的拉丁字母集’a’…‘z’)组成，至少有一个元音(‘a’, ‘e’, ‘i’, ‘o’, 或 ‘u’)和两个辅音(除去元音以外的音节)，并且是按字母表顺序出现的(例如，'abc’是有效的，而’bac’不是) 。

复制代码

1
2
3
4
  给定一个期望长度L和C个小写字母，写一个程序，打印出所有的长度为L、能由这给定的C个字母组成的有效密码。密码必须按字母表顺序打印出来，一行一个。
  
 你的程序只需输出前25,000个有效密码，即使后面还存在有效密码。

输入
第一行: 两个由空格分开的整数，L和C;

第二行: C个空格分开的小写字母，密码是由这个字母集中的字母来构建的。
输出
第一至?行: 每一个输出行包括一个长度为L个字符的密码(没有空格)。输出

行必须按照字母顺序排列。如果存在多于25,000个有效密码，你的程序必须在输出25,000个有效密码后停止。

我看完过后感觉特别像全排列，于是我就按深搜的做了，虽然拿不了满分，但我也想不出来有什么更优的做法了。（大佬勿喷）

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <cstdio>
#include <algorithm>

using namespace std;
int s=25000;
int l,c;
char str[30];
int vis[30];
int f[30];
int n;

void read()
{
	for(int i=1;i<=c;i++)
	{
		char t;
		do{
			
			scanf("%c",&t);	
			
		}while(t==' ' || t=='n');
		
		str[++n]=t;
	}
}

void run(int t)
{
	if(s==0)
		exit(0);
	if(t>l && s!=0)
	{
		for(int i=1;i<=l;i++)
			printf("%c",str[f[i]]);
		printf("n");
		s--;
		return;
	}
	for(int i=f[t-1]+1;i<=c;i++)
	{
		if(vis[i]==0)
		{
			vis[i]=1;
			f[t]=i;
			run(t+1);
			f[t]=0;
			vis[i]=0;
		}
	}
}

int main(int argc, char** argv)
{
	freopen("passwd.in","r",stdin);
	freopen("passwd.out","w",stdout);
	scanf("%d%dn",&l,&c);
	read();
	sort(str+1,str+1+n);
	run(1);
	return 0;
}

跳房子(numgrid)
(File IO): input:numgrid.in output:numgrid.out
时间限制: 1000 ms 空间限制: 262144 KB 具体限制
Time to Submit: 00:34:39
题目描述
奶牛们按不太传统的方式玩起了小孩子们玩的"跳房子"游戏。奶牛们创造了一个5x5的、由与x,y轴平行的数字组成的直线型网格，而不是用来在里面跳的、线性排列的、带数字的方格。然后他们熟练地在网格中的数字中跳：向前跳、向后跳、向左跳、向右跳(从不斜过来跳)，跳到网格中的另一个数字上。他们再这样跳啊跳(按相同规则)，跳到另外一个数字上(可能是已经跳过的数字)。一共在网格内跳过五次后，他们的跳跃构建了一个六位整数(可能以0开头，例如000201)。

复制代码

1
2
 求出所有能被这样创造出来的不同整数的总数。

输入
第1到5行: 这样的网格，一行5个整数。
输出
第1行: 能构建的不同整数的总数
样例输入
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 2 1
1 1 1 1 1
样例输出
15

~~艹，当时我一看，以为两题全排列，于是我又开心的打完了代码：~~
~~可是在打的过程中。。你知道就好~~
（此处无声胜有声待解决555）

卫星照片(satpix)
(File IO): input:satpix.in output:satpix.out
时间限制: 1000 ms 空间限制: 262144 KB
题目描述
Farmer John给他的农场买了W x H像素的卫星照片(1 <= W <= 80, 1 <= H <= 1000)，希望找出最大的"连续的"(互相连接的)牧场。对于一个牧场的任何一对像素，其中一个像素如果能横向的或纵向的与属于这个牧场的另一个像素相连，这样的牧场称作是连续的。(很容易创建形状稀奇古怪的牧场，甚至是围着其它圆圈的圆圈。)每一张照片都数字化的抽象了，牧场区显示为"*",非牧场区显示为"."。下面是一个10 x 5的卫星照片样例:

. . * . . . . . * *

. * * . . * * * * *

. * . . . * . . . .

. . * * * * . * * *

这张照片显示了大小分别为4、16、6个像素的连续牧场区。帮助FJ在他的每张

卫星照片中找到最大的连续牧场。
输入
第1行: 两个由空格分开的整数，W 和 H。

第2到H+1行: 每一行包含W个" * " 或者 " . "，代表卫星照片的横向行。
输出
第1行: 最大连续牧场的大小
样例输入
10 5
. . * . . . . . * *
. * * . . * * * * *
. * . . . * . . . .
. . * * * * . * * *
. . * * * * . * * *
样例输出
16
这一道题我本想用深搜，可是一看数据还是换一下吧，我们枚举每一个点如果他被访问过或者他是‘.’我们就跳过，否则就遍历一遍与他相连的牧场区找最大，emm应该能过吧
代码：

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
char str[1001][81];
int bo[1001][81]={0};
int n,m,ma=0,cnt;
int xy[4][2]={{0,-1},{0,1},{-1,0},{1,0}};
void dfs(int i,int j)
{
	int k,tx,ty;
	bo[i][j]=1;
	for(k=0;k<4;++k)
	{
		tx=i+xy[k][0];
		ty=j+xy[k][1];
		if(tx>=0&&tx<m&&ty>=0&&ty<n&&str[tx][ty]=='*'&&(!bo[tx][ty]))
		{
			cnt++;
			dfs(tx,ty);
		}
	}
}
int main()
{
	freopen("satpix.in","r",stdin);
	freopen("satpix.out","w",stdout);
	int i,j;
	scanf("%d %d",&n,&m);
	for(i=0;i<m;++i)
	{
		scanf("%s",&str[i]);
	}
	for(i=0;i<m;++i)
	{
		for(j=0;j<n;++j)
		{
			if(!bo[i][j]&&str[i][j]=='*')
			{
				cnt=0;
				dfs(i,j);
				if(ma<cnt)ma=cnt;
			}
		}
	}
	printf("%dn",++ma);
	return 0;
}