SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[POJ2104]K-th Number(主席树)

终于下定决心开始学主席树了,先找了一道不带修改的区间第K大做。关于带修改的区间第K大,参见我的下一篇博客 [BZOJ1902][ZOJ2112]ZJU2112 Dynamic Rankings(树状数组 + 主席树) 主席树其实就是一种可持久化的线段树,是函数式编程的一个很经典的应用(另外的话,我就只知道FANHQ_TREAP了)。主要思想是在对线段树的节点进行修改的时候,不改变原节点,而是新开一个节点并链到数中。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1012][JSOI2008]最大数(树状数组)

树状数组水了一题感觉不熟练就又水了一题。这题主要就是要把整个数列倒过来插,这样就可以把求后L项的最大数转化为求数列前L项的最大数。在树状数组中,维护一个数列大小size,每次插入就插入到第m - size的位置上,每次查询就查询前m - size + l项的最大值(前导零对答案不影响)。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ2743][HEOI2012]采花(离线 + 树状数组)

打算开始学主席树了,然后发现好久没写树状数组,就找了道题练练手,谁知今天脑残不宜写题,WA了半天又T了半天。。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1207][HNOI2005]虚拟内存(HASH + SPLAY)

我原本妄图做一道HASH乱搞题,本以为这道题可以HASH + 优先队列,后来发现好像不行,然后又蛋疼地敲平衡树了。一开始敲了个FANHQ_TREAP,结果被卡,一个点退化了,只好改SPLAY。虽然不是很快,不过完全不知道这道题开50S时限是什么心态。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1003][ZJOI2006]物流运输(DP + DIJKSTRA)

好吧这就是一道大水题,很显然的DP思路。DP状态转移方程就是(dpi = text{min}(f{1,i}, dpj + k + f{j+1,i}) (1 leq j < i)),其中(f{i,j})表示从i时刻到j时刻(包括i和j)走同一条路所需的总成本。而由于n和m都很小,这个直接暴力标记不能走的点然后做一次DIJKSTRA就可以了,同时把已经计算过的(f{i,j})存下来,以便下次使用。这样的话总体的时间复杂度大概就是(原谅我不会算,随便乱估计的)(text{O}(n^2 log_2 m))。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1002][FJOI2007]轮状病毒(DP + 高精度)

这题的DP实在是太可怕,证明了半天,其实就是排列组合。最后证明出来的式子是 (fn = \begin{cases} 1 & (n = 1) \ 2 & (n = 2) \ 3 * f{n-1} - f_{n-2} + 2 & (n \geq 3) \end{cases})     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1056][HAOI2008]排名系统(SPLAY + TRIE / HASH)

只是一道平衡树水题,其实TREAP就可以了,只是有个操作我觉得还是SPLAY写起来舒服。一开始用的TRIE维护名字,后来又用HASH写了,稍微快了一点点。。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ3196][TYVJ1730]二逼平衡树(分块·伪)

平衡树三道题终于全A了。为什么说分块是伪呢,毕竟这是平衡树的题目,然后我用了分块(我弱啊,不会树套)。听说TY上还有大爷直接用sort A掉了,这算什么嘛,还有话说我BZOJ上A掉的代码在TY上死活RE30分,还WA了两个点。不管了。。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ3337]ORZJRY I(块状链表)

保佑我能写出来。。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ3223][TYVJ1729]文艺平衡树(FANHQ_TREAP)

平衡树三件套的第三题目测要树套,我太弱了所以不会,只好接着用FANHQ_TREAP水第二题了。听说这题目只有一个操作,于是很高端地用了FANHQ_TREAP。但是莫名其妙写得好慢,比RANK1慢了1S多,一定是还有什么神奇的算法,求教。。     Read more