Educational Codeforces Round 179 (Rated for Div. 2)¶

2025-06-03

好久没写博客了，但是题还是在写吧。我需要有更充沛的精力，平时还是早点睡吧。。。

这场是打得还行的一场，如果不被hack和fst，那么这将是我目前rank最高的一场。

ABCD都很简单，看通过人数也是这样，E不算太难，但 1k 通过人数也只是正常难度吧，感觉写出来挺幸运的。C题爆int错了一发感觉有点唐，不过影响不大，些许风霜罢了。

A¶

其实我看到题感觉有点慌了，感觉稍微要想一会。观察了下样例，然后想着直接输出 \(2\log{n} + 1\) 试试，然后差了 2，改成 \(2(\log{n} + 1) + 1\) 就过了。发现无 \(n = 0\) 的情况，所以可以直接交。

操作的过程可以是 \(0, 1, 3, 5, 7, ...., x\)，并且每个数字出现 2 次，这样一定操作次数最少， \(x\) 多出现一次，所以答案就是 \(x\) 的有效二进制位数 + 1。

// Date: 2025-06-03
// Time: 22:39:05
void ChatGptDeepSeek()
{
    int x;
    cin >> x;
    cout << 2 * (__lg(x) + 1) + 1 << '\n';
}

结论: 只要最大的两个方块能放得进去，其他的都能放得进去。设 \(cube_i\) 为第 \(i\) 个方块，那么 \(cube_n\) 和 \(cube_{n-1}\) 挨着放，会多出一块空间，这部分空间一定能把 \(cube_{n-2}\) 和 \(cube_{n-3}\) 都放进去。因为 \(f_{n-1} = f_{n-2} + f_{n-3}\)，并且 \(f_{n} = f_{n-1} + f_{n-2}\)，所以 \(cube_{n-1}\) 和 \(cube_{n-2}\) 是可以并排放在 \(cube_{n}\) 上面的。

即若 \(f_{n}\) 和 \(f_{n-1}\) 能放进去，则 \(f_{n-2}\) 和 \(f_{n-3}\) 必能放进去。那么问题其实可以转换成，\(f_{n-2}\) 和 \(f_{n-3}\) 能放进去，它们那个小空间还能接着去放其他的。相当于是一个递归的过程了，所以之后其他的方块也必全都能放得进去。

// Date: 2025-06-03
// Time: 22:46:00
void ChatGptDeepSeek()
{
    int n, m;
    cin >> n >> m;
    vi f(n + 1);
    f[1] = 1, f[2] = 2;
    for(int i = 3; i <= n; i++)
        f[i] = f[i - 1] + f[i - 2];
    for(int i = 1; i <= m; i++){
        array<int, 3> w;
        for(int j = 0; j < 3; j++)
            cin >> w[j];
        sort(all(w));
        if(w[0] >= f[n] && w[2] >= f[n] + f[n - 1])
            cout << 1;
        else cout << 0;
    }
    cout << '\n';
}

C¶

这个就很简单不需要啥证明了，你最终的答案必然是中间留一段不操作，然后把左右全部变成中间的那个值。所以遍历一下就行。

因为爆int，wa了一次，问题不大。

// Date: 2025-06-03
// Time: 22:55:47
void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vi a(n + 1);
    for(int i = 1; i <= n; i++)
        cin >> a[i];
    vc<array<int, 3>> vec;
    int l = 1;
    for(int i = 2; i <= n; i++){
        if(a[i] != a[i - 1]){
            vec.push_back({l, i - 1, a[i - 1]});
            l = i;
        }
    }
    vec.push_back({l, n, a[n]});
    ll ans = LNF;
    for(auto [l, r, val] : vec)
        cmin(ans, 1LL * (l - 1) * val + 1LL * (n - r) * val);
    cout << ans << '\n';
}

D¶

肯定选出来的楼层必须是若干个最大和最小值，每个人可以用两个楼层来回跑。我们分配的顺序其实不太重要，因为你不管咋样都是 \(n\) 个数字 - \(n\) 个数字，只要分配了值，顺序就不会影响结果的。

// Date: 2025-06-03
// Time: 23:04:32
void ChatGptDeepSeek()
{
    int n, m;
    cin >> n >> m;
    vi a(m + 1);
    for(int i = 1; i <= m; i++)
        cin >> a[i];
    sort(ALL(a));
    for(int i = 1, j = 1; i <= n; i += 2, j++){
        vi ans(6);
        for(int k = 0; k < 6; k++)
            ans[k] = (k & 1) ? a[j] : a[m - j + 1];
        for(auto x : ans)
            cout << x << ' ';
        cout << '\n';
        reverse(all(ans));
        if(i + 1 <= n){
            for(auto x : ans)
                cout << x << ' ';
             cout << '\n';
        }
    }
}

E¶

像这种题，其实就是一个贪心，我们不可能做到在线处理。所以可以拿 set 存一下操作，其实我刚开始是尝试 queue 装的，但是不太行。

考虑一下如何操作，我们肯定是遍历字符串，前面的能改小那就一定要修改，因为我们是要最小字典序。

如果 \(s_i \ne a\) ，那么我们就看有没有让 \(s_i\) 变成 \(a\) 的操作；如果没有，那就看有没有让 \(s_i\) 变成另一种字符，且另一种字符有变成 \(a\) 的操作，并且需要满足顺序关系，即先改成别的再改成 \(a\)，所以第一种操作肯定尽量在前面比较好，第二种操作并非越大越好，因为可能导致之后用不了，所以用 set 二分来找。

若两种操作都无法进行，则如果 \(s_i\) 是 \(c\)，那我们就看能不能把它变成 \(b\)。

然后也就是说咱们有两种方式把不等于 \(a\) 的字符修改成 \(a\)，我本来在想它们会不会没有优先级的关系。但是这里，肯定是能用第一种方式修改就用第一种方式修改，因为你第一种修改的那个操作，你留着也没啥用，在前面用了肯定不会亏。你用第二种可能会导致另一种字符后面不能变成 \(a\)。那么显然第一种肯定是用尽量后面的操作。

然后很简单了吧。

// Date: 2025-06-03
// Time: 23:16:16
void ChatGptDeepSeek()
{
    int n, q;
    cin >> n >> q;
    string s;
    cin >> s;
    vc<vc<set<int>>> op(3, vc<set<int>>(3));
    for(int i = 1; i <= q; i++) {
        char x, y;
        cin >> x >> y;
        op[x - 'a'][y - 'a'].insert(i);
    }
    for(int i = 0; i < n; i++){
        if(s[i] == 'a'){
            cout << s[i];continue;
        }
        int x = s[i] - 'a'; 
        if(op[x][0].size()){
            s[i] = 'a';
            op[x][0].erase(op[x][0].begin());
        }else{
            if(op[x][3 - x].size() && op[3 - x][0].size()){
                int small = *op[x][3 - x].begin();
                auto it = op[3 - x][0].upper_bound(small);
                if(it != op[3 - x][0].end()){
                    op[x][3 - x].erase(op[x][3 - x].begin());
                    op[3 - x][0].erase(it);
                    s[i] = 'a';
                    cout << s[i];continue;
                }
            }
            if(3 - x < x && op[x][3 - x].size()){
                op[x][3 - x].erase(prev(op[x][3 - x].end()));
                s[i] = 'b';
            }
        }
        cout << s[i];
    }
    cout << '\n';
}

Educational Codeforces Round 179 (Rated for Div. 2)¶

A¶

B¶

C¶

D¶

E¶