第二届河南省大学生程序设计竞赛题型简要分析

时间限制: 每题运行时间不超过1000MS

概览：

题数	类型
1	最短路径（广度优先搜索）
2	模拟
3	树形DP；数学推导
4	数论（置换群）
5	关键路径
6	数论（进制转换）
7	二叉排序树（递归）
8	记忆化搜索

【试题一】

Dr.Kong的机器人

练习处：

类型：最短路径（广度优先搜索）

解法：

1、BFS，从A到B求最短路径（每条边的权值为1），可以采用Dijkstra算法（需要遍历计算的节点相当多，效率较低），利用BFS，构造队列，从A遍历到B的步数即最优解。

2、其实，求最短路径的方法有很多：Dijkstra算法、A*算法、SPFA算法、Bellman-Ford算法和Floyd-Warshall算法，各有各的优势，选择一个合适的就行。

【试题二】

奇特的艺术品

练习处：

类型：模拟

解法：可以使用链表结构，在Java中可以利用Vector来模拟操作这些构件（保存编号、所在层数等信息），完成所有搬动后，取出顶层的编号。

【试题三】

瓷器物流规划

练习处：http://www.cqoi.net/JudgeOnline/problem.php?id=1352

http://www.rqnoj.cn/Problem_339.html

类型：树形DP；数学推导

解法：http://www.rqnoj.cn/Discuss_Show.asp?DID=8775

【试题四】

壮观的瓷器广场

练习处：

类型：数论（置换群）

解法：此题类似于“篝火晚会”，只是需要排序得到元素有序序列，而且是直线型的，剩下的工作就是对比原序列与有序序列，利用置换群找出交换难度小（交换对象的值*交换次数）的方案。

置换群http://poj.org/showmessage?message_id=153818

http://blog.csdn.net/foreverlin1204/article/details/6646847

类似于http://poj.org/showmessage?message_id=161819

【试题五】

瓷器工艺

练习处：

类型：关键路径

解法：

参考 http://blog.csdn.net/kay_sprint/article/details/6696701

http://zhidao.baidu.com/question/151997718.html?fr=qrl&cid=93&index=4

【试题六】

FaultyOdometer

练习处：http://poj.org/problem?id=2719

http://acm.tju.edu.cn/toj/showp1987.html

类型：数论（进制转换）

题意：有一种很奇怪的计数法，它的数里面没有4，现在用这种计数法给定一个数字，把它换算成通用的十进制。

解法：很明显的九进制，只是不是真正的9进制，0~9缺少4，那么可以对每一位数字做处理，大于4的减1，使得每一位数字0~8，构造成9进制的数，在转换为十进制的数字输出即可。

【试题七】

The Number of the Same BST

练习处：http://poj.org/problem?id=2775

类型：二叉排序树（递归）

题意：给一个序列构成二叉排序树，求与该序列构成的二叉排序树相同的序列的个数num。输出num%9901。

解法：很容易推出递推公式：f[x]=f[l[x]]*f[r[x]]*combination(s[x]-1,s[l[x]]),问题的关键不在递归，而在算combination.即两个大数的商对9901的模。这需要用到乘法逆元，也是刚刚学会的：

若有b*x% M =1 ,则有 a/b % M = a/b * (b*x) %M=a*x % M. x称为b的乘法逆元。

参见http://blog.sina.com.cn/s/blog_4e01eb1d0100h3wp.html

http://blog.chinaunix.net/uid-20656730-id-1588813.html

【试题八】

DNA Evolution

练习处：http://poj.org/problem?id=3633

类型：记忆化搜索

题意：给你两个字符串S和T，要求你用尽量少的步数从S构造出T。每一步你可以做以下操作：从S或者T的片段中拷贝一个字符串，然后可以将这个字符串反向，然后你得到一个片段。片段可以随时合并，但不能拆分，并且所有的片段都要使用。从T中拷贝字符串只能从一个片段中拷贝。求你最少需要的步数。两个串的字符数≤18。

解法：强烈推荐，这是某某见过的最牛的搜索题之一！

这个题基本上除了搜索没有别的办法……那么我们就往搜索方面想想看。

首先，如何表示状态。如果把所有现在有的片段存下来，那就成脑残了。注意到片段必须对应到T中，并且合并两个可以合并的片段没有任何损失。所以，干脆用一个二进制数表示T串的“组装”情况。某一位上是1表示这个字符已经装好了，0反之。

状态数只有2^18=262144，所以说BFS和DFS均可。现在让我们来考虑状态转移。

首先，只有没有组装好的地方才有必要进行组装。那么，我们就考虑组装状态中为0的字符。当然，我们可以枚举起始点和终点然后去S和T中连续为1的段中匹配，但是这也太朴素了。说到字符串匹配，最爽的方法自然是KMP。我们只需要枚举起始点，然后在S和{S的反串，T'和T'的反串}中用KMP匹配就行了。T'表示在当前状态下可以匹配的T，如果某一位是1，那么T'和T的这一位相同，否则T'的这一位是'$'（或者其他S和T中都没有的特殊字符）。

可以这样状态转移的成本依然巨大，高达O(N^2)，N是字符串长度。思考之后会发现，组装两段[a, b]和[c, d]的情况，如果[c, d]是[a, b]的字串，那么组装[c, d]毫无意义。因为如果一段可以被组装，那么这一段的任何字串都可以任意组装，组装[a, b]并不会“挡住”什么。所以说，每次枚举一个起始点，我们只组装到最远点。并且记录这个最远点，在推进起始点之后判断这次的最远点是否远于刚才的最远点，如果不远，那就不扩展这个状态。

但是这样依然属于暴力方法，之后就是搜索策略的选择。如果走到了启发式搜索的路子上，那就是A*；如果发现了状态数有限，从而可以记录的特点，那就是记忆化搜索。A*见下一篇文章，这里先说记忆化搜索。

观察发现，这个题有很多重复的子问题，对于这样的搜索，用记忆化搜索的效果是非常好的，一下子把我从好几分钟的边缘拉到了100MS以内。并且只需要记录一个数组就行了，编程复杂度很低。http://hi.baidu.com/billdu/blog/item/4a1f89eeca0eb4fbce1b3e88.html

赛题见：http://download.csdn.net/download/wujun8/4218470