智障NiroBC的NOIP2016奇遇记"/>
智障NiroBC的NOIP2016奇遇记
Day 0.
原以为NOIP是一件轻松的事情，可惜事与愿违。
考试前一天很热，大巴车上大汗淋漓，我早就忘了这是冬天。
四小时到衢州。
衢州二中校园绿化很好，食堂大妈普通话很标准，哪像敝校的大妈，一口乡音呼唤我去打饭。然而我倒是觉得大妈讲普通话反而没有亲切感。
食堂发的那个苹果，我啃不下（这口破牙），然而还是强行啃了一些。
晚上。我在宾馆一个人住一间，虽然房间里有两张床。
沉迷全民K歌无法自拔，虽然墙壁隔音不好，我很扰民，在此向所有住在帝京大酒店的浙江OIer道歉。
放心，我唱的歌是不会发布的，因为我有羞耻心（哼！
然后就洗洗睡了，辣鸡宾馆没有吹风机，头发湿湿的，我到十一点半才睡，就是为了等该死的头发干啊喂。。
Day 1.
早饭没吃液体，怕上厕所（雾
今天的题很简单的样子。T1太笨了，Codeforces的每场A题也没见过这么无聊的。就用了一分钟。
T2，这道题看起来在哪见过，却又不知道在哪。直觉就会做了，详见后附题解。
T3，为什么比T2简单呢。看见期望两个字还以为多难，一定是出题人灵感枯竭，出不出题才放了这种题！
不出意外应该AK了吧。
回到宾馆后，下午看完了《垫底辣妹》。明明是一部励志片，在我眼里竟然成了致郁的。因为我再也无法实现人生的价值了（笑。
单人住，虽然没有什么麻烦，却很无聊。整个下午到晚上都很沉闷，想找人说话，想吼叫，想化身成独特的露珠。
外面开始下雨了，很大很大。
Day 2.
T1(似乎)是简单题。
T2，一开始只会写用堆模拟的 O((N+M)log(N+M)) 的做法，因此在草稿纸上写下了恶毒的语言咒骂该死的出题人（大雾），便去做T3.
T3是很蠢的状压DP，随手做完，又回来看T2。想到最大的瓶颈是堆操作中的 O(log(size)) 的复杂度，能否去掉log，便想到了链表。
写完之后，把检查的重点放在了T2和T3，酿成悲剧。
考完以为自己600了很开心，午饭都没吃便上车了。
车上开始写题解，写着写着发现Day2T1出事故了，我想当然以为K是质数，原地爆炸。
每个点5分。嗯。我记得20个点的K分别是2,3,4,…,21，其中有8个质数。。嗯。。应该还有40分。
那就540吧，希望540不要出事故了。比去年低。好难受。我的人生不过如此吧（笑。
上帝保佑。
结果Day2T3又出事故了。。
加上一些奇奇怪怪的感想吧：
我又见识到了什么叫青春，那是面对码农题时一鼓作气埋头码的勇气。曾经年轻的时候我没有这般勇气，现在垂暮之年又找回一些了。
六题码长分别为0.4K 3.3K 1.?K 0.6K 1.9K 1.?K
挺短的吧。为什么我会挂在Day2T1。上帝开我一个玩笑还不够吗为什么要两个。
其实后一个根本不是上帝的玩笑，纯粹自己作死。
如果有下一次NOIP的机会，我一定要真正的600，一定要！一定要！
后来啊，发现Day2T3的状压DP也挂了，照我的写法，每只猪只能被经过一次。这样这题只有N<=3的数据可过，剩下的由于多组数据，总有能弄死我的。一分都拿不到的。
诶，突然想起抛物线集合多组数据忘清空，这下是真没分了。
100+100+100+40+100+20=440
一等应该有。省选不用想了呵呵，不可能进了。
可现在来看AK只是空谈。我永远做不到的。
哈哈哈哈哈哈，来一串谜一样的哈。
我只剩一次青春可以挥霍了（吧）。
现在正在大巴上写下这游记，回去有网络后加上了markdown格式再发了上来。
附题解：
Day1:
T1:toy
太水了！直接模拟。
T2:running
对于一条路径 (u,v) ，以LCA为界分成两段
前面一段，深度每减小1，时间加1，即 W+dep 是常数
后面一段，深度每增加1，时间加1，即 W−dep 是常数
能够统计到这条路径的观测点i需要满足：
若在前面一段，需要满足 W[i]+dep[i]==dep[u]
若在后面一段，需要满足 W[i]−dep[i]==dep[u]−2∗dep[LCA]
前一段和后一段完全独立统计。
把“链修改，点询问”问题转化成“点修改，子树询问”问题。
每个点上长着若干个 dep[u] 或 dep[u]−2∗dep[LCA] ，我们询问一个子树中共长着几个 W[i]+dep[i] (对于前面一段对答案的贡献)，或是长着几个 W[i]−dep[i] (对于后面一段对答案的贡献)。
T3:classroom
先一个 O(V3) 的 Floyd
更多推荐
智障NiroBC的NOIP2016奇遇记
发布评论