AC. 梦想

frank_c1

51Nod Marathon 20

发布于2016年11月26日 | 暂无评论 | 571阅读 | 比赛经历

对51Nod的敬仰是由来已久的。一是这个平台建设的氛围很不错,二就是这个平台上有许多可怕的数学题。当然,“集训队爷赚钱平台”这个称号也让人望而生畏TAT

趁着还没有彻底滚回去上课的时候,再来做一场马拉松,希望能发挥出自己的水平。以前做马拉松的时候,基本上就止步于D题,觉得后面的题都是不可做题。而且大家AK的速度太快了,根本抢不到钱TAT 这次决心要改变一下。

晚上八点,准时开题。先看A,看起来清真的样子,可是我怎么不会?先看B,发现推推式子就行了,暴推一波搞了过去。发现A已经被A穿了,咦,好迷啊…… 想来想去,AwD大爷一句容斥惊醒梦中人。切了A后去看C,发现n,m好大,肯定不难。由于惯性先暴推了一波式子,结果推来推去出不来。于是弃疗开始打表,然后就找出了规律…… 原来就是等比数列求和啊。写了一行然后惨挂精度,写了矩乘结果没开long double又挂精度,终于前前后后卡了1h精度A了。

看D,好难啊,不会。看E,咦这不是线性基吗我会3个log!惨遭TLE…… 发现线性基合并是个瓶颈,该怎么办呢?自己还是Naive啊。百度一波线性基合并,发现有SCOI2016原题,不过是在树上,好像有个很妙的点分做法。妙啊妙啊那我直接搬序列上不就好了。写完了又惨遭TLE…… 原来出题人卡常数啊。于是卡常数卡到深夜,终于在凌晨A了,好气啊。

早上爬起来接着刚。D不会怎么办呢,让我乱搞一波吧。嗯,我不如DP的时候最多向上爬1500个点,看看多少分吧。啊,怎么A掉了…… 完全没有准备TAT 于是还剩一道F辣。咦,这个式子好眼熟啊,似乎哪里看到过。哎如果K=R那不就是国王奇遇记吗?国王奇遇记不是有O(m)做法吗?那这个模数是来负责娱乐的吗?发现如果要知道K \neq R的情况,就必须把整道题弄懂,好难啊嘤嘤嘤。于是把线性插值法看了一遍又一遍,终于基本上弄懂了。发现那不是只要式子中的一些变量改改就好了吗,再特判一下R = 1的情况。嗯,交上去果然很稳。哇,那不是六道题都做完了吗,好开心呀。发现排名是7,耶居然拿钱啦。Excited!所以冷静下来还是写写题解吧。有些题目还确实蛮涨姿势的。

A. treecnt

考虑一条边对答案的贡献。什么时候边要加入答案呢?一定是在边的两端都有点的时候。所以只要在对每条边统计时,用全集减去选择的k个点都在一边的情况即可。时间复杂度O(n)

B. 区间求和

f(L, R) = \sum_{i=L} ^ {R} \sum_{j=L} ^ {i} {a_i - a_j}

方便起见,设s_ia_i的前缀和。易得

\begin{aligned} f(L, R) & = \sum_{i=L} ^ {R} {(i - L + 1) a_i - s_i + s_{L-1}} \\ & = -(L-1)(s_R - s_{L-1}) + (R - L + 1) s_{L-1} + \sum_{i=L} ^ {R} {ia_i - s_i} \\ & = R s_{L-1} - (L-1) s_R + \sum_{i=L} ^ {R} {ia_i - s_i} \end{aligned}

于是我们只要预处理数列ia_i - s_i的前缀和就十分容易计算答案了。时间复杂度O(n)

C. 战忽局的手段

通过打表的手段,容易发现答案

F(n,m) = \sum_{i=0} ^ {m-1} {(1 - \frac{1} {n}) ^ i}

如果数学上就是一个等比数列求和,但是我们发现计算机计算时容易发生精度误差……

于是我们可以采用精度误差较小的矩阵快速幂计算,因为这样就不涉及除法了。需要开long double。

时间复杂度O(\log m)

D. 跑得比谁都快

有一个O(n ^ 2)暴力

f(i) = a[i] + \min{\{ f[j] + (i - j) ^ p | j \in ancestor(i) \}}

我们不妨猜想对于i的有效的转移不会太多,于是我们可以求i时至多往上找1500个点转移,居然能A。

至今不知道正解系列QAQ

E. 异或凑数

有一个Naive的想法是用线段树 / 树状数组 / ST表等数据结构维护线性基,对于一次询问,区间查询O(\log n),合并线性基单次O(\log ^ 2 {V}),总复杂度O(q \log n \log ^ 2 {V})。非常自然地TLE啦。

考虑对序列分治。设当前分治区间为[l,r],中点为mid,则我们预处理两边到mid的前缀线性基,这一部分算上分治的话总复杂度是O(n \log n \log V)。接着我们处理所有经过mid的询问,可以发现,处理一个询问仅需要合并一次线性基即可,这一部分总复杂度O(q \log ^ 2 {V})。其余的询问就下传递归解决。

所以总复杂度就是O(n \log n \log V + q \log ^ 2 {V})啦,需要许多常数优化才能通过。

F. 序列求和 V5

[UPD 03. 08] 怎么有个坑 填一下。

听说有一道题叫做国王奇遇记。有O(k ^ 3 \log n)的,O(k ^ 2)的,O(k)的三种算法。

前面两个是没有什么前途的。于是翻到杜教2013WC的课件学习了一波。最后好像要加个特判,复杂度应该是线性的。