某島

… : "…アッカリ~ン . .. . " .. .
July 14, 2012

Codeforces Round #129

Brief description:

Problem A. Little Elephant and Interval:
統計 [l, r] 區間中,首末位相同的數有多少個。
略。([數位DP] 或者直接算?。。

Problem B. Little Elephant and Cards:
略。([Map][貪心]..

Problem C. Little Elephant and Furik and Rubik:
略)[算數]

Problem D. Little Elephant and Retro Strings:
給你一字元串,B 和 W 表示白色和黑色、有 X 表示顏色不確定、給定整數 K。
問有多少種染色方案使得存在兩組不想交的長度為 k 的子串,滿足左串全部是白色、右串全部是黑色。
..

Problem E. Little Elephant and Strings:
給定 n 個串的集合,再給定 k,求每個串分別有多少個子串,是集合中至少 k 個串的子串。

Analysis:

Problem A. Little Elephant and Interval:
..
Problem B. Little Elephant and Cards:
..
Problem C. Little Elephant and Furik and Rubik:
..

Problem D. Little Elephant and Retro Strings:
我們用 F 和 G 分別處理左串和右串。。(方向相反
F1[i]: 恰好以第 i 位結尾,形成長度為 k 的 {BBBBB..} 的數目。
F2[i]: 所有以 i 位結尾,長度 >= k的 {BBBBB..} 串的數目。。
G1[i]: 恰好以第 i 位結尾,形成長度為 k 的 {WWWWW..} 的數目。
G2[i]: 所有以 i 位結尾,長度 >= k的 {WWWWW..} 串的數目。。

Problem E. Little Elephant and Strings:
… ?

const int N = 1000009;

int F0[N], F1[N], G0[N], G1[N]; char s[N];
int L[N], R[N], n, k, k_, l, r;

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
#endif

    RD(n, k); RS(s+1); k_ = k + 1;

	REP_1(i, n) L[i] = L[i-1] + (s[i]=='X');
	DWN_1(i, n, 1) R[i] = R[i+1] + (s[i]=='X');

    l = 0, r = 0; REP_1(i, n){
        if (s[i] == 'X' || s[i] == 'B') ++r; else l = r = i;
        F1[i] = sum(pdt(s[i] == 'X' ? 2 : 1, F1[i-1]), F0[i] = r-l>=k && s[i-k] != 'B' ? dff(pow(2, L[i-k_]), F1[i-k_]) : 0);
    }

    l = n+1, r = n+1; DWN_1(i, n, 1){
        if (s[i] == 'X' || s[i] == 'W') --l; else r = l = i;
        G1[i] = sum(pdt(s[i] == 'X' ? 2 : 1, G1[i+1]), G0[i] = r-l>=k && s[i+k] != 'W' ? dff(pow(2, R[i+k_]), G1[i+k_]) : 0);
    }

    int res = 0; FOR(i, 1, n) INC(res, pdt(F0[i], G1[i+1]));
    OT(res);
}
...

External link:

http://codeforces.com/contest/204/room/12