ACM 1008-1012

自用笔记

HDOJ-ACM 1008-1012解答及思路

1008

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

计算电梯的运行时间

参考AC代码

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
#include<stdio.h>
#include<iostream>
using namespace std;
int upp(int a,int b)
{
	int sum,diff;
	diff=b-a;
	sum=6*diff+5;
	return sum;
}
int down(int a,int b)
{
	int sum,diff;
	diff=a-b;
	sum=4*diff+5;
	return sum;
}
int main()
{
	int N,p[105]={0};
	while(cin>>N&&(N!=0))
	{
		int sum=0;
		for(int i=1;i<=N;i++)
			cin>>p[i];
		for(int i=0;i<N;i++)
		{
			if(p[i]<p[i+1])
				sum+=upp(p[i],p[i+1]);
			else
				sum+=down(p[i],p[i+1]);
		}
		cout<<sum<<endl;
	}
	return 0;
}

思路

把电梯上升和下降的情况分开考虑即可。

注意事项

电梯不是每一层都停，只有在起始和末尾位置才停5s。

1009

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

老鼠准备了M磅的猫食准备和N个房间的猫进行交换食物，N个房间中第i个房间存贮了J[i]磅的食物，需要F[i]磅的猫食才能交换，老鼠可以付出F[i]×a%磅的猫食即
可换回J[i]×a%磅的食物，求老鼠可以得到的最大食物量。

参考AC代码

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
#include<stdio.h>
#include<algorithm>
#include<iostream>
using namespace std;
struct Node
{
	double j,f,p;
}a[1001];
bool cmp(const Node a,const Node b)
{
	return a.p>b.p;
}
int main()
{
	int M,N;
	while(scanf("%d%d",&M,&N)!=EOF&&(M!=-1)&&(N!=-1))
	{
		double sum=0.0;
		for(int i=0;i<N;i++)
		{
			cin>>a[i].j>>a[i].f;
			a[i].p=a[i].j/a[i].f;
		}
		sort(a,a+N,cmp);
		for(int i=0;i<N;i++)
		{
			if(a[i].f<M)
			{
				sum+=a[i].j;
				M-=a[i].f;
			}
			else
			{
				sum+=a[i].p*M;
				break;
			}
		}
		printf("%.3lf\n",sum);
	}
	return 0;
}

思路

运用贪心算法，先算出每个房间可以换取javabeen的性价比用sort按照降序排列，从性价比最高的开始交换，全部交换完之后到性价比次之的房间，如果剩余的猫食
不足以全部满足该仓库的需要的猫食，则交换出全部的猫食换取javabeen后结束循环。

注意事项

该代码在G++中超时，在C++中即可AC。算出性价比按照降序排列后从高到低依次交换是本题的关键。

1010

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

输入一个矩阵，“.”代表可以通过，“S”表示起点，“D”表示终点，“X”表示墙，只能横着走或者竖着走，一个地方只可以走一次，问在t时刻能否恰好逃出去

参考AC代码

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
#include<stdio.h>
#include<iostream>
#include<math.h>
using namespace std;
char map[9][9];               //地图最多不超过7行7列,又从(1,1)计算,所以开辟9,9 
int M,N,T,di,dj;              //给定的三个量,以及终点位置  
bool escape;                  //标识逃生成功 
int Dir[4][2]={{0,-1},{0,1},{1,0},{-1,0}};       //分别表示左、右、下、上四个方向
void DFS(int si,int sj,int t)
{
	if(si==0||si>N||sj==0||sj>M)     //越出边界便不搜索  
		return;
	if(si==di&&sj==dj&&T==t)
	{
		escape=1;               //时间正好的时候才能逃生  
		return;
	}
	int temp=abs(T-t)-(abs(si-di)+abs(sj-dj));     //计算当前到终点的最短路与还需要的时间差,若小于0则路径剪枝 
	if(temp<0||temp%2==1)           //temp如果是奇数的话也要剪枝  
		return;
	for(int i=0;i<4;i++)
	{
		if(map[si+Dir[i][0]][sj+Dir[i][1]]!='X')
		{
			map[si+Dir[i][0]][sj+Dir[i][1]]='X';       //把当前点刷为X 
			DFS(si+Dir[i][0],sj+Dir[i][1],t+1);        //搜索该点   
			if(escape)
				return;
			 map[si+Dir[i][0]][sj+Dir[i][1]]='.';       //如果搜索不到退出来了,则重新把该点刷为'.'
		}	
	}
}
int main()
{
	int si,sj;
	while((cin>>N>>M>>T)&&!(N==0&&M==0&&T==0))
	{
		int wall=0;
		for(int i=1;i<=N;i++)
			for(int j=1;j<=M;j++)
			{	
				cin>>map[i][j];
				if(map[i][j]=='S')
				{
					si=i,sj=j;
				}
				if(map[i][j]=='D')
				{
					di=i,dj=j;
				}
				if(map[i][j]=='X')
					wall++;
			}
		if(N*M-wall<=T)                  //路径剪枝,当走完不含墙的迷宫都还不到T时间将不能逃生  
		{
			cout<<"NO"<<endl;
			continue;
		}
		escape=0;
		map[si][sj]='X';           //记得刷为'X'  
		DFS(si,sj,0);
		if(escape)
			cout<<"YES"<<endl; 
		else
			cout<<"NO"<<endl;
	}
	return 0;
}

思路

　　本题运用了深度搜索算法和剪枝算法。从（1，1）位置开始输入矩阵，记录下起点和终点的位置和墙的个数，如果走完所有没有的墙的位置后依旧小于时间T，那
么直接路径剪枝，把起点设为墙后进行深度搜素，如果越出边界那么不搜索结束函数，如果时间正好刚好的话escape返回值为1，再计算当前的最短路径如果小于需要
的时间差，那么路径剪枝，temp如果是奇数的话也要进行剪枝，草图如下




　　两种不同的走法，下面那一种可以控制时间刚好在T时刻。因为差出的是偶数，所以奇数的话要剪枝掉，省掉搜索时间。接下来进行该位置周围四个方向的前进，
如果不是墙的话进入循环，把当前点设为墙后搜索改点，如果成功后返回1，如果搜索不到退出来，那么重新把改点设为“.”。以此类推搜索完所有的点。

注意事项

　　由于是向四个方面前进，所以map的输入要从（1，1）开始，数组要设置为9行9列，确保搜索数组的时候不会越界。本题也多处运用了剪枝，大大减少了运算时间。
起点要注意在出发后要设置为“X”，在搜索每一个点的时候该点都要设为“X”，搜索结束后重新变回原样。输出的“YES”和“NO”均为大写，本人因为错把NO的O写成了数字
0导致检查了2个多小时，所以注意在书写代码的时候不要粗心。

1011

Problem Description

Input

Output

Sample Input

Sample Output

题目要求

一棵树，有n个结点，每个结点有v个bug，有w的brain。我从1号结点开始走，带着m个战士。1个战士可以消灭20个bugs，如果我把某个结点的所有bug都消灭了我就能
得到那个结点的brain。如果想攻击当前结点，那么必须先攻击了它的父结点（1号点除外）。其中当你攻占了当前结点，你可以分派人手，走向几个不同的子结点，
去攻占更多。也就是说，不是单一的路径。

参考AC代码

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
#include<iostream>
#include<cstring>
#include<vector>
#include<algorithm>
using namespace std;
int n,m;
int bug[105],brain[105];
int dp[105][105],vis[105];
vector<int>e[105];
void init()
{
	for(int i=0;i<=n;i++)
		e[i].clear();
	memset(dp,0,sizeof(dp));
	memset(vis,0,sizeof(vis));
}
void dfs(int root)
{
	vis[root]=1;
	int cost=(bug[root]+19)/20;   //上取整
	for(int i=cost;i<=m;i++)      //只要士兵数>=cost,所获宝藏是一样的，都是brain[root]
		dp[root][i]=brain[root];
	for(int i=0;i<e[root].size();i++)
	{
		int next=e[root][i];
		if(!vis[next])
		{
			dfs(next);
			for(int k=m;k>=cost;k--)    //派出去的士兵最多k-cost,因为至少要留下cost人在父节点
				for(int j=1;j<=k-cost;j++)
					dp[root][k]=max(dp[root][k],dp[root][k-j]+dp[next][j]);
		}
	}
}
int main()
{
	while(cin>>n>>m)
	{
		if(n==-1&&m==-1)
			break;
		init();
		for(int i=1;i<=n;i++)
			cin>>bug[i]>>brain[i];
		for(int i=1;i<=n-1;i++)
		{
			int a,b;
			cin>>a>>b;
			e[a].push_back(b);
			e[b].push_back(a);
		}
		if(m==0)
		{
			cout<<"0"<<endl;
			continue;
		}
		dfs(1);
		cout<<dp[1][m]<<endl;
	}
	return 0;
}

第二种dfs+dp写法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void dfs(int root)
{
	vis[root]=1;
	for(int i=0;i<e[root].size();i++)
	{
		int next=e[root][i];
		if(!vis[next])
		{
			dfs(next);
			for(int k=m;k>=1;k--)    //派出去的士兵最多k-cost,因为至少要留下cost人在父节点
				for(int j=1;j<=k;j++)
					ans[root][k]=max(ans[root][k],ans[root][k-j]+dp[next][j]);
		}
	}
	int t=(bug[root]+19)/20;
	for(int i=t;i<=m;i++)
		dp[root][i]=ans[root][i-t]+brain[root];
}

思路

树形dp问题，由于并未完全理解，所以未能提供思路，待更新。

注意事项

待更新。

1012

Problem Description

Output

Sample Output

题目要求

按照公式输出n为0-9所求出的e

参考AC代码

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
#include<stdio.h>
#include<iostream>
using namespace std;
int fun(int n)
{
	int sum=1;
	if(n==0)
		return 1;
	for(int i=1;i<=n;i++)
		sum*=i;
	return sum;
}
double fun2(int n)
{
	double e=0.0;
	for(int i=0;i<=n;i++)
		e+=1.0/fun(i);
	return e;
}
int main()
{
	cout<<"n e"<<endl<<"- -----------"<<endl;
	for(int i=0;i<=9;i++)
	{
		if(i<=1)
			printf("%d %.0lf\n",i,fun2(i));
		if(i==2)
			printf("%d %.1lf\n",i,fun2(i));
		if(i>2)
			printf("%d %.9lf\n",i,fun2(i));
	}
	return 0;
}

思路

按照题目要求写出函数即可。

注意事项

注意输出格式，如果对输出位数有苛刻的要求，请用printf输出而不要用iomanip中的setprecision。

本文标题:ACM 1008-1012

文章作者:Hippopmonkey

发布时间:2016-08-30, 19:55:27

最后更新:2017-01-17, 22:15:59

原始链接:http://xuboming8.github.io/2016/08/30/ACM-1008-1012/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. HDOJ-ACM 1008-1012解答及思路
    1. 1.1. 1008
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码
      3. 1.1.3. 思路
      4. 1.1.4. 注意事项
    2. 1.2. 1009
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
      4. 1.2.4. 注意事项
    3. 1.3. 1010
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
      3. 1.3.3. 思路
      4. 1.3.4. 注意事项
    4. 1.4. 1011
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 第二种dfs+dp写法
      4. 1.4.4. 思路
      5. 1.4.5. 注意事项
    5. 1.5. 1012
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
      4. 1.5.4. 注意事项
|