Page 1 of 212

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。。

Page 1 of 212