250. BuildingRoutes
Brief description:
给定一幅完全图。。。。对于任意两点，如果其最近路径可能经过某条道路，则这条道路的拥挤度 + 1.。
。问拥挤度 > K 的道路有多少。。。
Analysis:
。。。直接 Floyd + 暴力 O(n4) 枚举统计。。。
500. Ethernet
给定一颗 n 个结点的边权树，要求将树划分成尽可能少的子树，使得每棵子树的 diameter 都不大于 K。
http://hi.baidu.com/thinking610/item/afdd261dd5b152068fbde4d2
想复杂了。。。可以直接 dfs() 贪心的。。。
900. FibonacciXor
Brief description:
设 g(n) 表示将 n 的 Fibnacci 展开示为二进制数时的值。。
———— 例如。。
9 = F[4] + F[0] = 8 + 1..
g(9) = B(10001) = 17
求 \Xor_{i=l}^r g(i)
。。。n <= 10^15 ...
const int FN = 90;
bitset<FN> B[FN], BB;
LL F[FN];
void f(bitset<FN>& b, LL n){
if (n){
int t = upper_bound(F, F+FN, n)-F-1;
if ((n-F[t]+1)&1) b.flip(t);
f(b, n-F[t]); b ^= B[t]; //f(b, F[t]-1);
}
}
class FibonacciXor{
public:
int find(long long l, long long r) {
REP(i, FN) B[i].reset(); BB.reset();
F[0] = 1, F[1] = 2; FOR(i, 2, FN) F[i] = F[i-1] + F[i-2];
FOR(i, 1, FN) f(B[i], F[i]-1);
f(BB, r), f(BB, l-1); int res = 0;
REP(i, FN) if (BB[i]) INC(res, pow(2, i));
return res;
}
};
Analysis:
。。比数位 DP 简单。。直接讨论高位是否是 1。可以递归到两个子问题。。。而其中一个必然是某个 F[i]-1...
。。于是利用 bitset 缓存所有 F[i]-1 位置的结果即可。。
