9
29
2014
0

POI系列

PA做着做着就不会做了,上一个坑绝壁是填不满了。。然后对波兰人产生了一些兴♂趣。

也算是⑩月新坑吧,督促自己多刷题QAQ。


我先为BZOJ打一发广告。

这是非VIP的POI题目数量

这是VIP的POI题目数量

也是挺感人的。

为了不浪费我花掉的钱,于是决定来刷一刷。


upd.9.29

[POI2007]旅游景点atr:spfa跑完以后状压dp

[POI2007]办公楼biu:显然补图的联通分量即为答案,然而补图很稠密,联通分量很小但是依然可以卡,那就bfs+删链表+回退链表好了,很好写1k足矣。

[POI2007]树Drz:感觉很恶心的线段树啊,各种情况判一判分别维护线段树,大概就这样,我还没写(也不想写了),可能会口胡成分比较大。


upd.10.10
 
1100: [POI2007]对称轴osi:一开始想找个最小的对称轴角度,感觉没复杂度保证,然后就搜了一下题解QAQ,把这个图形翻转一下和原图形做串匹配。。
 
[POI2007]Zap:莫比乌斯反演。
 
[POI2007]山峰和山谷Grz:难得的POI水题。普及组难度。
 
1103: [POI2007]大都市meg:国外的数据结构题档次也就这样了,数据结构灭退保
 
1106: [POI2007]立方体大作战tet:很显然是挨得近的先删除,那就记一个是否出现过的flag,然后树状数组维护前缀和。
 
1107: [POI2007]驾驶考试egz:我们可以把横向边都反一下,然后最左的纵向道路能走到最右的纵向道路和最右的纵向道路能走到最左的纵向道路之差就是当前不支付代价所能选择的纵向道路。然后我们要加一些边计算最左(或最右)到某纵向道路的最小代价,那只能是dp了,[tex]f_{i,j}[/tex]表示第[tex]i[/tex]个纵向道路的第[tex]j[/tex]高度所要添加的边数,到然后还是用树状数组维护前缀MIN优化dp,由于左右的dp是一样的,写成一个过程就短很多,最后做一个贪心就好了。
 
1108: [POI2007]天然气管道Gaz:一开始题目看错了又T_T,感觉神题百度了一下。。。又见结论题。
 
1109: [POI2007]堆积木Klo:Seter有题解,知道那个式子推下去的结论后就可以随便来了。(我要举报,读入优化无节操T T)

upd.10.20

1110: [POI2007]砝码Odw:这么神的做法我显然想不出来。首先从小到大贪心放一定是对的,然后由于题目条件设置,其实不同的砝码一定是一个等比数列,那么不同的个数就是log级别的,我们把这些不同的砝码看作进制每一位的基底,每个容器都进制分解掉,然后从小到大能装则装。

1112: [POI2008]砖块Klo:固定区间中位数,用树状数组就好了,难度瞬间下降。

1113: [Poi2008]海报PLA:长值何用系列。无脑做差。

1115: [POI2009]石子游戏Kam:阶梯nim,get√

1105: [POI2007]石头花园SKA:猜一个结论,放到[tex]y=x[/tex]一边去就可以是最优的,发现叉不掉自己,那就是对了:P,然后还有一问,有点恶心,[tex]max_x,max_y[/tex]以及[tex]min_x,min_y[/tex]两两是可以互换的,除此以外,还要判可行性,但你以为这样就好了嘛,矩形边长会爆int你服不服。

1117: [POI2009]救火站Gas:树形贪心?233333


upd.10.24

1119: [POI2009]SLO:置换圈找一下,找个最小值换,或者找全局最小值换。

1121: [POI2008]激光发射器SZK:光路可逆。

1122: [POI2008]账本BBB:枚举2操作有几次,维护前缀min,单调队列,好烦T T。

1123: [POI2008]BLO:割点。

1124: [POI2008]枪战Maf:自环判,“环套内向树”上判,环上判。。。


upd.10.26

1125: [POI2008]Poc:听说波兰人喜欢卡hash?事实证明还是有点节操的。hash搞搞,并查集搞搞就[tex]O(\alpha m)[/tex]了,一开始想用map,为了复杂度好看一点就没用。


upd.11.1

1130: [POI2008]POD Subdivision of Kingdom:复杂度只允许[tex]C^{13}_{26}[/tex]。所以要优化计算边的方法,就用位运算,分块预处理[tex]0\sim2^{16}-1[/tex]在二进制下[tex]1[/tex]的个数,然后dfs位运算就好了。

1131: [POI2008]Sta:dfs下去转移就好了。

1132: [POI2008]Tro:[tex]3000^2log_23000[/tex]居然可以过。。。枚举[tex]i[/tex]极角排序,叉积前缀和。


upd.11.20

1133: [POI2009]Kon:首先要知道两两站之间转移有效检票数,这个只要把读入的乘客上下方案每层做一个后缀和,比如做出来的后缀和是[tex]suf_{i,j}[/tex],那么[tex]i[/tex]站转移到[tex]j[/tex]站的有效检票数就是[tex]\sum_{k=i+1}^{j}{suf_{k,j+1}}[/tex],然后直接做复杂度是[tex]O(n^3k)[/tex]显然不对,主要是因为区间求和很暴力,很容易发现改动一下转移方式就可做到区间求和和转移同步,就优化了一个[/tex]n[/tex],可过。

1135: [POI2009]Lyz:

令每个大小的人数为[tex]p_i[/tex]

当前合法的条件是

[tex]\forall(l,r)[l\leq r],~\sum_{i=l}^{r}{p_i}\leq (r-l+1+d)*k[/tex]

移项可得

[tex]\forall(l,r)[l\leq r],~\sum_{i=l}^{r}{(p_i-k)}\leq d*k[/tex]

由于[tex]d*k[/tex]值固定,故问题转化为动态维护最大子段和,判断其是否超过[tex]d*k[/tex]

线段树。


upd.11.20

poi太神了。。。好多题做不动T T。。。弱死了


poi题解分年写了QAQ。


 

Category: BZOJ | Tags: POI bzoj Problem sets Polish | Read Count: 4274

Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com