题解

我并不觉得这次NOIP的题目有多好。

再说我也不是都会做。

所以写个屁的题解。

感悟

国外的大牛们出题的套路:

Tom: 我想到了一个炒鸡有意思的题目呗。

Jerry:啥题目啥题目?说来听听?

Tom:就是这样,我给你一棵树,现在所有点都是白色的。你可以不停选择两个相邻且同色的点,将它们同时反色。你能不能将点全部变为黑色呢?如果能,那么最少几次你可以把所有点都变成黑色呢?

Jerry:有意思,我想想。嗯。。。我觉得可以这样,我们可以先考虑一下链的情况,你看,如果我有一条长度为偶数的白色的链,我可以把它的两端的颜色反色,而最终不改变内部颜色,而染色的代价就是链的长度。这样,我就可以将这个方法拓展到树上。将这棵树黑白染色,每次可以同时反转两个异色的点的原始颜色。现在,题目就变成了将树上的异色的点做最小权匹配。实际上,我们可以证明,这种匹配可以用贪心来做。现在我找到了一个复杂度为​的做法,不能再优化了。

Tom:哇你真是太聪明了,实际上我也是这么做的。

Jerry:而且我觉得我们可以把树的情况再拓展到基环树上,实现也不复杂,只需要分奇偶讨论一下。

Tom:是,我觉得可以。要不我们去问一下Spike,看看他是怎么做的?我们最好让大家用各种方法都可以通过。

国内大牛们出题的套路:

小九:你看你看,米国的Tom and Jerry出了一道题呗,我觉得好简单诶。

小十:是诶,你看我们能不能也出一道类似的,放到9102PION里?

小九:我觉得可以诶。这样,把他们那个做法放到仙人掌上。

小十:这样不够优秀,我们可以放到动态仙人掌上。

小九;对对对,我先去把题出出来。

两天后…

小九:我过对拍了诶!话说我们能不能再加点东西?要不外面再套个动态Dp?这东西可是最新科技呢,要不怎么体现PION的时效性。

小十:我觉得可以,我先把题做出来。

五天后…

小十:我也过对拍了诶!

小九:等等,还应该加个强制在线。而且我还可以把LCT上的常数减小一半,这样就可以卡掉那些非正解做法。

小十:对对对。

次年PION比赛…全场骂声一片。

我的感悟

这样一场比赛放到洛谷上都是会被爆破掉的,它竟然打着NOIP的名义光明正大地在全国范围内运行。

出原题的意义何在?让“基本功扎实”的选手多得点分?况且照搬的是不久之前的NOIP题目。

另外整场比赛难度分布异常不均匀。而且多数题目的难度仅仅在于“你是否做过”,以及“你是否打得出”,并没有太多思维难度。

反观世界范围内其他著名赛事,无不注重思维而次实现。如AtCoder上的常规赛,几乎没有一道题需要超过150行去实现,但是其思维难度却将这些比赛的水准拉高到了接近NOI的水平。又如POI的题目,同样罕见让人恐惧的码农题,但是POI的题目却一道道刷新着我对算法竞赛的认识,这些题目的分析过程,和对知识的灵活运用令人震撼(然而貌似这次NOIP就有POI原题)。

总之我不喜欢这次NOIP的出题方式。

分类: 文章

发表评论

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

你是机器人吗? =。= *