2013-06-16 Robert Zhang
分析:考虑二项式 (x1 + x2) ^ n 其中 x1 ^ m * x2 ^ (n - m) 项的系数是组合数 C(n, m) 多项式 (x1 + x2 + ... + xk) ^ n 可以记为 ((x1 + x2 + ... + x(k - 1)) + xk) ^ n more 继续阅读 »
2013-06-15 Robert Zhang
分析:Stern-Brocot树的每个节点(包括根节点)都是由两个分数生成的,分别记其为left, right。生成规则为: mid.numerator = left.numerator + right.numerator mid.denominator = left.denominator + right.denominator 继续阅读 »
2013-06-15 Robert Zhang
分析:如果n<10,则Stan一步即可轻松获胜;当n>=10时,假设Stan能获胜,那么Ollie的最后一次乘积必须在[ceil(n/9), n)之间。设: lower = ceil(n/9), upper = n 又设在此之前Stan的乘积是p,则Stan必须保证: 继续阅读 »
2013-06-15 Robert Zhang
分析:5.4节《进制及其转换》提到:把一个a进制整数x转化成b进制整数y的“自左向右”方法是:首先求出y的最高位dl (dl + 1) * b ^ k > x >= dl * b ^ k 在本题中令x = 2 ^ e,已知十进制y的高n位,则有: 继续阅读 »
2013-06-14 Robert Zhang
more ```cpp include include define MAX_SIZE 10 using namespace std; typedef long long llt; 继续阅读 »
2013-06-14 Robert Zhang
more ```cpp include include define MAX_SIZE 10 using namespace std; inline vector to_vec(int n) { vector v; v.reserve(MAX_SIZE); while (n) { v.push_back(n % 10); n /= 10; } return v; } 继续阅读 »
2013-06-13 Robert Zhang
分析:此题不难,但特别容易超时!——这正是困难之处:有n个元素的集合的子集共有2^n个,枚举算法的时间复杂度在O(2^n),且本题除枚举外别无他法(NP完全),因此必须尽一切可能性优化,着力在降低计算中n的值(以下1、2项优化)。关键的优化有以下几点(按重要性排列): 继续阅读 »
2013-06-07 Robert Zhang
分析:割点把木棍分成了若干区间,把这些区间从0到n编号,假设从区间i到j的最小代价为f(i, j),则f(0, n)即整根木棍的代价。不妨在稿纸上推演一下,如何从f(0, 1)开始一步步计算得到f(0, 2),f(0, 3)(以下设len(i, j)为区间i到j的长度): 继续阅读 »
2013-06-07 Robert Zhang
分析:此题同Edit Step Ladders类似(至少在解法思路上很相似):把大象按体重递增排序,然后从排序后的最后一只大象开始向前“反攻倒算”,总的时间复杂度在O(n^2)。more 继续阅读 »
2013-06-03 Robert Zhang
分析:此题是图的连通性问题。摄像头都位于图的关节点(articulation point)上。判断点v是否是关节点的简单办法是把v及其附着边从图中删去,然后用dfs或bfs检验图是否连通,若不连通则v是关节点。对图中的点依次做判断即可得出摄像头位置。more需要注意的是:输入的图可能是不连通的,须要把它拆成若干最大连通子图,然后再找出每个子图中的关节点。笔者不得不说,这是一个大坑。 继续阅读 »