SHENXN's BLOG

Purdue University
Computer Science, Math

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

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ3223][TYVJ1728]普通平衡树(FANHQ_TREAP)

这道题就是裸裸的TREAP,然后TREAP的裸题好像已经写过了,于是决定试试写FANHQ TREAP,一开始我插入没写旋转,后来仔细研究了FANHQ的博客,才知道后来他加了旋转(说好的没有旋转呢),然后我去加了旋转果断快了50ms     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1500][NOI2005]维修数列(SPLAY)

好像已经写了好多SPLAY了,维修数列说是最重口味的SPLAY题目了,好吧我也调了将近一上午,主要是最大子段和的地方自己YY错了,少考虑了一种情况。。     Read more