SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1189][HNOI2007]紧急疏散evacuate(二分答案 + 最大流)

做了好几题裸的最大流,来一道稍微不裸一点的(不过这种经典题也没什么好说的),首先题目二分答案,然后用最大流验证是否满流。首先要做一次BFS预处理,预处理出所有的空点到所有门的最短路。做最大流时,首先将源点向所有空位置连一条容量为1的边,将所有的门向汇点连一条容量为时间的边(一开始连了N * M的容量,坑了好久。。),再将所有空点向时间内能到达的门连一条容量为1的边。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1433][ZJOI2009]假期的宿舍(最大流)

又是一道最大流,建图很简单,源点到所有的在校学生和外校学生建一条容量为1的边,所有在校学生的床(感觉听起来怪怪的)到汇点连一条边,所有在校学生和自己的床连一条边,所有学生到他认识的在校学生的床连一条边。然后做最大流与需要住校的学生总数比较,相等就输出^_^,不相等就输出T_T(这个太逗了)。。     Read more

Xiaonan Shen's avatar Xiaonan Shen

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

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

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1934][SHOI2007]Vote 善意的投票(最大流)

双倍经验题,详见     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ2768][JLOI2010]冠军调查(最大流 最高标号预流推进 + GAP优化)

这题很显然是一道最小割的题目,然后题目只要求最小割的容量,那么直接跑个最大流(关于最小割-最大流定理请自行谷歌),以前写过DINIC感觉不够高大上,然后果断来一个最高标号预流推进秀优越,事实上这个时间复杂度的确很优秀。一开始我写的没加GAP优化,400+ms,跑得比DINIC还慢,真是不爽,下午看到了一种叫GAP优化的东西,加上之后就28ms了,怒刷到rank2。     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

Xiaonan Shen's avatar Xiaonan Shen

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

传说中的双倍经验题,详见     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1001][BEIJING2006]狼抓兔子(最小割 + DIJKSTRA)

这道题很裸的最小割,只是数据规模大,目测会T(WJS大爷说在BZ上能过,真是跪烂了),其实最小割可以转成最短路的做法。一种做法是转成对偶图然后求最短路,当然我不会,就只好去墙角画圈圈了。不过有一天没事乱翻LRJ的白书突然就翻到了这道题(我真的只是乱翻),然后就观摩了一下题解。转什么对偶图啊。。对于这道题,由于这个图样子比较特殊,可以知道割线必然是一条从图的左边界或下边界的边出发,经过若干条边到达右边界或上边界的边,需要的狼的数量就是经过的所有边的权值和。     Read more

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1902][ZOJ2112]ZJU2112 Dynamic Rankings(树状数组 + 主席树)

终于学会了主席树,写了高贵冷艳的带修改区间第K大(虽然二逼平衡树我是用分块水的),关于不带修改的区间第K大参见我的上一篇博客[POJ2104]K-th Number(主席树),其实这个跟树状数组维护前缀和基本是一样的,只是修改时树状数组只需修改(log_2n)个节点,而现在需要修改(log_2n)棵线段树,一共(log_2^2n)个节点。这题在八中上妥妥A了,ZOJ被卡内存(内存小,数据规模还大,还有多组数据,改了半天),到现在都没卡过去,真是不开心。     Read more

Xiaonan Shen's avatar Xiaonan Shen

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

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