Ruins He's house

本题算是比较难想的题目了，比赛的时候想成 Splay 果断悲剧，今晚才突然发现直接用可以合并的树就可以了。

思路是维护一颗二叉树，每次来了一个元素，找到元素对应的位置，注意找到的位置是靠最右边的第一个比它大的元素的位置，如果此元素在 $c_i$ 步内不能到达，就插入元素到右边第 $c_i$ 个位置。

动态树的 split 函数表示将树中的第 $k$ 个和第 $k-1$ 个元素分开，形成两棵树，这样我们将一个单独的结点分别与这两棵树合并，就可以得到新的序列。

最后进行中序遍历得到最后的解，注意树的合并必须用随机算法，否则会使树退化。

这题暴力复杂度是 $O(2^n)$ 的，对于 $24$ 的复杂度明显不可做，我的方法是进行优化，枚举前 $\frac{n}{2}$ 个，得到每个陷阱对应的宝物编号，这样对应了一个映射，然后枚举剩下的宝物，找到对应陷阱所对应的前半部分宝物，所有宝物的价值之和就是目前的答案，取最大的即可。

宝物和陷阱可以用 int 和 long long 压缩，最后放入 map 中。复杂度 $O(2^{\frac{n}{2}})$

这道题裸的 dp 方程应该可以写的出来，我记录的状态如下：

$dp[i][j]$ 表示以 $a_i$ 为第一个元素，$a_j$ 为第二个元素的斐波那契序列的最大长度，这样 $i \leq j$ 转移方程：

$$dp[i][j]=dp[j][k]+1$$

其中 $a_k=a_i+a_j$

从后向前扫描，每次更新 $dp$ 值后更新最大长度以及第一第二项，最后的答案直接根据第一第二项迭代即可

现在遇到的最大问题就是转移，裸的转移是 $O(n)$ 的，直接从前向后扫一遍，找到第一个符合条件的 k，这样总的复杂度是枚举加上扫描，是 $O(n^3)$ 的，明显对 $n$ 为 $3000$ 的数据来说太大了，不可取。

后来想到了二叉树，嗯，就是 map，在树中维护值为 x 的最前位置，这样直接通过在树中找 $a_i+a_j$ 的最前位置即可，后来想想也不对，复杂度是$O(n^2 \times logn)$ 的，对于 STL 的大常数不放心，算了一下 $3000^2 \times lg{3000}$ 差不多$10^8$ 数量级，会 TLE。又开始想转移能不能压缩。

最后想到 hash 的办法，因为转移无非就是在一个序列中找一个 $x$ 对应的最前位置，直接将 $x$ 进行 hash，对应的 hash 值的位置存放我们要的 $x$ 对应的最前位置即可。

hash 函数乱写的 - -

发现其实数据重复的概率不大，没有优化，直接用了。。。

这样可以在近似 $O(1)$ 的时间内找到我们要的值，转移加上枚举就是 $O(n^2)$ 的了

平衡二叉树的入门题，最近在研究 splay，就做了下，感觉题目不错，就写了。

这题就是简单的元素插入删除操作，注意一下绝对值相同的时候取较小的即可，还有就是每次收养所里要么都是人，要么都是宠物。

这里用到一个 $type$ 变量记录树种元素是人还是宠物，如果是 - 1 表示空

这样每次取得一个数，如果和树种类型一致，就加入树种，否则就在树中寻找绝对值离它最近点一个即可。

代码写的比较长，有些是这道题不需要的函数，主要是为了封装，全部写了出来，可以当模板用。只是多元素的处理没有弄好，如果有重复元素，$rank$ 和 $selete$ 函数以及结构体的封装就要换一下了。

最近很忙，基本上没时间写解题报告了，还是想写写当时比赛的情况，嗯，这篇文章是写的晚了点。

来到哈尔滨的时候是报到前一天中午，我们应该是比较早到的队伍了，到了哈尔滨，刚走出去就感受到了什么是寒冷，9 月的哈尔滨，10°C 不到的温度，我直接套上了大衣，中午吃完饭到了招待所，做的第一件事，就把内衣换上了。。。

热身赛比较悲剧，队友一时头脑发热，BFS 想成堆优化 Dijkstra，没有切圆