SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ3595][SCOI2014]方伯伯的OJ(MAP + SPLAY)

这道题实在是坑爹,比赛的时候一度以为要两个MAP两棵SPLAY,然后感觉写着蛋疼就写了一个SPLAY 40分滚粗了。后来重新看题,发现其实AC算法也只要一个SPLAY就好了,还有一个SPLAY也可以用MAP来代替(在此BS一下PASCAL,问PASCAL党做这种题该怎么办)。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1862][ZJOI2006]GameZ游戏排名系统(SPLAY + TRIE / HASH)

传说中的双倍经验题,详见     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

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

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

Xiaonan Shen's avatar Xiaonan Shen

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

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

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1269][AHOI2006]文本编辑器(SPLAY)

好吧这道题是NOI的那道EDITOR的升级版,就多了一个翻转操作,那不是改一下就行了嘛,果断继续A题     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1507][NOI2003]文本编辑器(SPLAY)

这题我一开始用块链写的,后来也许是memcpy上的问题本地AC了八中上死活A不掉,后来也就没去改。。几天后学了SPLAY,那就用SPLAY水掉了。 然后是代码(这个不是蛋疼模板了,我重写的SPLAY)     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1861][ZJOI2006]书架(SPLAY)

听说标程是树状数组,听说树状数组跑得可快了。。好吧拿这题来学SPLAY的确有点做死不过也还算裸 SPLAY要维护的东西很清楚,就是要单独开个数组指向SPLAY上每个节点,以方便根据编号找节点。     Read more