SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1066][SCOI2007]蜥蜴(最大流)

这道题就是最大流,首先对柱子进行拆点,一个入点和一个出点,入点向出点连一条容量为柱子高度的边,从每个柱子的出点,向可以一次跳到的所有柱子的入点连一条容量为当前柱子高度的边,再从每个可以一次跳出的柱子向汇点连一条容量为柱子高度的边,从源点向每个有蜥蜴的柱子的入点连一条容量为1的边,然后做一次最大流即可。当然答案输出的是不能跳出的蜥蜴,我被坑了好久233     Read more

Xiaonan Shen's avatar Xiaonan Shen

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

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