Problem B. Appleman and Tree

Brief description:

给定一棵有根树，每个点有黑白两种颜色，问有多少种树的划分方案，
使得每个联通块中都恰好有一个黑色结点。

Analysis:

树 DP，子树合并。设：

• f[u] 表示以 u 为根的子树中，经过划分过后，与 u 相连的联通块恰好包含一个黑色结点的方案数。
• g[u] 表示以 u 为根的子树中，经过划分过后，与 u 相连的联通块。。。不包含黑色结点的方案数。

转移讨论是否切割 (u, v) 这条边即可。

void dfs(int u = 0){
    ECH(it, adj[u]){
        dfs(v);
        f[u] = f[u]*(f[v]+g[v]) + g[u]*f[v];
        g[u] *= (f[v]+g[v]);
    }
}

http://codeforces.com/contest/461/submission/7612452

C:

Brief description:

给定一张纸，支持两个操作：。
。。沿某个位置对折。
。。询问某个区间纸张的体积。

Analysis:

树状数组。对于折叠操作，我们总是枚举较短的一部分，加到较长的一部分中去。
每个位置只会用来合并一次。总复杂度 O(nlogn)。。

具体说来我们需要记录 ll, rr, rev 三个值。。
分别表示两侧的偏移，以及是否翻转。。。

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;

namespace BIT{
    int C[N], n;
    void Add(int x, int d){
        for (;x<=n;x+=low_bit(x)) C[x] += d;
    }
    int Sum(int x){
        int z=0;for (;x;x^=low_bit(x)) z += C[x];
        return z;
    }
    int Sum(int l, int r){
        return Sum(r) - Sum(l-1);
    }
    int At(int x){
        int z=C[x],p=low_bit(x);for (--x;x&&low_bit(x)<p;x^=low_bit(x)) z -= C[x];
        return z;
    }
} using namespace BIT;

bool rev; int ll, rr;


int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

#define len (rr-ll+1)
#define pp (2*p)

    REP_1_C(i, RD(n)) Add(i, 1); ll=1,rr=n;rev=0; Rush{
        if (RD()==1){ // Fold
            int p; RD(p); if (pp<=len){
                if (!rev){
                    REP_1(i, p) Add(ll+pp-i, At(ll+i-1)); ll += p;
                }
                else{
                    REP_1(i, p) Add(rr-pp+i, At(rr-i+1)); rr -= p;
                }
            }
            else{
                rev ^= 1; p=len-p; if (!rev){
                    REP_1(i, p) Add(ll+pp-i, At(ll+i-1)); ll += p;
                }
                else{
                    REP_1(i, p) Add(rr-pp+i , At(rr-i+1)); rr -= p;
                }
            }
        }
        else{ // Query
            int a, b; RD(a, b);
            OT(rev ? Sum(rr-b+1, rr-a) : Sum(ll+a, ll+b-1));
        }
    }
}

http://codeforces.com/contest/461/submission/7612792

D：

1   2   3
 12  23
2  123  2
 23  12
3   2   1

  1  2
1  12  2
 12  12
2  12  1
  2  1

const int N = int(2e6) + 9;

int n;

namespace DSU{ // Disjoint Set Union
    int P[N], R[N];
    inline void Make(int x){
        P[x] = x, R[x] = 0;
    }
    inline int Find(int x){
        return P[x] == x ? x : P[x] = Find(P[x]);
    }
    inline void Unionn(int x, int y){
        if (R[x] == R[y]) ++R[x];
        else if (R[x] < R[y]) swap(x, y);
        P[y] = x;
    }
    inline void Union(int x, int y){
        int xx = Find(x), yy = Find(y);
        if (xx == yy){
            return;
        }
        else{
            Unionn(xx, yy);
        }
    }

    void Union(int x, int y, int z){
        if (z) Union(x,y+n+2),Union(x+n+2,y);
        else Union(x,y),Union(x+n+2,y+n+2);
    }

    inline void Init(int n){
        REP(i, n) Make(i);
    }
} using namespace DSU;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    RD(n); Init(2*(n+2)); Rush{
        int a, b; RD(a, b); int u = abs(a-b), v = n-1 - abs(a+b-n-1);
        if (u > v) swap(u, v);
        Union(u, v+2, RC()=='o');
    }

    REP(i, n+2) if (Find(i) == Find(i+n+2)){
        puts("0");
        return 0;
    }

    int rk = -2; REP(i, n+2) if (Find(i) == i) ++rk;
    cout << pow(2, rk) << endl;
}

E:
dp[i][j][k]：起始i终止j需要2^k次的最短长度- –

但是 SAM 中状态太多怎么办？。。。
通过预处理出起始 x 终止 y 的最短不在 SAM 中的串。。。可以将 i, j 改成字符集。。。

External link:

http://ftiasch.github.io/blog/2014/08/27/codeforces-round-263/

Posted by xiaodao
Category: Codeforces, 日常