$Problem’s$ $Website$

BOI2009 Radio Transmission 无线传输

$Solution$

• 这道题会详细地解释$KMP$算法中的$next$数组(下文写作$nxt$)，可以配合我的另外一篇辣鸡题解进行学习。

$Problem’s$ $Website$

圣诞树

（没有权限查看题目的同学不要打我）

$Problem’s$ $Website$

X龙珠

$Solution$

运用链表思想，用数组模拟链表，存储一个数据的$next$和$last$(后一个和前一个)，然后类似于贪心，我们从大到小枚举，如果当前的数没有$next$，说明无法输出，如果有，则将它和它的$next$输出，更新一下与这两个数相邻的数的$next$和$last$，然后将这两个数的$next$和$last$清零即可。

$Problem’s$ $Website$

2019.8.28模拟赛T2

$Solution$

$dp$求解，我们设$f[i][j][k]$为前$i$个数，最后连续$j$个黑球，连续$k$个白球的方案数，这样求出来答案要$\times 2$，因为颜色可以互换。

$Problem’s$ $Website$

20190828模拟赛T3

$Solution$

首先，不懂权值线段树的同学可以暂时先去这学习一下。

根据数据范围，我们要离散化一下。

$Problem’s$ $Website$

TJOI2013 最长上升子序列

$Solution$

这道题是一道既考思想有考代码能力的好题，能学到不少东西。

这道题我是用$fhq-Treap$ $+$ 线段树 做的，思想类似于模板 最长公共子序列，这道题我写了一篇题解，大家可以先去查看一下，当然也可以不看。。。

$Problem’s$ $Website$

TJOI2007 书架

$Solution$

这是一道平衡树的好题，因为我暂时不会$Splay$，所以我就用$fhq-Treap$来写。

首先关于$fhq-Treap$的一些解释在我的另外一篇blog中已经详细说明了，不懂的童鞋可以先去学习一下。

这道题要用到排名分裂，同样用到这种方法的还有另外一道同名题。

$Problem’s$ $Website$

ZJOI2006 书架

$Solution$

这道题是一道平衡树好题，我暂时不会$Splay$，所以就用$fhq-Treap$做。

这道题就要用到排名分裂了。

也就是以排名为对象进行分裂。

对这道题来说，排名就相当于当前这本书上有几本书。

特殊地一点：用一个数组将书的编号映射到树中的编号。

因此，我们还要记录每个节点的父亲节点。

我们来详细解释一下题目中操作的步骤：

Problem’s Website

NOI 2004_郁闷的出纳员（LOJ）

NOI 2004_郁闷的出纳员（洛谷）

Solution

这道题是平衡树的一道模板题，可以用$Treap$做，但是我太菜了，于是我用$fhq-Treap$做。

这道题加深了我对$fhq-Treap$分裂操作的理解。

Problem’s Website

普通平衡树（洛谷）

普通平衡树（LOJ）

Solution

没错，又是这道题。

再上一篇题解中，我们介绍了使用$Treap$的做法，那么本篇题解讲解一下$fhq-Treap$的做法。