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

Posted on By 二价氢

#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

2

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

代码

##[POI2007]办公楼biu

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

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

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

代码

##[NOI2008]糖果雨

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

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

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

然后上二维树状数组就够了

代码

##[POI2007]石头花园SKA

这题用到了很强的结论,如果将所有的石头移到的一侧,那么周长一定最小

然后枚举坐标最大最小的4种情况,一一判断即可

代码

#6,Mar,2014 Thu

##[POI2007]山峰和山谷Grz

给一个地图,问局部极值块(我起的名字,就是一块数,相等且局部最大/小)的数量

Flood Fill+并查集

代码

各种STL无节制使用ing

##[CTSC2008]祭祀river

从一个DAG上取若最多的点,使得所取的点两两不可达

涉及到一个“二分图最大独立集”问题

一个结论:二分图最大独立集=点数-最大匹配数

如果两点可达,则在两点间连边,匹配即可

代码

##[CTSC2008]网络管理Network

树上带修改区间第k大,用DFS序构造的树状数组套线段树

代码

#7,Mar,2014 Fri

##[Wc2011] Xor

最大异或和路径

找出所有的环,对环进行高斯消元,使之成为“基础环”(我起的名字),然后从中选取若干个,使结果最大

代码

##[HNOI2007]最小矩形覆盖

凸包+旋转卡壳

[代码略]

##[ZJOI2010]network网络扩容

这题是当时说“还有一个小时吃饭就再做一题”做的来着

太水了!!!

代码

##[CTSC2008]图腾totem

一个排列,问2341型,3421型和1324型排列占的个数(貌似还是不清楚)

代码

然后这个星期下来,Page1差不多做完了,下一步估计就是随机做,或者是按各省省选题为单位做吧= =

一周总结到此结束