【作业向】程序设计思维与实践 Week12 作业

发表于 | 分类于 ，
字数统计: 2.9k | 阅读时长 ≈ 14

【作业向】程序设计思维与实践 Week12作业

♔A 必做题1

♔Problem

给出n个数，zjm想找出出现至少(n+1)/2次的数， 现在需要你帮忙找出这个数是多少？

♔Input

本题包含多组数据：
每组数据包含两行。
第一行一个数字N(1<=N<=999999) ，保证N为奇数。
第二行为N个用空格隔开的整数。
数据以EOF结束。

♔Output

对于每一组数据，你需要输出你找到的唯一的数。

♔Example

♔Input

1
2
3
4
5
6
5
1 3 2 3 3
11
1 1 1 1 1 5 5 5 5 5 5
7
1 1 1 1 1 1 1

♔Output

1
2
3
3
5
1

♔解题思路

遍历一遍记录出现次数，找到出现次数大于（n+1）/2的数立即结束循环（因为只能有一个这种数）

♔代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
int a[1000005],n,maxn;

int main()
{
	int i,j;
	while(scanf("%d",&n)!=EOF)
	{
		maxn=0;
		memset(a,0,sizeof(a));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&j);
			a[j]++;
			maxn=max(maxn,j);
		}
		for(i=0;i<=maxn;i++)
			if(a[i]>=(n+1)/2)
			{
				printf("%d",i);
				break;
			} 
		printf("\n");
	}
}

♔B 必做题2

♔Problem

zjm被困在一个三维的空间中,现在要寻找最短路径逃生！
空间由立方体单位构成。
zjm每次向上下前后左右移动一个单位需要一分钟，且zjm不能对角线移动。
空间的四周封闭。zjm的目标是走到空间的出口。
是否存在逃出生天的可能性？如果存在，则需要多少时间？

♔Input

输入第一行是一个数表示空间的数量。
每个空间的描述的第一行为L，R和C（皆不超过30）。
L表示空间的高度，R和C分别表示每层空间的行与列的大小。
随后L层，每层R行，每行C个字符。
每个字符表示空间的一个单元。’#‘表示不可通过单元，’.‘表示空白单元。
zjm的起始位置在’S’，出口为’E’。每层空间后都有一个空行。
L，R和C均为0时输入结束。

♔Output

每个空间对应一行输出。
如果可以逃生，则输出如下
Escaped in x minute(s).
x为最短脱离时间。

如果无法逃生，则输出如下
Trapped!

♔Example

♔Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3 4 5
S....
.###.
.##..
###.#

#####
#####
##.##
##...

#####
#####
#.###
####E

1 3 3
S##
#E#
###

0 0 0

♔Output

1
2
Escaped in 11 minute(s).
Trapped!

♔解题思路

一道比较简单的bfs题，注意边界的处理和六个方向的处理（以及不要学我上来顺手写了个dfs然后TLE了就行

♔代码

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
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
struct data
{
	int x,y,z;
	int l;
};
int h,m,n,minn,flag;
int sh,sm,sn,eh,em,en;
int kj[35][35][35],visit[35][35][35];
int fx[6][3]= {{1,0,0},{0,1,0},{0,0,1},{0,0,-1},{0,-1,0},{-1,0,0}};
char c;
queue<data> q;

int main()
{
	int i,j,k;
	scanf("%d%d%d",&h,&n,&m);
	while(h!=0 || n!=0 || m!=0)
	{
		memset(kj,0,sizeof(kj));
		memset(visit,0,sizeof(visit));
		while(!q.empty()) q.pop();
		flag=0;
		for(i=1; i<=h; i++)
			for(j=1; j<=n; j++)
				for(k=1; k<=m; k++)
				{
					scanf(" %c",&c);
					if(c=='.') kj[i][j][k]=1;
					else if(c=='#') kj[i][j][k]=0;
					else if(c=='S') sh=i,sn=j,sm=k;
					else if(c=='E') eh=i,en=j,em=k,kj[i][j][k]=1;
				}
		data u,v;
		u.x=sn,u.y=sm,u.z=sh,u.l=0;
		visit[sh][sn][sm]=1;
		q.push(u);
		while(!q.empty())
		{
			u=q.front();
			q.pop();
			//printf("-%d-%d-%d-\n",u.z,u.x,u.y);
			if(u.z==eh && u.x==en && u.y==em)
			{
				printf("Escaped in %d minute(s).\n",u.l);
				flag=1;
				break;
			}
			for(i=0; i<6; i++)
			{
				if(u.z+fx[i][0]>0 && u.z+fx[i][0]<=h && u.x+fx[i][1]>0 && u.x+fx[i][1]<=n && u.y+fx[i][2]>0 && u.y+fx[i][2]<=m)
				{
					if(!visit[u.z+fx[i][0]][u.x+fx[i][1]][u.y+fx[i][2]] && kj[u.z+fx[i][0]][u.x+fx[i][1]][u.y+fx[i][2]])
					{
						visit[u.z+fx[i][0]][u.x+fx[i][1]][u.y+fx[i][2]]=1;
						v.z=u.z+fx[i][0],v.x=u.x+fx[i][1],v.y=u.y+fx[i][2],v.l=u.l+1;
						//printf("+-%d-%d-%d-\n",v.z,v.x,v.y);
						q.push(v);
					}
				}
			}
		}
		//printf("%d+++\n",flag);
		if(!flag) printf("Trapped!\n");
		scanf("%d%d%d",&h,&n,&m);
	}
	return 0;
}

♔C 必做题3

♔Problem

东东每个学期都会去寝室接受扫楼的任务，并清点每个寝室的人数。
每个寝室里面有ai个人(1<=i<=n)。从第i到第j个宿舍一共有sum(i,j)=a[i]+…+a[j]个人
这让宿管阿姨非常开心，并且让东东扫楼m次，每一次数第i到第j个宿舍sum(i,j)
问题是要找到sum(i1, j1) + … + sum(im,jm)的最大值。且ix <= iy <=jx和ix <= jy <=jx的情况是不被允许的。也就是说m段都不能相交。
注：1 ≤ i ≤ n ≤ 1e6 , -32768 ≤ ai ≤ 32767 人数可以为负数。。。。(1<=n<=1000000)

♔Input

输入m，输入n。后面跟着输入n个ai 处理到 EOF

♔Output

输出最大和

♔Examples

♔Input

1
2
1 3 1 2 3
2 6 -1 4 -2 3 -2 3

♔Output

1
2
6
8

♔解题思路

我们用二维数组dp[i] [j]表示选了i段，到第j个为止，最大的结果，其中第j个必选。对于第j个数，我们有两种处理方法：

与最后一段合并，dp[i] [j]=dp[i] [j-1]+a[j];
成为新的一段，dp[i] [j]=dp[i-1] [k]+a[j]; (i-1<k<j)

然后三者取最大值即可，但是问题是这样会MLE，由于dp[i] [j]都是从dp[i-1]或者dp[i]推过来的，我们将第一维优化掉，只开两个一维数组就可以了。

♔代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
int n,m,ans;
int dp[1000005],dpp[1000005],a[100005];

int main()
{
	int i,j,k;
	while(scanf("%d%d",&m,&n)!=EOF)
	{
		memset(dp,0,sizeof(dp));
		memset(dpp,0,sizeof(dpp));
		for(i=1;i<=n;i++) scanf("%d",&a[i]);
		for(i=1;i<=m;i++)
		{
			ans=-0x7fffffff;
			for(j=i;j<=n;j++)
			{
				dp[j]=max(dp[j-1]+a[j],dpp[j-1]+a[j]);
				dpp[j-1]=ans;
				ans=max(ans,dp[j]);
			}
		}
		printf("%d\n",ans);
	}
	return 0;
}

♔D 选做题1

♔Problem

We give the following inductive definition of a “regular brackets” sequence:

  • the empty sequence is a regular brackets sequence,
  • if s is a regular brackets sequence, then (s) and [s] are regular brackets sequences, and
  • if a and b are regular brackets sequences, then ab is a regular brackets sequence.
  • no other sequence is a regular brackets sequence

For instance, all of the following character sequences are regular brackets sequences:

1
(), [], (()), ()[], ()[()]

while the following character sequences are not:

1
(, ], )(, ([)], ([(]

Given a brackets sequence of characters a1a2 … an, your goal is to find the length of the longest regular brackets sequence that is a subsequence of s. That is, you wish to find the largest m such that for indices i1, i2, …, im where 1 ≤ i1 < i2 < … < im ≤ n, ai1ai2 … aim is a regular brackets sequence.

Given the initial sequence ([([]])], the longest regular brackets subsequence is [([])].

♔Input

The input test file will contain multiple test cases. Each input test case consists of a single line containing only the characters (, ), [, and ]; each input test will have length between 1 and 100, inclusive. The end-of-file is marked by a line containing the word “end” and should not be processed.

♔Output

For each input case, the program should print the length of the longest possible regular brackets subsequence on a single line.

♔Examples

♔Input

1
2
3
4
5
6
((()))
()()()
([]])
)[)(
([][][)
end

♔Output

1
2
3
4
5
6
6
4
0
6

♔解题思路

一道区间DP题，dp[i] [j]表示区间 [i,j] 中合法序列的长度，根据上述条件进行状态转移即可：

条件一：
空串为合法序列，那么初始化 dp 数组为 0 即可
条件二：遇到合法序列的左右括号匹配则长度加 2
dp[i] [j]=max(dp[i] [j],dp[i+1] [j−1]+2)
条件三：A、B为合法序列，则AB为合法序列
dp[i] [j]=max(dp[i] [j],dp[i] [k]+dp[k+1] [j])

最后的答案为dp[0] [n-1]

♔代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
char c[105];
int dp[105][105],n; 

int main()
{
	int i,j,k,h;
	while(scanf(" %s",c)!=EOF)
	{
		if(c[0]=='e') break;
		n=strlen(c);
		memset(dp,0,sizeof(dp));
		for(k=1;k<n;k++)
		{
			for(i=0;i+k<n;i++)
			{
				j=i+k;
				if((c[i]=='(' && c[j]==')') || (c[i]=='[' && c[j]==']'))
				{
					dp[i][j]=dp[i+1][j-1]+2;
				}
				for(h=i;h<j;h++)
					dp[i][j]=max(dp[i][j],dp[i][h]+dp[h+1][j]);
			}
		}
		printf("%d\n",dp[0][n-1]);
	}
	return 0;
}

♔E 选做题2

♔Problem

马上假期就要结束了，zjm还有 n 个作业，完成某个作业需要一定的时间，而且每个作业有一个截止时间，若超过截止时间，一天就要扣一分。
zjm想知道如何安排做作业，使得扣的分数最少。
Tips: 如果开始做某个作业，就必须把这个作业做完了，才能做下一个作业。

♔Input

有多组测试数据。第一行一个整数表示测试数据的组数
第一行一个整数 n(1<=n<=15)
接下来n行，每行一个字符串(长度不超过100) S 表示任务的名称和两个整数 D 和 C，分别表示任务的截止时间和完成任务需要的天数。
这 n 个任务是按照字符串的字典序从小到大给出。

♔Output

每组测试数据，输出最少扣的分数，并输出完成作业的方案，如果有多个方案，输出字典序最小的一个。

♔Examples

♔Input

1
2
3
4
5
6
7
8
9
2
3
Computer 3 3
English 20 1
Math 3 2
3
Computer 3 3
English 6 3
Math 6 3

♔Output

1
2
3
4
5
6
7
8
2
Computer
Math
English
3
Computer
English
Math

♔解题思路

一道状压DP例题：

令 S 表示当前完成的作业集合，dp[S] 表示完成 S 作业集合后被扣的最少分数

则状态转移方程为：

  • dp[S∣(1<<x)]=dp[S]+作业x被扣的分数
  • 作业x被扣的分数=max(S作业集合对应的总时间+作业x完成所需时间−作业x的DDL，0）
  • 保证字典序最小：由于任务是按照字符串的字典序从小到大给出的，所以 S 从小到大枚举，即 x 从小到大枚举即可。

输出方案：对每个状态 S 记录 pre[S] 表示其对应的最后一个作业，回溯即可。

♔代码

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
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<queue>
#include<vector>
#include<utility>
using namespace std;
struct data
{
	char n[25];
	int ddl,w;
} hw[20];
int sum,tmp,dp[40005],pre[40005];
int n,T;

void makeout(int x)
{
	if(!x) return;
	makeout(x-(1<<(pre[x]-1)));
	printf("%s\n",hw[pre[x]].n);
}

int main()
{
	int i,j,k,h;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d",&n);
		memset(dp,0x3f,sizeof(dp));
		memset(pre,0,sizeof(pre));
		for(i=1; i<=n; i++) scanf(" %s%d%d",hw[i].n,&hw[i].ddl,&hw[i].w);
		dp[0]=0;
		for(i=0; i<(1<<n); i++)
		{
			sum=0;
			for(j=0; j<n; j++)
			{
				if(i&(1<<j)) sum+=hw[j+1].w;
			}
			for(j=0; j<n; j++)
			{
				tmp=max(sum+hw[j+1].w-hw[j+1].ddl,0);
				if(dp[i]+tmp<dp[i|(1<<j)])
				{
					dp[i|(1<<j)]=dp[i]+tmp;
					pre[i|(1<<j)]=j+1;
				}
			}
		}
		printf("%d\n",dp[(1<<n)-1]);
		makeout((1<<n)-1);
	}
	return 0;
}
坚持原创技术分享，您的支持将鼓励我继续创作！