NOIP2005-篝火晚会(fire)解题心得

最近做了一下NOIP2005篝火晚会(fire),刚刚对这道题的时候也感觉到了一些无厘头。后来阅读了一下某解题报告,说是用什么冒泡排序就能出来,结果就只能过样例,最后我发现他连题都理解错了,估计写的时候只测了样例。在此,偷偷的对这种行为表示强烈的谴责

在被祸害了很久以后,我终于明白了,具体解法可以看看官方的说明,结果最后程序出来只有第八个点不过,在看了这位的解题报告里的程序以后,终于惊喜地发现,构建目标状态需要从两边构造,也就是说我从左边开始构造一边、还要从右边开始构造一边,因为这是一个环,而我们断开以后其相对信息只有起始点能够等价,其他的左右关系是不可以的,所以要两遍。

希望大家多多吸取教训,不过目前还不知道如何证明其需要调整的点数就是最终的代价,也就是说我们如何证明每个点最多调整一次?


Posted

in

by

Tags:

Comments

2 responses to “NOIP2005-篝火晚会(fire)解题心得”

  1. George J. SUN Avatar
    引自 maxiem

    这道题让我很囧。
    那个冒泡的解题报告也让我无厘头了半天……

    那个报告的方法只能过样例。

  2. maxiem Avatar
    maxiem

    这道题让我很囧。
    那个冒泡的解题报告也让我无厘头了半天……

Leave a Reply to George J. SUN Cancel reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.