SHENXN's BLOG

Purdue University
Computer Science, Math

Xiaonan Shen's avatar Xiaonan Shen

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

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

Xiaonan Shen's avatar Xiaonan Shen

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

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

[BZOJ1861][ZJOI2006]书架(SPLAY)

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