为了热身NOIP做了这个比赛。。
Fall 2003
水平有限。。我是沙茶。。
Problem 1:
有限制的背包问题。。
首先把S、B都大于0的选了。。
首先把S、B都小于或等于0的扔掉。。
那么所剩的就是一项正一项负了。。
按照其中的一项从大到小排序。。必然是如下形式。。
S B
＋ －
＋ －
。。。以（S的正负性为划分线）
－  +
－  ＋
。。。
设S已经有了HaveS（来源于先前已经选的东西。。肯定为正。。）
对上下两个分别运行背包。。求出上下两个容量各个选择容量时B和的最大值。。
为了方便把下面的那个背包价格S值全部取反。。这样当上面背包S为和X时。。下面的最多为X＋HaveS个。。
那么可以枚举上面的背包的S值。并用个变量记录下面的最小值。。若B和的最大值加上原来先前选的B的和大于0的话。。
用于更新最优解。。
P.S实际上直接暴力背包也可以。。但我估计要TLE。。进行一些优化之后可以快N多。。
几个小优化。。
首先若上面S的和为SumS，则不需要考虑下面SumS＋HaveS以后的状态。。因为根本不会用到。。
那么上面的的和自然要小。。
故在下面比上面短的时候可以交换上下两个。。（也就是交换S和B的位置）
众所周知DP需要一个序
直接的暴力DP没有考虑到题目的特性而运用了盲目的序。。
而结合题目的特性可以得出更好的序从而更高效的算法俄。。
Problem 2:
好难阿。。应该要用到分治吧。。我不会阿。。教教我阿。。
Promblem 3：
比较水的问题。。首先很明显要求出强连同分量。。然后转化成DAG。。
题目就是求一个节点到其他所有节点都有路径。。
因为没有环。。故一个节点如果有入度那么一定不能到达射向他的那个顶点。。不然就有环了。。
故只有没有入度的节点可能满足条件。。
如果有两个或以上的话。。那么这两个节点必不能互达。。故无解
如果有一个的话。。那个节点就是答案了。。
Problem 4:
OI中数据范围不一样的题目真不是一道题目阿。。
题目就是求N个点中最长的两点间距离。。假如N<1000的话直接暴力就OK了。。可惜N<50000
先求出凸包。。那么最长距离一定在凸包上。。
尽管平均意义上凸包上的点为N的三次方根的数量级。。那么直接枚举凸包上的点对就是N的三分之二次方。。
可惜那是平均意义上的。。很容易就可以构造出所有点都在凸包上的BT数据。。显然不行。。
实际上求凸包上的最远点利用对重点可以做到O（N）但我不会。。
我发现凸包上的点的距离是有单峰性的。。故可以用ternary查找其最值。。是logn的。。
加上排序。。还是NlogN。。勉强过吧。。