《Bin Code》解题报告

大榕树 \ 信息学奥赛 \ 解题报告

《Bin Code》解题报告

原文链接：http://www.mydrs.org/program/list.asp?id=196
一、算法分析：
　　题目给出方阵末列的字串，根据题意可以知道：将末列按照从0到1进行排序，即可得到方阵首列的字串。又因为所有的字串都是由0和1组成，所以排序的过程可以简略为统计0和1的数量即可。对于样例，该过程之后，首列和末列的字串如下所示：
首列 0 0 0 1 1
末列 1 0 0 1 0
　　然而此时末列和首列各个字符之间的对应关系仍就难以很直观的体现。字符之间的先后顺序难以确定。
　　那么就让我们换一种思路，将每个字符所对应位置替换上表所示的字符，我们得到下表：
首列 2 3 5 1 4
末列 1 2 3 4 5
　　这样，末列与首列的对应关系便清晰可见了。按照上表所示的顺序，可以将方阵的第一行的字符位置串接起来：1--〉4--〉5--〉3--〉2，再将每个位置换成所对应的字符，即得到第一行的字串。
　　关于无解的数据，只需要统计所得字串中0和1的数量是否与给定字串的相同即可。
二、小结
　　对于此类没有现成算法可以套用的题目，而搜索算法又明显低效时，对于选手的思维能力和基本功都是一个很好的锻炼。只有在扎实的基础之上，才会有这种"灵光一闪"的灵感，可谓是："山穷水复疑无路，柳暗花明又一村。"

作者：许靖凡
来源：福州三中
时间：2001-08-28

上一篇：《迷宫问题》解题报告
下一篇：《彩灯布置》解题报告