> A. 把进程按m种资源分别各自排序，用一个数组记录各进程还有多少种资源没满足。然后m个指针扫一遍。
> B. 用动态树做，复杂度mlogn
> C. 动态规划，n*n*27的状态，O(n^3)复杂度
> D. 以包含关系来建一颗树，即一个圆的儿子是他直接包含的圆。然后从叶子往根遍历一次。
> E. 暴力做
> F. 先做预处理，把不能做边界的边标志出来，并求出左上角到任一点的子矩形里的国家数。然后暴力穷举两个国家，总复杂度1000^2
> G. 贪心，把边按边权从大到小排序，然后顺序尝试添边，如果添加后会变非法，就把这条边丢弃。
> H. 先不考虑旋转，有：{3,1}*{{3,1},{-1,0}}^(n-2)={a,b}，f(n)=a*3-b*2-2。再用Polya定理求本质不同的，由于n很大不能直接用ploya，可以根据循环节长度分为不超过sqrt(n)类，一个类的大小用欧拉公式计算。
> I. 直接广搜
> J. n^2的预处理，n^3的枚举
> K. 概率题。首先考虑以栈中盘子的放置不同作为状态，这些状态间相互的递推关系可以构成一颗树，然后可以从叶子开始向上用代入法消元解方程，最后求得答案。但这样的复杂度是O(2^N)的(因为栈中盘子的放置方案数最多是O(2^N)的)。进一步观察可以发现这棵树有大量重复结构，可以把状态数缩小成N*H个状态(盘子的总厚度*最顶一个盘子)进而消元求解。O(N^2)的递推和O(N^3)的递推都是可以的。

• Re:D怎么利用包含关系建树? (50) zwdant 2008-12-01 00:07:51