Educational Codeforces Round 150 A~D

c题好难。

A. Game with Board

Problem - A - Codeforces

题意

给定若干个数字1，Alice和Bob每回合合并两个相同的数字，Alice先手。如果谁最先不能合并数字，谁就胜利。

思路

通过推导可以看出\(n<5\)时先手必输，否则先手胜利的策略是取得只剩下两个数字可以合并。

代码

void solve() {
    int n;
    cin >> n;
    cout << (n <= 4 ? "Bob" : "Alice") << "\n";
}

B. Keep it Beautiful

Problem - B - Codeforces

题意

如果一个序列，把可以前若干个元素移到序列后面，如果这时的序列是非递减的，则称原序列是美丽的。

现在给定几个元素和一个初始为空的序列，如果把元素添加到序列后面后，该序列是美丽的，这输出0；如果该添加后的序列不是美丽的，则不添加这个元素，并输出0。

思路

直接模拟即可。

代码

void solve() {
    int q;
    cin >> q;

    vector<int> v(q+1);
    int f = 0, t1 = 0, t2 = INT_MAX;
    for(int i = 1; i <= q; i++) {
        cin >> v[i];
        if(v[i] >= t1 && v[i] <= t2) {
            t1 = max(t1, v[i]);
            cout << 1;
        } else {
            if(v[i] <= v[1] && !f) {
                cout << 1; f++; 
                t1 = v[i]; t2 = v[1];
            } else {
                cout << 0;
            }
        }
    }

    cout << "\n";
}

C. Ranom Numbers

Problem - C - Codeforces

题意

给定一串由A,B,C,D,E组成的字符串，其中A的值为1，B的值为10，C的值为100，D的值为1000，E的值为10000。如果某字符的右边有大于它的字符，该字符的值为负数，否则为正数。最多可以改变其中一个字符，求整个字符串的最大值。

思路

改变一个字符会产生两种情况，一是修改字符使其贡献值增大，二是把字符改小，使其前面字符的贡献值增大。

可以推出第一种是找出每个字符第一次出现的位置，这样可以最大程度上减少前面字符贡献值变为负数的情况，第二种是找出每个字符最后一次出现的位置，最大程度增加字符贡献值变为整数的情况。然后枚举更改字符后的答案，维护其最大值。

代码

const int p[] = {1, 10, 100, 1000, 10000}; 
 
int func(string s) {
    int res = 0, mx = -1;
    for(int i = s.size() - 1; i >= 0; i--) {
        int c = s[i] - 'A';
        if(c < mx) {
            res -= p[c];
        } else {
            res += p[c];
        }
        mx = max(mx, c);
    }
    return res;
}
 
void solve() {
    string s;
    cin >> s;
 
    int ans = func(s);
    vector<vector<int>> pos(5);
    for(int i = 0; i < s.size(); i++) {
        pos[s[i]-'A'].push_back(i);
    }
    for(int i = 0; i < 5; i++) {
        if(pos[i].empty()) continue;
        for(int j = 0; j < 5; j++) {
            s[pos[i][0]] = char('A' + j);
            ans = max(ans, func(s));
            s[pos[i][0]] = char('A' + i);
            s[pos[i].back()] = char('A' + j);
            ans = max(ans, func(s));
            s[pos[i].back()] = char('A' + i);
        }
    }
 
    cout << ans << "\n";
}

D. Pairs of Segments

Problem - D - Codeforces

题意

给定几个区间，去掉几个区间，使剩下的个区间满足：能够成对组合，相互组合的两个区间相交，且每对区间不与其它区间相交。求最少要去掉几个区间。

思路

可以看成求最大不相交区间数量的升级版。

求最大不相交区间数量，可把区间按右端点排序，然后枚举区间。如果枚举区间的左端点小于标记点，则去掉这个区间，否则更新标记点为枚举区间的右端点。可以证明最后得到的区间数量就是最大不相交区间的数量。

本题把每对区间看成一个区间。设last表示目前单个区间的右端点，cut表示前面一个成对区间的右端点，如果枚举区间的左端点小于等于cut，则去掉这个区间，否则如果小于等于last，则答案加一，更新cut为枚举区间右端点，如果大于last，更新last为枚举区间右端点。

代码

void solve() {
    int n;
    cin >> n;
 
    vector<int> l(n), r(n);
    for(int i = 0; i < n; i++) {
        cin >> l[i] >> r[i];
    }
    
    vector<int> v(n);
    iota(v.begin(), v.end(), 0);
    sort(v.begin(), v.end(), [&](int i, int j){return r[i] < r[j];});
 
    int cut = -1, last = -1, ans = 0;
    for(auto i : v) {
        if(l[i] <= cut) continue;
        if(l[i] <= last) {
            ans++;
            cut = r[i];
        }
        else {
            last = r[i];
        }
    }
 
    cout << n - 2 * ans << "\n";
}