首页 > 其他题解 > 第二届顶嵌杯决赛解题报告与总结

第二届顶嵌杯决赛解题报告与总结

第二届顶嵌杯决赛已经结束,必须从中总结一些经验:

1.太过依赖于C++标准库

以前做题目时,只要能够用到C++标准库里面的地方,我都会用到,为什么?就是因为方便。这次B题BFS,结果悲剧到在队列这个数据结构上面卡了很久,囧。

2.忘了及时刷榜

一到手就看了A题,24点,很熟悉的题目。于是开始做。然而此时,B题已经很快有人过了。于是又转过去看B题,才发现是个原始的BFS。

3.对Linux还不够熟悉

在比赛之前,我特地进入了Ubuntu,打开Eclipse写代码,然而,对于调试,我还差的很远。以至于中间我有重启切换到Windows,浪费时间。

4.心态不好

这次比赛心态过于紧张,致使想问题时效率太低。

因为此次比赛题目简单,所以暂时只是发现了这些问题。接触ACM都快两年了,可以说我一直在划水,从来不研究!!!


A题:A题是一个24点游戏的问题。所谓24点就是说给你四个数,通过+-*/中的运输以及括号组合这些数字成为一个算式,这个表达式的值为24.因为只有4张牌,每张牌的值只有1-10十种值,可能的算术表达式有以下四种:

 

  • ((a ? b) ? c) ? d)
  • (a ? b) ? (c ? d)
  • a ? (b ? c) ? d
  • a ? (b ? (c ? d))

对于每一个?都可能是四则运算中的一种,所以,我们可以用一个3层的for循环来遍历。而对于(a ? b)这样的式子,用以函数来计算他的值就行了。另外还要注意避免做除法时除数为0,浮点数比较最好控制一下精度。


B题:B题是一个朴素而又原始的BFS,只是我以前基本都是用STL里面的queue在用,导致这次慌张了,手脚乱了,囧。


A题解题代码:(本人代码较乱,仅供参考)

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
78
79
80
81
82
83
84
#include <stdio.h>
#include <string.h>
#include <math.h>
 
#define EPS 1e-8
double data[4];
char cop[5] = {' ', '+', '-', '*', '/'};
char szres[64] = {0};
 
double calc(double x, double y, int n)
{
	//判断是否会除0
	if (y == 0 && n == 4)
		return 0;
	//判断
	switch (n)
	{
		case 1:
			return x + y;
			break;
		case 2:
			return x - y;
			break;
		case 3:
			return x * y;
			break;
		case 4:
			return x / y;
			break;
		default:
			break;
	}
	return -1.0;
}
 
void work()
{
	int i, j, k;
	for (i = 1; i <= 4; ++i)
	{
		for (j = 1; j <= 4; ++j)
		{
			for (k = 1; k <= 4; ++k)
			{
				if(fabs(calc(calc(calc(data[0], data[1], i), data[2], j), data[3], k) - 24.0) < EPS)
				{
					sprintf(szres, "((%.0f%c%.0f)%c%.0f)%c%.0f\n", data[0], cop[i], data[1], cop[j], data[2], cop[k], data[3]);
					return ;
				}
				if (fabs(calc(data[0], calc(calc(data[1], data[2], i), data[3], j), k) - 24.0) < EPS)
				{
					sprintf(szres, "%.0f%c((%.0f%c%.0f)%c%.0f)\n", data[0], cop[k], data[1], cop[i], data[2], cop[j], data[3]);
					return ;
				}
				if (fabs(calc(calc(data[0], data[1], i), calc(data[2], data[3], j), k) - 24.0) < EPS)
				{
					sprintf(szres, "(%.0f%c%.0f)%c(%.0f%c%.0f)\n", data[0], cop[i], data[1], cop[k], data[2], cop[j], data[3]);
					return ;
				}
				if (fabs(calc(data[0], calc(data[1], calc(data[2], data[3], i), j), k) - 24.0) < EPS)
				{
					sprintf(szres, "%.0f%c(%.0f%c(%.0f%c%.0f))\n", data[0], cop[k], data[1], cop[j], data[2], cop[i], data[3]);
					return ;
				}
			}/*End For k*/
		}/*End For j*/
	}/*End For i*/
}
 
void szprint()
{
	printf("%s", szres);
}
 
int main()
{
	int i;
	for(i = 0; i < 4; ++i)
		scanf("%lf", &data[i]);
	work();
	szprint();
 
	return 0;
}

B题解题代码:(同样仅供参考)

 

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
78
79
80
81
82
83
84
85
#include <stdio.h>
#include <string.h>
 
int maze[5][5];
int n = 5;
int step[4][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
 
typedef struct TagNode
{
	int x;
	int y;
	int xp[20];
	int yp[20];
	int idx;
}Node;
 
int checkok(Node n)
{
	if(n.x >= 0 && n.x < 5 && n.y >= 0 && n.y < 5)
	{
		return 1;
	}
	return 0;
}
 
int flag[5][5] = {0};
Node q[10000];
 
void BFS()
{
	int i, j, idx = 0, len = 0;
	Node start, tmp, t;
 
	start.idx = start.x = start.y = 0;
	memset(q, 0, sizeof(q));
	memset(flag, 0, sizeof(flag));
	flag[0][0] = 1;
	start.xp[0] = start.yp[0] = 0;
	start.idx = 0;
	idx = 0;
	q[len++] = start;
	while(idx < len)
	{
		t = q[idx];
		++idx;
		for(i = 0; i < 4; ++i)
		{
			tmp = t;
			tmp.x += step[i][0];
			tmp.y += step[i][1];
			if(checkok(tmp) && maze[tmp.x][tmp.y]==0 && flag[tmp.x][tmp.y]==0)
			{
				tmp.idx++;
				tmp.xp[tmp.idx] = tmp.x;
				tmp.yp[tmp.idx] = tmp.y;
				q[len++] = tmp;
				flag[tmp.x][tmp.y] = 1;
				if(tmp.x == 4 && tmp.y == 4)
				{
					for(j = 0; j <= tmp.idx; ++j)
					{
						printf("(%d, %d)\n", tmp.xp[j], tmp.yp[j]);
					}
					return ;
				}
			}
		}
	}
}
 
int main(int argc, char **argv)
{
	int i, j;
	for(i = 0; i < n; ++i)
	{
		for(j = 0; j < n; ++j)
		{
			scanf("%d", &maze[i][j]);
		}
	}
 
	BFS();
 
	return 0;
}

最后,感谢大家的围观:)


觉得文章还不错?点击此处对作者进行打赏!


本文地址: 程序人生 >> 第二届顶嵌杯决赛解题报告与总结
作者:代码疯子(Wins0n) 本站内容如无声明均属原创,转载请保留作者信息与原文链接,谢谢!


更多



分类: 其他题解 标签: , , , , ,
  1. 2010年12月4日20:21 | #1

    引用自文章:因为只有4张牌,每张牌的值只有1-10十种值,可能的算术表达式有以下四种:
    问题:为什么只有4种啊?这四种是怎么得出来的?有技巧不?

    [回复]

  2. 2010年12月4日21:35 | #2

    @翔久博客 这里不是说真的只有四种,我应该说可以分成四类。显然,对于只有四张牌且已经排号顺序的情况下是只有下面四类组合的,而?则代表+-*/四则运算中的一种。
    ((a ? b) ? c) ? d)
    (a ? b) ? (c ? d)
    a ? (b ? c) ? d
    a ? (b ? (c ? d))
    因此,总共有4*4*4*4中情况。

    [回复]

  3. 2010年12月5日01:51 | #3

    呵呵,很不错嘛,继续加油。

    [回复]

  4. 2010年12月5日21:58 | #4

    @the5fire 呵呵 我很菜的

    [回复]

  5. 2010年12月8日14:47 | #5

    牛~疯子加油~!

    [回复]

  6. tujfj
    2010年12月24日21:52 | #6

    @怪蜀黍
    还有一种情况你忽略了,总共5总情况
    1 (((a b) c) d)
    2 ( (a b) (c d))
    3 ( (a (b c)) d)
    4 (a ((b c) d))
    5 ( a (b (c d)))

    按你上面的程序输入 7 5 2 3 就不行
    7*(5-2)+3=24

    [回复]

  7. 2010年12月24日22:20 | #7

    @tujfj
    哈哈 把这个忘了 看来测试数据也弱了点

    [回复]

  8. Kid
    2011年1月1日11:08 | #8

    A题思路跟你不太一样,因为我在语言上偏向C,所以语言上没什么问题,但是很遗憾的A题没有通过,小小的悲剧一下

    [回复]

  9. 2011年1月1日11:33 | #9

    @Kid
    A题主要是以前比赛见到过,看过别人的解题代码。

    [回复]