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