SRM 622

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