正规、严谨、精妙。 -POI

发现POI(波兰信息学奥赛)的题都很有意思。于是开刷bzoj上的poi题目(按ac人数降序。。)。顺手写一写题解，加深印象。

BZOJ 1103 : [POI2007]大都市meg

给一棵树，每次可以把树上的一些边标记了，问一个点与根之间需要走多少没有标记的边。

这个可以把这颗树遍历得到一个dfs序每第一次经过一个点的时候记录为+1,第二次经过一个点的时候记录为-1，然后记录每个点第一次经过时在序列里的位置f[i]和第二次经过在序列里的位置l[i]，对于查询（x）就是序列中一直到f[x]-1的前缀和，因为真正没走的那些边都+1 -1消掉了，只剩下真正要统计的边了。对于每次标记(a,b) 设a < b 就是序列里 f[b]的位置-1，l[b]的位置+1，就相当于消掉了这条边。另外这道题得手写栈dfs，否则会爆栈。

BZOJ 1121 : [POI2008]激光发射器SZK

刚看完觉得不可做。
因为光线都是沿45°，所以从一个点发射光线必有一个点接收，又因为光路是可逆的，不可能有不同的点出发的光路重合的现象，所以输出n/2（原题让输出方案。。）;

BZOJ 1113 : [Poi2008]海报PLA

显然单调栈啊，相等的时候处理一下。没了。

BZOJ 1529 : [POI2005]ska Piggy banks

一堆存钱罐，每个存钱罐的钥匙在另一个存钱罐里，问最少砸烂多少个存钱罐。
如果A罐的钥匙在B罐里，我们连边B->A，表示只要开了B就能开A。然后得到一张无向图，显然在一个强连通分量中的罐子最多只用砸烂一个，而每个强连通分量的罐子有可能被别的强连通分量的罐子打开，所以将这张图缩点，得到一个DAG，显然我们只用砸那些入度为0的强连通分量并且每个分量砸一个就ok了，也就是DAG的叶子节点。
（原来tarjan中，dfn没有记录的必要啊，详见程序。）

BZOJ 1532 : [POI2005]Kos-Dicing

网络流里这个模型太熟了。
首先求最大值最小先二分，然后判定是否可以相互制约使得都在ans场内决出冠军。具体连边就是S向每场比赛连边容量为1，每场比赛向两个人分别连边，容量1。然后每个人向T连边，容量为ans。看看最大流S是否满载。搞定。

bzoj 1098 : [POI2007]办公楼biu

如果把互相有手机号的建边得到一个无向图，那么这个图的补图的连通分量个数就是答案了。因为互相没手机号的必然在同一个连通分量里。但是注意到N（2<=N<=100000）M（1<=M<=2000000） 补图是个非常稠密的图，如果直接做的话会tle或mle。可以用一个链表来优化bfs。链表初始有N个点，bfs每次开一个now[n]数组标记该点是否邻接，然后对于链表中的每个元素若不邻接，就可以加到队列里扩展，同时在链表中删去。这样就是O(n+m)的了。

bzoj 1106 : [POI2007]立方体大作战tet

这个有点贪心的意思，想了半天，首先如果两个数之间还有n个数，那么肯定需要至少n次交换，于是可以用一个树状数组维护，第一次遇到一个数记录位置，然后+1，第二次遇到一个数，答案加上消去这个数所要的交换次数即该位置到第一次出现之间的和，然后-1，扫一遍就ok了。

bzoj 1116 : [POI2008]CLO

可以证明，如果一个连通分量内有>=3个点并且边数>=点数，那么就可以构造一个解。证明链接。

bzoj 1115 : [POI2009]石子游戏Kam

首先差分，然后经过几步转化变成只考虑偶数位上的Nim和就行了。参考详细讲解链接。（其实挺难的。）

bzoj 1102 : [POI2007]山峰和山谷Grz

这个模拟就行了，按照题目要求扫几遍即可。我用了并查集。

BZOJ 1131 : [POI2008]Sta

树形dp吧，让求找一个点使以这个点深度和最小。首先可以随便整出来一棵树，对于每个节点记录down[i]以i为根下面的点的深度和，up[i]以i为根除了下面的那些点的深度和。down[i]好说，直接递推就可以了，问题就是怎样计算up[i]。需要记录一个Sub[i]以i为根的下面那些点的个数。然后就有了下面的转移方程。（ps.#define 下面那些点 子树中的点专业了好多。。） [图片已挂] 输出up[i]+down[i]最小的就行了。其实重要的思想还是把每个节点上面的点和下面的点分开考虑，试图寻找递推关系。

BZOJ 2079 : [Poi2010]Guilds

这个题原题让输出答案，oj上只用判定。判定好说，如果有一个联通分量只有一个点，那么它肯定不会满足要求。如果不是只有一个点，可以随便搞出一个生成树来，然后奇数层一组，偶数层一组，就能满足题意。

BZOJ 2091 : [Poi2010]The Minima Game

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

BZOJ 2096 : [Poi2010]Pilots

优先队列，找最长的串最大最小差值符合题意，可以维护两个队列分别表示最小值和最大值，（最大值递增，最小值递减）当最大值-最小值<=k的时候，添加后面的元素到队列。知道不满足然后就可以求出在当前位置最大扩展的长度，删除当前位置，继续往后扫。然后取max就可以了。　

BZOJ 1100 : [POI2007]对称轴osi [推荐]

神题一个，看着像计算几何题，但是枚举对称轴至少得n^2，然后发现对称轴只能过边的中点，顶点。于是我们可以把这个图形表示成一个角-边序列，复制一倍。然后对称轴就是这个序列的一个长度>=n的回文串。回文串算法嘛，manacher就挺好。

BZOJ 1531 : [POI2005]Bank notes

裸的背包，可以二进制拆分一下。一个物品比如说有n个，可以拆成 1,2,4,8,16…个。
OJ上没有样例，这里附上原题样例。

In:
3
2 3 5
2 2 1
10
Out:
3

样例解释：略。

BZOJ 2084 : [Poi2010]Antisymmetry

根据定义，回文串的长度必定是偶数，然后可以用回文串算法Manacher，因为是“反对称”只需把条件改成!=即可。

BZOJ 2276 : [Poi2011]Temperature !

单调队列，记录最小值递减，然后，队尾不合适的退出，更新答案。 详细

BZOJ 1526 : [POI2005]ban- Bankomat

注意是求满足所有的录像带的串一共有多少种。反着扫一遍，记录每个录像在i之后最早出现某个数字是在什么地方，然后枚举所有可能的编码，判断是否符合这段录像。当某个编码符合的录像数达到n时，ans++。输出ans即可。

BZOJ 1535 : [POI2005]Sza-Template

二分+KMP算法，满足题意的串肯定是该串的一个前缀，同时也是该串的一个后缀，可以用kmp找出这样的所有串，可以证明如果一个串成立，那么比它长的串也成立，然后二分就行了，需要注意一些细节。

BZOJ 2213 : [Poi2011]Difference

如果我们每次枚举两个字母最大最小情况时，很容易想到写出代码里注释的样子。这样是26*26*n的，我们发现枚举不同的之间是没有关联的，所以可以开一个二维数组同时枚举所有的字母，就是 26*2*n的了。然后就可以过了。

BZOJ 2095 : [Poi2010]Bridges

求最大值最小，二分。然后<=的加边，>的不加边，如果有欧拉迹，就成立，没有就不成立。混合图的欧拉回路这个讲的很好。

BZOJ 3060 : [Poi2012]Tour de Byteotia

贪心，两边都大于k的边可以保留用并查集处理一下，然后扫一遍边，如果两个点不在一个集合，那么合并，如果在这个集合，那么必删，可以证明这样是最优的。解决了。

BZOJ 2802 : [Poi2012]Warehouse Store

优先队列，如果现在能买就买，不能买，就扔一件以前买的最贵的买下现在的，然后记录一下买的是哪些，输出即可。

BZOJ 2430 : [Poi2003]Chocolate

诶呀水题，贪心，每次切当前代价最小的。

以上

再难的题也就那几k。