【整理向】一周刷题记录4年3月1周

#4,Mar,2014 Tue

##[POI2007]大都市meg

一棵树上，问从根节点到某节点的权值和（带修改，权值为0或1）

可以用DFS序加上BIT实现

从根节点开始遍历，如果进入某一节点时，往序列末加上一个1，离开时，往序列末加上一个-1

记下某一节点在序列中对应的位置，维护前缀和即可

代码

##[POI2007]旅游景点atr

一个图，按照一个给定DAG来遍历，问最短路

状压记忆化搜索+SSSP

DAG上才20个节点

所以我们可以针对DAG上每一个节点求一次SSSP

接下来DP，二进制状压，记搜就够了

代码

#5,Mar,2014 Wed

##[POI2007]洪水pow

一个图，然后干些奇怪的事情，我实在不好描述，下面是原题：

###Description

AKD市处在一个四面环山的谷地里。最近一场大暴雨引发了洪水，AKD市全被水淹没了。Blue Mary，AKD市的市长，召集了他的所有顾问（包括你）参加一个紧急会议。经过细致的商议之后，会议决定，调集若干巨型抽水机，将它们放在某些被水淹的区域，而后抽干洪水。你手头有一张AKD市的地图。这张地图是边长为mn的矩形，被划分为mn个11的小正方形。对于每个小正方形，地图上已经标注了它的海拔高度以及它是否是AKD市的一个组成部分。地图上的所有部分都被水淹没了。并且，由于这张地图描绘的地面周围都被高山所环绕，洪水不可能自动向外排出。显然，我们没有必要抽干那些非AKD市的区域。每个巨型抽水机可以被放在任何一个11正方形上。这些巨型抽水机将持续地抽水直到这个正方形区域里的水被彻底抽干为止。当然，由连通器原理，所有能向这个格子溢水的格子要么被抽干，要么水位被降低。每个格子能够向相邻的格子溢水，“相邻的”是指（在同一高度水平面上的射影）有公共边。

###Input

第一行是两个数m,n(1<=m，n<=1000). 以下m行，每行n个数，其绝对值表示相应格子的海拔高度；若该数为正，表示他是AKD市的一个区域；否则就不是。请大家注意:所有格子的海拔高度其绝对值不超过1000,且可以为零.

###Output

只有一行，包含一个整数，表示至少需要放置的巨型抽水机数目。

###Sample Input

6 9
-2 -2 -1 -1 -2 -2 -2 -12 -3
-2 1 -1 2 -8 -12 2 -12 -12
-5 3 1 1 -12 4 -6 2 -2
-5 -2 -2 2 -12 -3 4 -3 -1
-5 -6 -2 2 -12 5 6 2 -1
-4 -8 -8 -10 -12 -8 -6 -6 -4

###Sample Output

优先队列加广搜，可以离散化实现优先队列，显然每次要往低的地方放

代码

##[POI2007]办公楼biu

话说我看到这个biu莫名喜感，Biu的一声= =

这题有个结论，答案就是补图的连通块个数

唔，这个结论证明过于简单，如果两块之间没有连线，那么显然两块的内部节点两两肯定连了边（貌似没说清楚来着）

代码

##[NOI2008]糖果雨

唔，NOI2008总算搞完了，算是了结一个心愿了

BZOJ第一面也差不多做完了，当然还有Anti Ants这种神题，待哪天有时间心情好了结掉

当时想着十分复杂，现在算是明白了，就是一个和线段覆盖问题类似的问题，但是这回由于时间，我们要将这个坐标轴变换一下