额。。前几天花了点时间A光了Baltic OI 2010的题目。。感觉还是挺有意思的。。
就写个小结吧囧（其实是充数的，官网上有题解的囧。。）。。。
[Baltic2010]Bears
这个题目的二分还是不难想的囧。。假如二分一下可以阻拦在外的长度的话，
一开始禁止区域是个正方形，然后如果有mainstreet伸入里面的话，这些
mainstreet上面的点自然也划入禁止区域，然后注意到如果一个点有两个
方向上都是禁止区域的点的话，那么这个点就可以无压力进入禁止区域，
故其也是禁止区域。。所以禁止区域一定是个矩形。。
然后看就二分+判断（A，B）是否在里面就可以了。。
[Baltic2010]lego
这个题目首先可以发现状态数肯定不会大，然后对于某一个状态首先要符合
输入的条件，如果有些没被看到的话，可以随便染。。
那么似乎好像就可以状态压缩Dp了。。由于每次都要能够放在上一个的上面，
所以要记录当前的层数和最上面一个是什么。。
常数有点小重要，TLE了一次囧。。
[Baltic2010]Pcb
首先按X1排序。。那么找一条最长的递减的链L，显然这个
链上两两不能分在一层，所以最少要|L|的层数，可证这是可行的囧。。
[Baltic2010]Bins
额。。这个题目有点猥琐。。他的意思就是每个数只能跟比它大的数配对，
问前X个跟第X+1..2X个之间能够完全匹配的最大的X是多少。。
设A[t]为前面X个中大于t的数有几个，
B[t]为X+1…2X中大于t的数有几个。。
显然大于t的数只能用大于t+1的数来放，
所以A[t]<=B[t+1]。。用归纳法可以证明这个。。
然后为了判断是否成立，
假设C[t]是前X中t的个数，D[t]是X+1..2X中t+1的个数。。
那么设E[t]=C[t]-D[t]。。可以发现A[t]-B[t+1]的最大值就是E[t]的最大后缀。。
所以使用线段树维护这个就可以了。。每次修改都是O(LogN)的。。
[Baltic2010]candies
额。。这个题目非常的强大。。
首先可以把题目变换一下，变成删掉一个，再添加一个。。
注意如果添加的话，我可以弄一个很大的能弄出的种数*2.。
所以就变成了对每一个，看它删掉之后的种数，找一个最大的。。
首先注意到一般的Dp是这样的
Dp[i][j]=Dp[i-1][j]+Dp[i-1][j-A[i]]…
那么由于物品是对称的，每个都可以看成最后一个，所以
Dp[i-1][j]=Dp[i][j]-Dp[i-1][j-A[i]]…
这样的话对每个物品就可以在O(B)的时间搞出它能弄出来的种数了。。
然后这部分的复杂度就是O(N*B)。。
不过有一点就是显然会溢出，不过也没事，我们只要判是否0就可以了。。
随便找个数mod一下就差不多了。。

第二步就是要找一个最小的数+进去，使得种数*2，
注意到这个数不能是任何两个不相交子集的差，
也就是说不能用A[0],-A[0],A[1],-A[1]….表示出来。。
对这些数用Dp就可以了。。。