题解-Codeforces Global Round 29 (Div. 1 + Div. 2)

C题WA麻了，还是得先找好情况再敲啊。

题目链接

A

分类讨论，答案显而易见，只有-1，2，3三种情况。

void solve() {
    int x, y; cin >> x >> y;
    if(x < y) {
        cout << 2 << "\n";
    } else {
        if(x == y) {
            cout << - 1 << "\n";
        } else {
            if(x >= y + 2 && y != 1) 
	            cout << 3 << "\n";
            else cout << -1 << "\n";
        }
    } 
}

B

推式子，例如
$x = 6$ :

6 4 2 5 2 4 6 3 5 1 3 1
$x = 7$ :
6 4 2 7 2 4 6 5 3 1 7 3 5 1

所以：

if(x 是奇数) {
	[x - 1, x - 3, ..., 2, x, ..., x - 3, x - 1, 
	x - 2, x - 4, ..., 1, x, x - 4, x - 2, 1]
} else {
	[x, x - 2, ..., 2, x - 1, ..., x - 3, x - 5,
	..., 1]
}

void solve() {
    int x; cin >> x;
    vi v(x * 2 + 5);
    if(x & 1) {
        int idx = 1;
        for(int i = x - 1; i >= 2; i -= 2) {
            v[idx] = i; 
            v[idx + i] = i;
            idx ++;
        }
        v[idx] = x;
        v[idx + x] = x;
        idx = x + 1;
        for(int i = x - 2; i > 1; i -= 2) {
            v[idx] = i;
            v[idx + i] = i;
            idx ++;
        }
        v[idx] = 1;
        v[2 * x] = 1;
        for(int i = 1; i <= x * 2; ++ i) 
	        cout << v[i] << " \n"[i == x * 2];
    } else {
        int idx = 1;
        for(int i = x; i >= 2; i -= 2) {
            v[idx] = i; 
            v[idx + i] = i;
            idx ++;
        }
        if(x - 1 != 1) {
            v[idx] = x - 1;
            v[idx + x - 1] = x - 1;
            idx = x + 2;
        }
        for(int i = x - 3; i > 1; i -= 2) {
            v[idx] = i;
            v[idx + i] = i;
            idx ++;
        }
        for(int i = 1; i <= x * 2; ++ i) {
            if(v[i] != 0) 
                cout << v[i] << " \n"[i == x * 2];
            else cout << 1 << " \n"[i == x * 2];
        } 
    } 
}

C

最难蚌的一集， WA * 7

把字符串分成若干段，每段之间没有关联，一段中最多只有1个连续的1, 每段独立计算。再把每段通过那一个1分成若干小份，统计每小份的最大长度和数量，如果当前段的小份的最大长度是1（即全是1），且数量为奇数个，则当前段无解。统计所有段的解的情况，如果首个字符为0, 则将第一个解的情况改为有解，末尾同理。判断整个是否全是有解，有一个段无解，即为NO, 全有解即为YES.

例如：
010101101001

我们分成两段：01010 0100

第一段每小份的长度：1 1 1 ，最大长度是1, 且为奇数个。ans.push_back(0)
第二段每小份的长度：1 2 ，最大长度是2 。ans.push_back(1)

因为s[0] = '0'， 所以ans[0] = 1

因为ans全为1， 故输出YES.

void solve() {
    int n; cin >> n;
    string s; cin >> s;
    vi dp;
    int idx = 0;
    while (1) {
        int cnt = 0, mx = 0;
        while (idx < n && s[idx] == '1') idx ++;
        if (idx >= n) break;
        while (1) {
            int num = 0;
            while (idx < n && s[idx] == '0') {
                idx ++; num ++;
            }
            if(idx == n) break;
            if(num == 1) cnt ++; 
            mx = max(mx, num);
            if (idx != n - 1 && s[idx + 1] == '1') 
                break;
            idx ++; 
        }   
        if (cnt % 2 == 1 && mx == 1) dp.pb(0);
        else dp.pb(1);
    }

    if (s[0] == '0') dp[0] = 1;
    if (s[n - 1] == '0') dp[sz(dp) - 1] = 1;

    for (int i = 0; i < sz(dp); ++ i) {
        if (dp[i] == 0) {
            NO; return;
        }
    }
    YES;
}