NanoApe's Blog

既是咸鱼又是辣鸡

【Plan B】#18

NanoApe posted @ 2016年7月08日 20:58 in 蒟蒻不做题提前退役 , 536 阅读

NOI 前最后一篇 Plan B

啊有可能是退役前的最后一篇[苦笑]

15/50

update:16.07.08

2091: [Poi2010]The Minima Game

DP,一个人一定是从大到小拿牌,f[i] 表示还剩第 i 小的牌,能够获得的最大收益,显然答案是 f[n];然后对于一个 f[i] 只有两种情况,第一种是只拿第 i 大的,获得收益是 a[i]-f[i-1],要么不拿第 i 大的,收益为 f[i-1] 取 max 即可

2938: [Poi2000]病毒

AC 自动机建完后结尾点禁止,预处理出每个点走0或1的路会到哪个点,然后看从根能不能走出一个环

3728: PA2014Final Zarowki

每次将灯泡用在要求最高的房间,若有灯泡没用到的时候拿它去之前跳过的房间,若没有跳过的房间则直接丢掉,最后看剩多少房间没灯泡,换个一样的即可

1103: [POI2007]大都市meg

单点修改根路径询问,转成子树修改单点询问,然后 dfs 序就可以了

1109: [POI2007]堆积木Klo

转成最长上升子序列

2802: [Poi2012]Warehouse Store

能放就放,不能的话就看有没有能换下之前那些已经满足要求的且比现在大的

2793: [Poi2012]Vouchers

调和级数可知暴力做就能过了

1535: [POI2005]Sza-Template

kmp 完 Fail 树上遍历,然后每个点维护个双向链表储存祖先的点,答案是在结尾的点到根的路径上

2946: [Poi2000]公共串

SAM 完统计一下

3747: [POI2015]Kinoman

枚举左端点,线段树维护右端点的贡献,做法同“HH的项链”

1119: [POI2009]SLO

同某道题来着,求出置换群后除了能群内交换以外,在群外引入全局最小值绕一圈也是种策略

3522: [Poi2014]Hotel

树形 DP,用相同高度的子节点对减去相同高度的同个子树的子节点对

2079: [Poi2010]Guilds

除了联通块个数为 1 的无解,其余有解

2095: [Poi2010]Bridges

二分答案,变成求混合图的欧拉回路;有向边固定,无向边可以更改方向,且要满足入度=出度,用网络流完成改向这个操作来判定即可

1110: [POI2007]砝码Odw

进制拆分

举例子:当有 3,9,18,54 这些种类的砝码时,133 的容量可以写成 2*54+1*18+0*9+2*3+1,既 (2,1,0,2) 末尾无用舍去

然后按贪心从小到大放置即可,不够则拆高位下来补


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter