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

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

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

Xiaonan Shen's avatar Xiaonan Shen

[BZOJ1208][HNOI2004]宠物收养所(treap)

没什么好说的,一道不能更裸的TREAP,TREAP这随机种子真是蛋疼。。直接上代码了(原谅我的代码风格,这代码真是长。。)     Read more