又一次RP爆发卡线rank 10……有点爽……

由于周五是我出的校内训练，所以等21:30讲完题回家路上才开始看题。

路上用手机看题。A题看完以后想到FJOI2016一试T3，其实就是Codechef原题FRBSUM。看起来很复杂，其实注意到一个核心性质：把 $S$ 中的元素排序得到 $a_1\le a_2\le\cdots\le a_n$ 以后，最小的满足 $a_i > 1+\sum_{j=1}^{i-1}a_j$ 的 $i$ 对应的 $\sum_{j=1}^{i-1}a_j$ 就是 $S$ 的优美值。

因为当 $0 < i' < i$ 时，如果 $\{a_1,\cdots,a_{i'-1}\}$ 能配出的数为 $[0,\sum_{j=1}^{i'-1}a_j]$，那么 $\{a_1,\cdots,a_{i'}\}$ 就能配出 $[0,\sum_{j=1}^{i'-1}a_j]\cup[a_{i'},\sum_{j=1}^{i'}a_j]=[0,\sum_{j=1}^{i'}a_j]$。而由于 $a_i$ 已排序，所以 $a_{i'} > 1+\sum_{j=1}^{i-1}(i'\ge i)$，因此 $1+\sum_{j=1}^{i-1}$ 配不出来。这样求优美值就很简单了：排序以后，一开始 $\mathrm{sum}=0$，从小到大把 $a_i$ 加入 $\mathrm{sum}$，一旦加入前发现 $a_i\not\in[0,1+\mathrm{sum}]$ 就得到答案了。（FJOI原题是多次询问区间答案，做法是用可持久化线段树加速查询 $[0,\mathrm{sum}+1]$ 区间内的数，因为一次可以把多个数加进 $\mathrm{sum}$，所以 $\mathrm{sum}$ 只会增加 $O(\log\sum a_i)$ 次）

想到这里，这题差不多就会做了，从小到大选 $S_1$ 中的元素，如果 $S_1$ 中没有 $[0,\mathrm{sum}+1]$ 内的元素（$\mathrm{sum}$ 为已选元素之和），那么就从 $S_2$ 中贪心选出尽量大的数加入 $S_3$（因为答案是选出数的和，所以不贪心取最大的话可以调整成更大的数更优），直到 $S_1$ 和 $S_2$ 剩下元素都大于 $1+\mathrm{sum}$ 或 $|S_3|=k$。于是我直接在手机上写完，交上去，TLE。

然而我的复杂度是 $O(nm\log m+Tm)$ 啊，应该不会TLE的？回头看一遍数据范围发现这题输入了 $10^6$ 个数，不加输入优化没什么救，然后就在刚到家的时候把输入优化码完，AC了。

回家上电脑接着看了后几题。B题一开始以为是个无聊的卡精度马尔可夫过程，思考了一下才明白决策是自己选的，然后列出来就是最小化一个带一堆 $\min$ 的奇怪式子，不会了。C题题目不是很懂，一大堆 $e$ 看起来很丧。D题让我想到了UOJ #176，然而这题我并不会做，惨啊……

不过好像D可做？用UOJ那题的题解里提到的Boruvka算法，建Trie维护一下可能就OK了？问题是要计数。接着想了一些办法，首先是相同点权构成的点集 $S$ 连的是边权 $0$ 的完全图，一定全部被连起来，方案数是 $|S|^{|S|-2}$。缩完相同点权以后，相同边权的边就没有公共点了，意味着MST唯一？好像很资磁。

于是快要0:00开始写Boruvka，写完一测样例果然萎了。原来……我太SB了，虽然相同边权的边没有公共点但是在缩的时候会把这些边的端点缩到一块去……看样子这么做下去并没有前途。

先去睡觉了。

纠结于5题刚不出来的我冷静了一晚上，感觉好像理解了C题的意思。于是第二天一起来去刚C题。

推了一发式子——

$$[f(x)-e^x]^2=\sum_{i=0}^Na_i^2x^{2i}+2\sum_{i=0}^{N-1}\sum_{j=i+1}^Na_ia_jx^{i+j}-2\sum_{i=0}^Na_ix^ie^x$$

$$(x^i)'=ix^{i-1}\Rightarrow\int_0^1x^i\mathrm{d}x=\frac{1}{i+1}1^{i+1}-\frac{1}{i+1}0^{i+1}=\frac{1}{i+1}$$

然后并没有想清楚 $x^ie^x$ 定积分怎么求，就开始手算小数据：

$$(x^ie^x)'=(ix^{i-1}+x^i)e^x$$

$$\Rightarrow [(x-1)e^x]'=xe^x$$

$$\Rightarrow [(x^2-2x+2)e^x]'=x^2e^x$$

$$\Rightarrow [(x^3-3x^2+6x-6)e^x]'=x^3e^x$$

这样归纳一下好像就推出来了：

$$(e^x\sum_{i=0}^n(-1)^iA_n^ix^{n-i})'=x^ne^x\Rightarrow\int_0^1x^ne^x\mathrm{d}x=e\sum_{i=0}^n(-1)^iA_n^i-(-1)^nn!$$

这么看来原式应该就等于

$$\sum_{i=0}^N\frac{1}{2i+1}a_i^2+2\sum_{i=0}^{N-1}\sum_{j=i+1}^N\frac{1}{i+j+1}a_ia_j-2\sum_{i=0}^N[e\sum_{j=0}^i(-1)^jA_i^j-(-1)^ii!]a_i$$

只有二次诶，那只要对每个 $a_i$ 令偏导为 $0$ 就行了，就能得到一个 $N+1$ 元一次方程组（UPD）：

$$\frac{2}{2i+1}a_i+2\sum_{0\le j\le N,j\ne i}\frac{1}{i+j+1}a_j-2[e\sum_{j=0}^i(-1)^jA_i^j-(-1)^ii!]=0$$

用高斯消元解方程组就做完了，可是 $a_i=\sum_{j=0}^\infty p_{ij}\cdot e^j$ 什么鬼？？难道要把多项式放进去消元，这个是要炸的呀。看了下方程组发现系数矩阵 $A$ 的数都是有理数，那么解方程 $Ax=b$（$x,b$ 为列向量）得到 $x=A^{-1}b$，而 $b$ 中的数都能表示成 $p_0+p_1e$ 的形式，所以答案 $x$ 也能表示成 $p_0+p_1e$ 的形式。

出题人真坑，明明答案是 $p_0+p_1$ 的形式，只有 $p_{i0},p_{i1}$ 是有用的，题面偏要写成 $\sum_{j=0}^\infty p_{ij}$ 误导别人存整个多项式。然后又只要输出有用的那两个数。坑爹！！

推导这里就开始写，写完之后测了下样例 $N=0$ 过了，$N=1$ 的WA了。开始怀疑算法有没错。或者是哪一步推导错了。好虚啊。

手算了一边发现算法是对的，调一发程序，是程序把某个式子算错了= =b

改改改。

终于过样例了。

终于过了C。

看了下榜已经一堆人过5题了，而我只有约四十名。我开始做B题。

一开始想枚举每个点的前继然后怎么搞，觉得好像有反例（？）就犹豫了好长时间。不过想了一会儿还是找到了正确的思路：先确定 $0$ 个星的时候的决策，显然升级概率越大越好，再确定 $1$ 个星时候的决策……

因此，记 $f_i$ 为当前有 $i$ 个星，按照最优策略，第一次变成 $i+1$ 星的期望花费，则枚举选择的魔法石 $j$，有 $1-\mathrm{prob}(i,j)$ 概率失败，失败的话就要从 $i-\mathrm{lose}(i,j)$ 星逐步转移到 $i+1$ 星，因此 $f_i=\min_j\{C_j+[ 1 - \mathrm{prob}(i,j) ]\sum_{k=i-\mathrm{lose}(i,j)}^if_k\}$。

移项得到 $f_i=\min_j\{\frac{C_j}{\mathrm{prob}(i,j)}+[\frac{1}{\mathrm{prob}(i,j)}-1]\sum_{k=i-\mathrm{lose}(i,j)}^{i-1}f_k\}$。直接DP会有精度问题吗？

那我写一下交个看看。写完没过样例因为我把 $C_i$ 写丢了（还查了好一会儿），过了样例交上去。结果，居然直接AC了，完全没有卡精度的迹象。

我也不知道为什么没有出精度问题，也许是运气好吧。上次在51nod做同一个出题人出的马尔可夫过程题还卡了好久的精度呢。

再看D的时候D的通过人数已经好多了。这题一定不难，只是我想复杂了。

于是手工模拟了一遍点集 $\{0,1,2,3,4,5,6,7,8\}$ 的Kruskal过程，整个过程如下：

$$\{0\},\{1\},\{2\},\{3\},\{4\},\{5\},\{6\},\{7\}$$

$$\{0,1\},\{2,3\},\{4,5\},\{6,7\}$$

$$\{0,1,2,3\},\{4,5,6,7\}$$

$$\{0,1,2,3,4,5,6,7\}$$

我好像发现了什么……是按二进制位从低到高合并的！

如果在Trie树上呢？连边 $(u,v)$ 的时候，$(u,v)$ 的权值最高位就是 $u,v$ 在Trie上的LCA高度。因此对Trie树 $T$ 模拟Kruskal的方法是这样的：

Kruskal(T):
    若 T 的左子树非空: Kruskal(T 的左子树)
    若 T 的右子树非空: Kruskal(T 的右子树)
    // 以上两步之后最多只剩左右子树两个连通块，并且这两步过程中连的边权都比剩下可能连的边小，因此是正确的
    若 T 的左子树 T1 和右子树 T2 均非空（假设 |T1| < |T2|）:
        x = Infinity, c = 0
        DFS 枚举 T1 节点 u，DFS 过程中在 T2 中贪心地找点 v 使得 a[u] xor a[v] 最小: // 由于缩了相同点，每个 u 对应的 v 唯一
            若 a[u] xor a[v] = x: c += 1
            若 a[u] xor a[v] < x: x = a[u] xor a[v], c = 1
    最小生成树边权和加 x，方案数乘 c

这个问题的性质就是左右子树独立，注意到这一点以后就变地简单多了。然后我把原来写的错误的Trie树Boruvka算法删了一大半，改成直接在树上DFS，过了样例，交上去也过了。

过D的时候12:00多。昨晚觉得B、C、D都一副不可做的样子，不过现在都做出来了，有点爽。

还剩E、F两题。

下午开始搞E。有点像个大代码数据结构题，不过如果真是这样的话不虚，因为时间充足，呵呵。

一开始题目看错了，以为是链上插入一个元素，查询过一个点的元素中前 $k$ 小的异或。我想这不就是把链拆成到根的路径以后转成查子树区间 $k$ 小吗，可持久化线段树就搞定了。E题肯定不是这么简单！又读了遍题目，才明白真正的题目意思是：每个点 $i$ 维护一个初值为 $0$ 的数组 $c_i$，每个操作 $(u,v,a,b)$ 把链 $(u,v)$ 上所有点 $i$ 的 $c_i[b]$ 增加 $a$，查询的是 $c_w$ 数组中 $c_w[i]$ 前 $k$ 小的 $i$ 的异或。

这下就不太一样了，因为用可持久化线段树虽然可以对每个 $b$ 查出 $c_w[b]$，却不能查出 $c_w[b]$ 前 $k$ 大的 $b$。不给力。

可能我需要换个想法。如果不是树而是序列呢？那就只要按顺序扫一遍过去，维护一个 $c$ 数组，遇到操作的左端点就把 $c[b]$ 加 $a$，遇到右端点就 $c[b]$ 减 $a$。用线段树维护每个 $x$ 对应的满足 $c[i]=x$ 的 $i$ 个数就能查前 $k$ 小了。可是一样多的按 $i$ 排序怎么搞？

那就把每个 $(c[i],i)$ 表示成一个数 $c[i]\cdot B+i$。

值域好像很大的样子，线段树要动态开节点- -那么如果是树呢？树剖一下？

于是一个操作被拆成了 $O(\log n)$ 个，每次要改线段树，复杂度变成 $O(\log^2 n)$ 了- -

不知道能不能过，而且觉得空间会爆炸的样子。不过空间好像不是 $O(m\log^2 n)$ 而是 $O(m\log n)$？我写下。……写完了，调一发。……过样例了。

然后在51nod上运行了第一个点，MLE。

数组改小。

MLE。

再改小。

MLE。

再改小。

RE。

想放弃。

然后记起51nod好像是64位机？如果我把指针改成 int 下标呢？改。

改完。

测一下。

第一个点过了。

交。

WA

WA

WA

……

那应该是我写挂了。回去和暴力拍小数据，怎么都拍不WA，又拍了好多组大数据也拍不WA。这就很尴尬了QAQ

最后还是死于线段树的区间：right = m * 10000000000ll 打成了 right = 10000000000ll。这个小数据不太可能拍出来……

挣扎了一下午，终于在17:00前用两个 $\log$ 把这题卡过去了。

有希望。

现在剩下F。

所有LCS的和？我只会求 $|s_2|$ 遍LCS。可是显然过不去。

或者是需要一些特殊的状态设计？于是开始设计新的DP，结果不管怎么改都要 $O(|s_1||s_2|^2)$。GG。总觉得自己是想复杂掉坑了，可是又总是找不到可行的方法。

最后还是在rank 1的AKF帮助下才得救……AKF表示这题是“All Substring LCS”，是论文题。于是我就去看了论文，然而由于我太菜鸡了，看了很久才看懂。。。

所以到了第二天的下午才搞掉F。一看排行榜，刚好rank 10。有点感动。

这场比赛还是有一些收获的。

A题的贪心算法还是比较妙的，虽然如果做过Codechef原题以后就没什么难度了- -

B题给我的启发是：形如 $f(i)=a_i+\sum_{j=0}^{i+1}c_{i,j}f(j)$（其中 $\sum_{j=0}^{i+1}c_{i,j}=1,c_{i,i}\ne 1$）这样的方程，可以按照 $i=0,1,2,\cdots$ 的顺序递推，这样的好处是，每个 $f(i)$ 可以表示为 $f(i+1)+p_i$ 的形式，可以归纳证明：

$$f(i)=a_i+\sum_{j=0}^{i-1}c_{i,j}[f(i)+\sum_{k=j}^{i-1}p_k]+c_{i,i}f(i)+c_{i,i+1}f(i+1)$$

$$\Rightarrow f(i)=a_i+(1-c_{i,i+1})f(i)+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k+c_{i,i+1}f(i+1)$$

$$\Rightarrow f(i)=\frac{1}{c_{i,i+1}}(a_i+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k)+f(i+1)$$

即 $p_i=\frac{1}{c_{i,i+1}}(a_i+\sum_{j=0}^{i-1}\sum_{k=j}^{i-1}p_k)$，若已知 $f(n)=0$，按 $i=0,1,2,\cdots,n-1$ 顺序递推 $p_i$ 可以求出所有的 $f(i)$。另外我还是很好奇这题为什么要注意精度，直接写应该就过了吧？

C题的收获是求 $x^ie^x$ 的积分以及用偏导求多元二次函数的最值（其实原理和初中学的二次函数一模一样）以及克服看到一大坨数学公式时的畏难情绪。

D题的思路很不错，也是容易想错的题，主要是容易往基尔霍夫矩阵等复杂算法考虑，却解决不了。能深入理解Kruskal这一个算法，比涉猎各种复杂的图论算法（如基尔霍夫矩阵等）有意义得多。

E题后来immortalCO给我讲了一个更简单的做法：按照我之前的想法拆链之后，不用可持久化线段树前缀和来查询，而是对每个节点维护子树的 $c$ 数组以及对应的排序列表，用平衡树启发式合并来维护。这样虽然时间也是 $O(n\log^2n)$ 的，但空间是 $O(n)$ 的，不需要强行优化内存常数。想想我去年做一道Codechef的启发式合并题想了好几天才想到正解。可见我还需要加强数据结构的灵活变通能力。

F题的收获是学习了一个新的算法ALCS，这个算法思想是很不错的，利用特殊的单调性来改变状态设计。希望能找到这类问题的更多应用。