优势在我学说详解（复杂度分析 wcnm）

noip 210，期望是冲进三倍队线。

CQ-0139

Day ?

激情押题。

开学。晚会最后一项合唱《我的未来不是梦》。

咋给我唱哭了，我是不是也不太配哭。

充分的准备是作战的关键。

坐轻轨的时候遇见了 lrd。进场前大龙猫和我们说省选换评测系统了，可能有通信。

进场后花了一个小时大概会了 T1，是一个背包状物。但是要求一个卷积逆。

这个卷积逆昨天才在学自己卷积逆的时候学到，这不是直接爽飞了？

又花了 1h 写完了发现大样例跑 64s。发现统计答案的时候枚举了很多 0 导致复杂度是 O(n^3)。改了一下上下界变成 4s。

到这里就不会了啊，我发现计算卷积逆（f=\frac hg）是 O(n(n+m)) 的，n 是 f 的长度，m 是 g 的长度。这就导致我会被构造的数据卡到 O(n^3)。

到这里已经有 2~3h 了。紧急写 T2T3 暴力。写完后想了一会，想到 1:20 的时候突然发现卷积求逆是不必要的，直接左右两边背包拼起来就好。在剩下 3min 的时候改完并测完大样例，跑了 0.6s。

出场的时候感觉自己快得心脏病了，但是其实让我得心脏病的另有其事。

相信有水平的选手都已经发现我 T1 爆炸了。卷积求逆的复杂度其实是 O(nm) 而非 O(n(n+m))。而前后缀背包拼起来又会被菊花轻易卡到 O(n^3)。所以我 T1 不一定有 64。

听到的时候还不敢相信，和同学争论了好一会才相信这个事实。自己的梦被自己深度思考 0s 送掉了，哈哈。

晚上睡觉做梦梦到卷积求逆了。是真的。希望 day2 的通信能救我一命。

优势在我学说注重投入信心而非能力达成目标。

开题。交互传统传统。

这个交互不是唐，随便做啊，那翻盘是不是没啥希望了。写完大概 30min 左右。

然后就在尝试手玩三元环性质和尝试理解 T3 题面中横跳。大概在 2.5h 后 T2 颗粒无收而 T3 大概会了 o_x=o_y=0。发现拼上菊花和 r=1 有 44。day 2 有 144 感觉不少了，于是直接开写。

写到一半发现这个排名怎么这么邪恶，竟然是从大到小。不过这也方便我写 r=1 了。花了一点时间写完了这 8 分然后就开始写剩下 36 分了。

还有两个小时，优势在我啊！

剩下 0.5h 的时候写完并且过了小样例。

还剩半个小时，优势在我啊！

剩下 5min 的时候还没调出来。

还剩 5min，优势在我啊！

宣布加时 15min。

还剩 20min，优势在我啊！

最后剩 5min 的时候过了。原因是根据题意模拟挂了。

总之优势在我！

最后估分是 64+30+12+100+0+44=246。看样子没有三倍队线。CQ 标准分计算是把省选两天合在一起计算的，所以 day1 崩盘了就真的爆炸了。

那我能干什么呢？我问我自己。

押题命中率高达 60%，我太牛了。

recollect=recall。

回家抽卡，80 抽出刻律。没歪不错。

无论如何，优势在我。

我是不是只会念这一句话尝试挽回我那本不应该存在的信心/cf

我和我爸说了下分数，然后我爸意识到我好像和 250 有什么缘分。

什么能我说。