Page 1 of 41234

Codeforces Round #263

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/

Page 1 of 41234