题解

我并不觉得这次 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 的出题方式。