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 位置的结果即可。。

External link:

https://gist.github.com/lychees/369d5ead82bbb3253e3d

Posted by xiaodao
Category: TopCoder