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 个人。如果一节车厢有 3 或 4 个人那么这节车厢会充满快活的空气。。。问至少移动几个人，可以令所有车厢都充满快活的空气。。。（或者无解时输出无解。。）

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[c][1] = 0; FOR_1(i, 2, n){
        REP(c, C) prd[c][i] = prd[c][i-1];
        prd[str[i-1]][i] = i-1;
    }

    REP(c, C) suc[c][n] = n+1; DWN(i, n, 1){
        REP(c, C) suc[c][i] = suc[c][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[c][i0] < l0-_l && r0+_l < suc[c][i0]){
                    if (c == str[i0]) G[lv][i0] = 1, ans0 += ll, FF[l0-_l] -= ll, FF[r0+_l+1] += ll;
                    else F[c][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[c][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

Posted by xiaodao
Category: Codeforces