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) 末尾无用舍去

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