某島

… : "…アッカリ~ン . .. . " .. .
October 17, 2013

Codeforces Round #207

Problem A. Knight Tournament

Brief description:

略)

Analysis:

。。直接線段樹了。。(似乎有簡單一些的方法。。但是不願意動腦筋。、、。。
http://codeforces.com/contest/356/submission/4791519

Problem B. Xenia and Hamming

Brief description:

略)

Analysis:

既然要長度相等。那麼肯定是 lcm 的整數倍。。也就是要統計出一段 lcm 的結果就行了。。
考察 gcd = 1 的時候。。那麼顯然每個字元會跑遍每一個位置。之後就能 yy 出一般情況的做法了。。。

I =->{gets.split.map &:to_i}

n, m = I[]; a = gets.chomp; b = gets.chomp
dd = a.size.gcd(b.size); mm = a.size.lcm(b.size); nn = a.size*n; ss = 0
c = Array.new(dd){Array.new(128, 0)}
0.upto(a.size-1){|i|c[i%dd][a[i].ord] += 1}
0.upto(b.size-1){|i|ss += c[i%dd][b[i].ord]}
p nn-ss*nn/mm

http://codeforces.com/contest/356/submission/4810357

Problem C. Compartments

Brief description:

小夥伴們分布在一些車廂中,每節車廂里可以是 0、1、2、3、4 個人。如果一節車廂有 34 個人那麼這節車廂會充滿快活的空氣。。。問至少移動幾個人,可以令所有車廂都充滿快活的空氣。。。(或者無解時輸出無解。。)

Analysis:

顯然 1, 2, 5 時是無解的。。經過一番努力。。我們發現這這些就是無解的全部情況。。顯然要從落單的人開始下手。。
。。設 d = min(c1, c2) 。。顯然這 d 個人是從 c1 -> c2 的。。。之後討論。。
如果 d == c2。。那麼多出來那 c1 個人,肯定三個三個配對。。若有餘數,如果餘數是 1 且有 3 人的。。則再加一否則加二。。。
d == c1 情況類似。

I =->{gets.split.map &:to_i}

def f	
	gets; a = I[]; c1 = a.count(1); c2 = a.count(2); c3 = a.count(3); c4 = a.count(4)
	s = c1+2*c2+3*c3+4*c4; return -1 if (s == 1 || s == 2 || s == 5)

	z = d = [c1, c2].min; c1 -= d; c2 -= d; c3 += d
	if !c1.zero? then
		z += 2*(d=c1/3); c1 -= d*3; c3 += d
		z += c1.zero? ? 0 : (c1 == 1 && !c3.zero? ? 1 : 2)
	elsif !c2.zero? then
		z += 2*(d=c2/3); c2 -= d*3
		z += c2.zero? ? 0 : (c2 == 1 && !c4.zero? ? 1 : 2)
	end

	return z
end

p f()

http://codeforces.com/contest/356/submission/4810189

Problem D. Bags and Coins

Brief description:

構造 n 個結點的森林,使得總的權值和為 s。。
並且以每個結點為根的子樹的權值和恰為 ai

Analysis:

。。。真·傻逼題。。 複雜度是 O(n2/32) 。。。
。。顯然方案滿足所有根結點的 $$!\sum_{i=1}^n a_i = s$$。
。。然後就是一個背包。。。因為需要構造方案。還要嚴格控制平方後面的常數。。。所以好像連 bitset 都沒法用了。。只能手寫。。。
。。那些 40ms 過的。。似乎是 hash 背包 + 奇怪的剪枝。。。。

注意注意注意!。。

  1. 1<<31 is undefined 。。(so always use 1u << 31
  2. x>>32 is undefined 。。(so 特判。。

http://codeforces.com/contest/356/submission/4809700

Problem E. Xenia and String Problem

Brief description:

。。一個子串被稱為是 G-子串。。如果.. .

  1. odd…(長度為奇數
  2. GxG.. (左右兩半都是 G-子串 且相同。。中間是一個任意字元。。於是其實條件 1 多餘。。。。
  3. x 不曾在 G 中出現。

。。給定一段文本,你可以至多修改其中的一個字元,問最大的 G-子串 的長度的平方和。

Analysis:

.首先,G-子串 的長度呈 1、3、7 … 2^n – 1 幾何增長。
顯然可以枚舉長度暴力 hash 先把不修改的統計出來。。。(據出題人說存在不用 hash 的方法。。我猜是改 Manacher。。有待研究。。

設 G[lv][i] 表示以 i 為中心是否構成一個 lv 階的 G 子串。。
。。考慮修改一個字元。。會造成兩種影響。。

第一種對於跨越了這個字元的一組 G-子串現在將會失效,需要計入損失。
。對於那些 准-G 子串。。可能經過一次修改變成 G-子串,得到收益。

前者是一個區間修改,單點詢問的問題。。但是只在最後統計,可以很簡單的離線。
對於後者。。需要在用 hash 得到 G[][] 的時候,順便二分出那兩個不相同的位置。(如果恰有一位不相同的話。。。

const int N = int(1e5) + 9, C = 27, LN = 18;

uLL P[N], S[N]; char str[N]; int prd[C][N], suc[C][N]; int n;
LL F[C][N], FF[N]; bool G[LN][N]; LL ans0;

inline uint h(int l, int r){
    --l; return S[r]-S[l]*P[r-l];
}

inline bool d1(int l1, int r1, int l2, int r2, int &p1, int &p2){

    while (l1 < r1){
        int m1 = l1 + r1 >> 1, m2 = l2 + r2 >> 1;
        if (h(l1, m1) != h(l2, m2) && h(m1+1, r1) != h(m2+1, r2)) return 0;
        if (h(l1, m1) != h(l2, m2)) r1 = m1, r2 = m2; else l1 = m1 + 1, l2 = m2 + 1;
    }

    p1 = l1, p2 = l2;
    return 1;
}

inline int prdd(int i, int p){
    return prd[str[i]][i] == p ? prd[str[i]][p] : prd[str[i]][i];
}
inline int succ(int i, int p){
    return suc[str[i]][i] == p ? suc[str[i]][p] : suc[str[i]][i];
}


int main(){

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

    ans0 = n = strlen(RS(str+1)), P[0] = 1; REP_1(i, n) str[i] -= 'a', P[i] = P[i-1]*C, S[i] = S[i-1]*C+str[i]+1, G[0][i] = 1;

    REP(c, C) prd[1] = 0; FOR_1(i, 2, n){
        REP(c, C) prd[i] = prd[i-1];
        prd[str[i-1]][i] = i-1;
    }

    REP(c, C) suc[n] = n+1; DWN(i, n, 1){
        REP(c, C) suc[i] = suc[i+1];
        suc[str[i+1]][i] = i+1;
    }

    for (int lv=1,lxl=3,l=1,_l=0,p1,p2;lxl<=n;_l=l,l=lxl,lxl=(l<<1)+1,++lv){
        FOR_1(i0, l+1, n-l){
            int l0 = i0-_1(lv-1), r0=i0+_1(lv-1); LL ll = sqr((LL)lxl);
            if (G[lv-1][l0] && G[lv-1][r0] && h(l0-_l, l0+_l) == h(r0-_l, r0+_l)){
                REP(c, C) if (prd[i0] < l0-_l && r0+_l < suc[i0]){
                    if (c == str[i0]) G[lv][i0] = 1, ans0 += ll, FF[l0-_l] -= ll, FF[r0+_l+1] += ll;
                    else F[i0] += ll;
                }
            }
            else if (d1(l0-_l, l0+_l, r0-_l, r0+_l, p1, p2)){
                if (G[lv-1][r0] && prdd(i0, p1) < l0-_l && r0+_l < suc[str[i0]][i0]){
                    F[str[p2]][p1] += ll;
                }
                if (G[lv-1][l0] && prd[str[i0]][i0] < l0-_l && r0+_l < succ(i0, p2)){
                    F[str[p1]][p2] += ll;
                }
            }
        }
    }

    //OT(ans0);

    LL bonus = 0, ff = 0; REP_1(i, n){
        ff += FF[i]; REP(c, C) checkMax(bonus, ff + F[i]);
    }

    OT(ans0 + bonus);
}

http://codeforces.com/contest/356/submission/4814590

綜上所述,我們整理如下:

首先寫字元串 hash 相關。。再者我們需要求每個位置前面一個、和後面一個和它相同的字元的位置。(prd,suc。。
。。因為有修改操作,進一步我們需要求出。每個位置如果它是某個字元時前、後和它相同的位置。。。
ans0 表示不修改時的答案,F[][] 表示修改字元產生的收益,FF[] 統計損失。

d1(l1,r1,l2,r2,p1,p2) 表示是否 [l1, r1] 與 [l2, r2] 這一段只有一個字元不相同,如果是,
則用 p1, p2 帶出兩邊的下標,在討論 p1 覆蓋 p2 和 p2 覆蓋 p1 這兩種情況。
注意因為替換了一個字元,所以 prd 要簡單調整。。

以 p2 覆蓋 p1 為例,這裡寫做 prdd(i0, p1) 表示 p1 這個字元的位置實際上被替換了。。。
注意我們只是簡單的考慮 p1 所在位置的字元被刪去,因為這個時候如果替換的字元產生了新的阻礙那麼在右半段肯定已經發生過了。

External link:

http://codeforces.com/contest/356