Zplhz_智破连环阵

NOI 2003 全国信息学奥林匹克竞赛试题 解题报告——Day2——Problem3——智破连环阵（Zplhz）

南京市外国语学校 朱泽园

Zplhz.cpp 程序结果 测试点 我的程序①C++ 我的程序②C++ 我的程序得分 标程一①C++ 标程一得分 标程二①C++ 标程二得分 测试点 我的程序①C++ 我的程序②C++ 我的程序得分 标程一①C++ 标程一得分 标程二①C++ 标程二得分 时限：

6sec

1 0.0000s 0.00s 10 0.0000s 10 0.0000s 10 6 0.0000s 0.00s 10 0.0549s 10 0.0000s 7 2 0.0000s 0.00s 10 0.0000s 10 0.0000s 10 7 0.0000s 0.00s 10 0.0549s 10 0.0000s 10 3 0.0000s 0.00s 10 0.0549s 10 0.0000s 9 8 0.0000s 0.00s 11 6.5934s 5 0.0000s 9 4 0.0000s 0.00s 10 0.0000s 10 0.0000s 9 9 0.0000s 0.00s 10 TLE TLE 0.0000s 9 5 0.0000s 0.00s 10 0.0000s 5 0.0000s 8 10 2.2527s 1.06s 10 8.4615 5 TLE TLE 这里我的程序是MIDDLE_NODE_COUNT取8，LARGE_NODE_COUNT取2的程序，如果MIDDLE_NODE_COUNT取7，第10个测试点只需要约0.5sec即可。

标程一是刘汝佳的IDA*程序，其中卡结点数为2000。标程二是侯启明的深

9

NOI 2003 全国信息学奥林匹克竞赛试题 解题报告——Day2——Problem3——智破连环阵（Zplhz）

南京市外国语学校 朱泽园

度优先A*搜索程序。声明：这两个程序不代表就是刘汝佳和侯启明的最终版本，原著是他们，是出自多时多手多地的一个中间版本。

TLE的点我等了1min也没有出结果就Ctrl+C了，这些比较说明我的这种近似算法单对这一道题来说是非常成功的。

测试环境与标准环境详见附录。 [总结]

在上海我没有想到IDA*搜索，使用了直接深度优先加上后面提到的冒险优化，可能是因为时间的关系，我也没有想到对“次优局部状态”的数量进行限制。我最后的得分是63分，其中大部分（7个点）的分数都在8分以上，3个点超时。超时是很不应该的，因为只要输出一个较优解，一般来说都能稳拿至少5分，这是我最大的失误所在！

我对NP问题的接触不多，各大ACM在线评测的网站上，也很少出现这样的题目，因为他们无法进行评测。不过离开上海以后我想到的这种冒险优化，还是很有代表性的，应该也可以称得上是NP问题的克星。我觉得在今后的训练道路上，一方面我要尽可能多接触NP问题，另一方面要让自己的思维和不理想的结果碰撞，产生火花！ [附录]

测试环境与标准环境 测试环境①

编译器 Djgpp3.2.1 + Rhide 1.4.9

-Wno-deprecated -O6 -march=pentium3 -ffast-math -fomit-frame-pointer

Freepascal 1.0.6 -Op3 机型Intel Celeron processor 735 + 128MB RAM

平台Windows XP Professional 2002（5.1.2600）+ Dos for XP

10

NOI 2003 全国信息学奥林匹克竞赛试题 解题报告——Day2——Problem3——智破连环阵（Zplhz）

南京市外国语学校 朱泽园

测试环境②

编译器 Djgpp2.953 + Rhide 1.4.7

-pipe -O6 -march=pentium3 -ffast-math -fomit-frame-pointer Freepascal 1.0.6 -Op3 机型Intel Celeron processor 735 + 128MB RAM 平台Debian Linux 3.0r0 stable + KDE3.1r0

标准环境

编译器 Djgpp2.953 + Rhide1.4.9

Freepascal 1.0.4

机型Inter Pentium 1.4GHz 平台Debian Linux 3.0

11