20160212湖大寒假训练赛3题解

这貌似也算是今年第一场比赛,搜索练习,能AK还是很开心的~~
先贴比赛地址代码地址
话说,这种代码多的题最能体现一个人编程基本功(wo zi ji xia bian de),所以我这种代码丑的人基本也就是。。。。。欢迎大神指正= =
不过搜索题真的是考验人对编程细节的处理。那样至少代码会写的漂亮点。

 

A - DZY Loves Chessboard

中等搜索练习题。
题目大意:大致是给你一个棋盘,有的是坏点,要求给出一个方案,使得每个点都涂上黑色或者白色,要求相邻两个格子不能颜色相同。
大致做法:遇到没有上色的就涂成白色,相邻的涂成黑色,然后递归搜索,把所有的相邻的都上色。直到整个棋盘都上色。由于题目保证了有解,所以不用担心这种做法是不是符合题意。
下面是代码。-1表示坏点,0表示未上色,1表示白,2表示黑。

 

B - Party

依赖树形结构的深搜题。
题目大意:告诉你所有人直系领导是谁,让你把所有人分组,要求一组里面不能有上下级关系。问最少要多少组。
大致做法:把领导关系按树存起来,深搜找出所有树中最深的度(就是这棵树有几层),就是答案。
存树我是使用前向星存树的,这是一种高效的存图方法。
下面是代码:

 

C - Fox And Two Dots

题目大意:找住由相同的颜色组成的环,要求环至少大于等于四个点。
大致做法:把A题代码改一改就好。搜索时记录联通块中的个数,如果搜索到已经去过的地方,那么就成环了,判断一下就好。注意,要记录父节点,不然可能会误判。
代码:

 

D - Valera and Antique Items

水题,扫一遍就行。。。结果我还看翻译看了半天,英语要人命啊!!

 

完结

发表评论

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