xdu 1007：易碎的鸡蛋

这是一道很有意思的题，给你k个相同鸡蛋，有n层楼，高于一定的楼层数扔下鸡蛋会被摔碎，求最少要摔多少次才能确定鸡蛋摔碎的高度。

首先可以看到要是有足够的鸡蛋，至少也要log2(n) 次才能判断，也就是答案不少于log2(n)。开始看上去以为是直接二分，用前n-1个鸡蛋二分尝试，最后一个鸡蛋从剩下的区间往上模拟。实际上这样不对，因为如果鸡蛋没摔碎可以接着用。也就是说可以把划分的区间往下移来省出一点鸡蛋以后用，但要划分多少不好说，所以用dp。dp[i][j]表示i层楼j个鸡蛋的最优解，转移方程就是dp[i][j]=min{max{dp[i-k][j],dp[k-1][j-1]}}。因为直接转移是O(n^3)，n,k<=1000会超时，所以尝试着看一下规律，发现对稍微大一点的鸡蛋数，结果就已经是下界log2(n) ，具体大概是k>log2(n) 就可以达到下限，这一部分直接出解即可。这样O(n^2*log(n))可过。

其实还可以优化，注意到转移决策max{dp[i-k][j],dp[k-1][j-1]}里dp[i-k][j]具有单调性，所以max{dp[i-k][j],dp[k-1][j-1]}应该是中间凹的函数，直接二分/三分即可。这个大概是我所能做的极限了，复杂度是O(n*log(n)^2)。

题解里直接给了OI选手的一篇论文专门讲这道题，最终把时间优化到O(sqrt(n))，实在是太可怕了。其中优化到O(n)的算法大概是使用了类似四边形不等式的方法来加速，感觉勉强可以理解。至于O(sqrt(n))的算法实在是太强了，一时理解不能OrzOrzOrz

 

xdoj 1008：约瑟夫环

简单的链表练习题，直接用链表优化模拟即可。

尝试着用了一下stl::list，只比手写链表慢了一点点，完全可以接受。