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/

HDU 3948. The Number of Palindromes

Brief description:

。。。 SPOJ 705. New Distinct SubstringsURAL 1297. Palindrome 的結合。。。。
求一個字元串中,迴文子串的個數(內容相同,位置不同的算一個)。
。。。時隔這麼久,再做一遍依然覺得這是一道不可多得的好題。。。

Analysis:

。。。這個題有兩種風格迥異的做法。後綴數組凹和 Hash 亂搞。。。
。。。兩種做法都有可取之處、可以互相借鑒。
。。。對於迴文子串問題。我們知道經過 Interleave 之後。($.a.a.a.a. )
。。就不需要討論迴文串長度的奇偶了。。(這樣得到的答案需要 / 2。。因為每種迴文串(包括空串)都會多計數一次。。)
。。下面的做法都默認這一點。。

演算法一:後綴數組

我們首先回憶 SPOJ 705. New Distinct Substrings。。。

在這個題中。。我們從左往右掃描每個後綴,並統計所有前綴在 sa[i] 的貢獻。
。這個數值是: n-sa[i]-h[i]。只所以要減去 h[i] 是因為這些串之前已經被統計過,避免重複計數。

再回憶 URAL 1297. Palindrome 。。。(僅討論奇數長度的迴文子串)。。。

在那個題中。。我們檢查所有所有 lcpp(i, n-1-i) 。。從中選出答案最大的即可。。。
而現在我們需要完成計數。。我們類比前面一個題。。將所有 lcpp(i, n-1-i) 取出。。
。。。形成一個新的 SA。。。在得到 h[]。。我們就可以如法炮製。。
而我們可以很方便的得到新的 SA。。。。

...
int hh[N], oo[N]; bool cp(int a,int b){
    int t = lcpp(a, b);
    if (t <= hh[a]) return t <= hh[b] ? r[a]<r[b] : 0;
    else return t <= hh[b] ? 1 : hh[a]<hh[b];
}
...
REP(i, nn) hh[i] = lcpp(i, n-1-i), oo[i] = i; sort(oo, oo+nn, cp);
...

。。當 t <= hh[a] && t <= hh[b] 時。。我們就可以直接用原 SA 中的 rank 數組完成比較(因為這兩個串在t+1位置已經分出勝負)。其他情況類似。。。

http://vjudge.net/vjudge/problem/viewSource.action?id=2707432

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

const int N = int(4e5) + 9, Z = 256;

int a[3*N], sa[3*N], r[N], h[N];
int C[N], key[N], t1[N], t2[N]; char s[N], _s[N];
int n, _n;

inline void rs(int *x, int *y, int *sa, int n, int m){
    REP(i, n) key[i] = i[y][x];
    memset(C, 0, sizeof(C[0]) * m);
    REP(i, n) ++C[key[i]];
    FOR(i, 1, m) C[i] += C[i-1];
    DWN(i, n, 0) sa[--C[key[i]]] = y[i];
}

void da(int a[], int sa[], int n, int m){
    int *x = t1, *y = t2;
    memset(C, 0, sizeof(C[0]) * m);
    REP(i, n) ++C[x[i] = a[i]];
    FOR(i, 1, m) C[i] += C[i-1];
    DWN(i, n, 0) sa[--C[x[i]]] = i;
    for (int l = 1, p = 1; p < n; l <<= 1, m = p){
        p = 0; FOR(i, n-l, n) y[p++] = i;
        REP(i, n) if (sa[i] >= l) y[p++] = sa[i] - l;
        rs(x, y, sa, n, m), swap(x, y), x[sa[0]] = 0, p = 0; FOR(i, 1, n)
            x[sa[i]] = (y[sa[i]] == y[sa[i-1]] && y[sa[i]+l] == y[sa[i-1]+l]) ? p : ++p;
        ++p;
    }
}

#define F(x) ((x)/3+((x)%3==1?0:tb))
#define G(x) ((x)<tb?(x)*3+1:((x)-tb)*3+2)
int c0(int *r,int a,int b)
{return r[a]==r[b]&&r[a+1]==r[b+1]&&r[a+2]==r[b+2];}
int c12(int k,int *r,int a,int b)
{if(k==2) return r[a]<r[b]||r[a]==r[b]&&c12(1,r,a+1,b+1);
 else return r[a]<r[b]||r[a]==r[b]&&key[a+1]<key[b+1];}

void dc3(int a[], int *sa, int n, int m){
    int i, j, *an=a+n, *san=sa+n, ta=0, tb=(n+1)/3, tbc=0, p;
    a[n] = a[n+1] = 0; REP(i, n) if (i%3) t1[tbc++]=i;

    rs(a+2,t1,t2,tbc,m), rs(a+1,t2,t1,tbc,m), rs(a,t1,t2,tbc,m);
    p = 0, an[F(t2[0])] = 0; FOR(i, 1, tbc)
        an[F(t2[i])] = c0(a,t2[i-1],t2[i]) ? p : ++p;

    if (++p < tbc) dc3(an,san,tbc,p);
    else REP(i, tbc) san[an[i]] = i;

    REP(i, tbc) if(san[i] < tb) t2[ta++] = san[i] * 3;
    if (n%3==1) t2[ta++] = n-1; rs(a,t2,t1,ta,m);
    REP(i, tbc) key[t2[i]=G(san[i])] = i;

    for(i=0,j=0,p=0; i<ta && j<tbc; p++)
        sa[p]=c12(t2[j]%3,a,t1[i],t2[j]) ? t1[i++] : t2[j++];
    for(;i<ta;p++) sa[p]=t1[i++]; for(;j<tbc;p++) sa[p]=t2[j++];
}

void print_sa(){
    REP_1(i, n){
        cout << sa[i] << ": ";
        FOR(j, sa[i], n) putchar(a[j]);
        puts("");
    }
}

int get_h(){
    REP_1(i, n) r[sa[i]] = i;
    int k = 0; for (int i = 0; i < n; h[r[i++]] = k){
        if (k) --k; for (int j = sa[r[i]-1]; a[i+k] == a[j+k]; ++k);
    }
}

const int LV = 21; int ST[LV][N];
#define cmp(a,b)(h[a]<h[b]?a:b)
int lcp(int l, int r){
    int lv = lg2(r-l); ++l,++r;
    return min(h[ST[lv][l]], h[ST[lv][r-_1(lv)]]);
}


int lcpp(int l, int r){
    //if (l == r) return nn-l;
    l = ::r[l], r = ::r[r]; if (l > r) swap(l, r);
    return lcp(l, r);
}
void get_lcp(){
    REP_1(i, n) ST[0][i] = i;
    for (int lv=1;_1(lv)<=n;++lv)
        for (int i=1;i+_1(lv)<=n+1;++i)
            ST[lv][i] = cmp(ST[lv-1][i], ST[lv-1][i+_1(lv-1)]);
}
#undef cmp


int hh[N], oo[N]; bool cp(int a,int b){
    int t = lcpp(a, b);
    if (t <= hh[a]) return t <= hh[b] ? r[a]<r[b] : 0;
    else return t <= hh[b] ? 1 : hh[a]<hh[b];
}

int main(){

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

    Rush{

        RS(_s); int _n = strlen(_s);

        REP(i, _n) s[2*i] = '.', s[2*i+1] = _s[i]; int nn = 2*_n+1; s[nn-1] = '.';
        n = 0; REP(i, nn) a[n++] = s[i]; a[n++] = '$';

        DWN(i, nn, 0) a[n++] = s[i]; a[n] = 0; dc3(a,sa,n+1,Z); get_h(); get_lcp();
		//print_sa();

		REP(i, nn) hh[i] = lcpp(i, n-1-i), oo[i] = i; sort(oo, oo+nn, cp);

        int z = 0, i1; REP(ii, nn){
            int i = oo[ii]; z += hh[i];
            if (ii) z -= min(hh[i], hh[i1], lcpp(i, i1));
            i1 = i;
        }
        OT(z/2);
	}
}

演算法二:Manacher + Hash

注意到不同 Palindromes 的總數是 O(n) 的。。所以可以用 Manacher + Hash 暴力。。。方法是枚舉每個迴文中心,按照迴文半徑從大到小利用字元串 Hash 枚舉迴文串,當出現已經出現過的迴文串是直接 break; 掉。。(更小的迴文串一定也出現過。。)

(。。這種方法還是比較危險。。。最好用一些方法減少衝突的機會。。)
(。奇偶長度分開討論,不放進相同的 Hash 表裡。。)
(。開 uLL。。。)
(。雙 hash(多取幾個模或者 + 長度信息)。。。)

實際中應該 3 的效果最穩定。。。

http://vjudge.net/vjudge/problem/viewSource.action?id=2706937

External link:

http://hi.baidu.com/lccycc_acm/item/70cf7e3f389ddd5881f1a7d3

SPOJ 744. Longest Permutation

http://www.spoj.com/problems/LPERMUT/

Brief description:

給出一個序列,求最大的 mx,使得存在一個長度為 mx 的連續子序列,使其恰好為 1..mx 的一個排列。

Analysis:

好題。。。Vijos1381 數據太弱,正解應是 O(n) 。

盡量避免使用數據結構。。。我們需要充分利用排列的性質。。。
區間 [l, r] 恰好是 1..len (len = r-l+1)的排列的充分必要條件是:

  • [l, r] 區間的數兩兩不同。
  • s[r]-s[l+1] = 1+2+…+len。。。

為了確保區間中的數字兩兩不同。。。我們設 l[i] 為 i 向左最長可以延伸的距離。。(邊界設 l[0] = 0, l[n+1] = n+1。。)
。。那麼有 l[i] = max(l[i], p[a[i]]+1)。。。(p[a[i]] 是上一個 a[i] 的位置。。。(也可以用 two point 得到這個東西。。。。

void upd(int l, int r, int len){
    if (len < ans) return;
    if (::l[r] <= l && (s[r]-s[l-1])*2 == (1+len)*len) ans = len;
}

。序列被 1 分割成了一些小的區間。。(不能包含兩個相同的 1。。。)。。

____ 1 ____ 1 _________ 1 _____

我們枚舉每個 1.。。討論區間中最大的數字 mx 出現在 1 的左邊還是右邊。。對稱處理。。
。。考慮左邊。。

        for (int j=i-1,mx=1;l[i]<=j;--j){
            checkMax(mx, a[j]);
            upd(j,j+mx-1,mx);
        }

由於 upd() 過程是 O(1) 的。。所以整個演算法是 O(n) 的。。。

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

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

int a[N], s[N], l[N], p[N], n, ans;

void upd(int l, int r, int len){
    if (len < ans) return;
    if (::l[r] <= l && (s[r]-s[l-1])*2 == (1+len)*len) ans = len;
}

int main(){

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

    REP_1_C(i, RD(n)) s[i] = s[i-1] + RD(a[i]);

    RST(p); l[0] = 0; REP_1(i, n){
        l[i] = max(l[i-1], p[a[i]]+1); p[a[i]] = i;
        //cout << l[i] << " ";
    }
    l[n+1] = n+1;

    //puts("");

    REP_1(i, n) if (a[i] == 1){

        upd(i, i, 1);

        for (int j=i-1,mx=1;l[i]<=j;--j){
            checkMax(mx, a[j]);
            upd(j,j+mx-1,mx);
        }

        for (int j=i+1,mx=1;l[j]<=i;++j){
            checkMax(mx, a[j]);
            upd(j-mx+1,j,mx);
        }
    }

    OT(ans);
}

Codeforces Round #129 (Div. 1) Problem E. Little Elephant and Strings

http://codeforces.com/problemset/problem/204/E

Brief description:

給定 n 個串。。問對於每一個字元串,有多少它的子串,可以至少匹配 k 個字元串。(包含自身)

Analysis:

後綴數組

演算法1. 二分 + 可持久化線段樹

首先當然還是要把所有串拼一起跑後綴數組。。。以aaa$aba$aaa 為例

考察第一個串。。記作 s0 = aaa 。。。我們枚舉起始位 x。。
。。設 f(x, len)。。表示 。。。s0[x, x+len] 這個子串。。是否出現在了 k 個子串中。
。。。(。我們希望求最大的 len。。。。顯然 len 越長對這個性質越不利。。
。。。(考慮二分。。。

$aaa 
$aba$aaa 
a 
a$aaa 
a$aba$aaa 
aa 
aa$aba$aaa 
aaa 
aaa$aba$aaa 
aba$aaa 
ba$aaa  

。。對於任意一個 xlen。。。
。。我們需要在後綴數組中,找到最大的包含 x[l, r] 區間。。滿足 lcp(l, r) ≥ len

。。而這又是一個二分過程。。。(。。這裡需要用到 SA 的一個性質。。然後對於任一個串 Plcp(P, SA[i]) 是單峰的。
。。找到 [l, r] 區間後。。。就是。。。。

。。。判斷這個區間的後綴出現在了幾個不同的字元串中。。。
。。。而這個是個可持久化線段樹的入門題。。(參見 SPOJ Dquery 。。

。。。這樣這個題我們就得到了最傻逼的做法。。。複雜度 $O(nlog^2n)$。
http://codeforces.com/contest/204/submission/4545205

演算法 2. two-point
http://www.cppblog.com/hanfei19910905/archive/2012/07/26/185139.html

。。。上面的做法中。可持久化線段樹。未免有點 overkill。。注意畢竟只是詢問是否 >= k。。。
。而這個可以通過 two-point 離線搞出對於每個左端點。最早的合法位置。。。
具體做法是 prd[], suc[] 分別表示左右第一個與 b[i] 相同的位置。。

int last[N], prd[N], suc[N];

兩遍循環。。

    FOR_1(i, nn, n) prd[i] = last[bb(i)], last[bb(i)] = i;
    REP_1(i, nn) last[i] = n + 1;
    DWN_1(i, n, nn) suc[i] = last[bb(i)], last[bb(i)] = i;

之後 two-point。。
(l 增大的時候。。如果 suc[l] > r 。。c -= 1
(r 增大的時候。。如果 prd[++r] < l。。則 c += 1 [cpp] for(int l=nn,r=nn-1,c;l<=n;c-=(suc[l++]>r)){ if (r<l) r=l,c=1; while(c<k&&r<=n) if(prd[++r]<l)++c; if (c<k){n=l-1;break;} last[l] = r; } [/cpp] 其他地方不變。。。。。複雜度依舊是 O(nlog^2n) http://codeforces.com/contest/204/submission/4544775 演算法 3. 標記 。。為了杜絕掉二分的過程。。。我們注意到上面 two-point 得到一組最小的合法 (l, r, lcp) 的時候。。。 。。可以沿途打上事件標記。。。用掃描線的方法。弄一個平衡樹。。每次取出最大的 lcp 好像就行了。。 http://hi.baidu.com/wyl8899/item/04772d462eeb6797823ae16d ..似乎已經做完了么...其實被坑了,樣例2就可以把這個做法擼死。 究其原因,是存在某個k,他的真正可用的最大值並不能被上面所述的方法更新到。 這就坑爹了..因為能更新到k的最大值的那個區間,假設是[x,y'],會出現y'>y(使得rank為x..y的後綴分屬K個串的最小y值)的情形。

。。然而這點也正是這題最精彩的地方。。。因為對於一組標記 (l, r, lcp) 來說。。
。。。r 之後並不代表這個標記就完全失效了。。而是以這個時刻開始。。。
。。隨著時間的流逝。。產生衰減。。(說的神乎其神的。。具體來說就是每次 checkMin(delay, height[i])。。

因此。。我們每次除了要取出平衡樹中的最大值以外。。還需要那些過了 「保質期」 的標記中的最大值。。
。。。然後從這兩者之間。取最大值。。。。

。。 平衡樹內的標記。。涉及增刪操作。。最好的方法使用 multiset 實現。。。
。。 平衡樹以外的標記。。只需保留一個最大值即可(記作 delay)。。然後隨著時間的推移。每次 checkMin(delay, height[i])。。
http://codeforces.com/contest/204/submission/4544928

。。除去不多的幾次平衡樹操作。。這個演算法的複雜度已經很接近 O(n) 了。。而且非常好寫。。
。。。。是一個優秀的演算法。

演算法 4. 後綴自動機
https://www.13331.org/205.html
http://codeforces.com/contest/204/submission/2579006

——————
普通並查集。。。
http://codeforces.com/contest/204/submission/4601790 (280ms。。
加按秩合併。。
http://codeforces.com/contest/204/submission/4601803 (248ms。。