Codeforces Round 1014 (Div. 2)

2025-03-30

赛时出了ABCD，这场上了87分，排名691，又是打得还不错的一场。但是其实后面还有四十分钟就不太想看E了，连题都没咋读，等会再好好看一看吧。

比赛链接: https://codeforces.com/contest/2092

感觉这场C是非常简单的一集，D也偏简单的，纯模拟没有任何算法。或许放到几天之前，我可能就不太想写关电脑了，虽然也不一定能写出来。

A

\(gcd(x,y)=gcd(x,y-x)\)

\(gcd(x+k,y+k)=gcd(x+k,y-x)\)

所以最大的可能的最大公因数一定是 \(y-x\) ，且只要让 \(x+k\) 是 \(y-x\) 的倍数，则一定可以有这种情况。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a.begin() + 1, a.end());
    cout << a[n] - a[1] << '\n';
}

B

第一排的奇数位的只能去第二排的偶数位，所以第一排的奇数位的\(1\) + 第二排的偶数位的 \(1\) 数量必须小于等于第二排的偶数位置的数量。

另一边同理。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    string s1, s2;
    cin >> s1 >> s2;
    int cnt1 = 0, cnt2 = 0;
    for (int i = 0; i < n; i++)
    {
        if (s1[i] == '1')
        {
            if (i % 2 == 0)
                cnt1++;
            else
                cnt2++;
        }
        if (s2[i] == '1')
        {
            if (i % 2 == 0)
                cnt2++;
            else
                cnt1++;
        }
    }
    int x = n / 2;
    if (cnt1 > x || cnt2 > n - x)
    {
        cout << "NO\n";
    }
    else
    {
        cout << "YES\n";
    }
}

C

我们假设把所有奇数全都给加到偶数上，那么最后我们数组会有若干个奇数和若干个偶数，我们可以把所有的偶数都给加到1个 \(1\) 上。

也就是说答案会是总和减去 奇数的数量-1 。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), p, q;
    for (int i = 1; i <= n; i++)
    {
        cin >> a[i];
        if (a[i] & 1)
            p.push_back(a[i]);
        else
            q.push_back(a[i]);
    }
    sort(a.begin(), a.end());
    sort(p.begin(), p.end());
    sort(q.begin(), q.end());
    if (p.empty() || q.empty())
    {
        cout << a[n] << '\n';
        return;
    }
    long long ans = 0;
    for (int i = 1; i <= n; i++)
        ans += a[i];
    ans -= p.size() - 1;
    cout << ans << '\n';
}//3 3 4 5 9

D

\(n\) 的规模很小很小，手推一下发现并不需要很多次操作就可以完成，且不合法情况很少。

于是直接模拟，有限放数量少的，不行则放数量第二少的，否则放最多的。若不能操作，则直接退出。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<int> cnt(130);
    string s;
    cin >> s;
    for (int i = 0; i < n; i++)
    {
        cnt[s[i]]++;
    }
    vector<int> a(3);
    a[0] = cnt['L'], a[1] = cnt['I'], a[2] = cnt['T'];
    sort(a.begin(), a.end());
    vector<int> ans;
    auto Ins = [&](char ch)
    {
        for (int i = 0; i + 1 < s.size(); i++)
        {

            if (s[i] != s[i + 1] && s[i] != ch && s[i + 1] != ch)
            {
                s.insert(s.begin() + i + 1, ch);
                cnt[ch]++;
                a[0] = cnt['L'], a[1] = cnt['I'], a[2] = cnt['T'];
                sort(a.begin(), a.end());
                ans.push_back(i + 1);
                return true;
            }
        }
        return false;
    };
    // Ins('T');
    // cerr<<s<<'\n';
    while (1)
    {
        // break;
        if (a[0] == a[2])
            break;
        if (cnt['L'] == a[0])
        {
            if (Ins('L'))
                continue;
            else
            {
                if (cnt['I'] == a[1])
                {
                    if (Ins('I'))
                        continue;
                    else if (Ins('T'))
                        continue;
                }
                else
                {
                    if (Ins('T'))
                        continue;
                    else if (Ins('I'))
                        continue;
                }
            }
        }
        else if (cnt['I'] == a[0])
        {
            if (Ins('I'))
                continue;
            else
            {
                if (cnt['L'] == a[1])
                {
                    if (Ins('L'))
                        continue;
                    else if (Ins('T'))
                        continue;
                }
                else
                {
                    if (Ins('T'))
                        continue;
                    else if (Ins('L'))
                        continue;
                }
            }
        }
        else
        { // T
            if (Ins('T'))
                continue;
            else
            {
                if (cnt['L'] == a[1])
                {
                    if (Ins('L'))
                        continue;
                    else if (Ins('I'))
                        continue;
                }
                else
                {
                    if (Ins('I'))
                        continue;
                    else if (Ins('L'))
                        continue;
                }
            }
        }
        cout << "-1\n";
        return;
    }
    // cerr << s << '\n';
    cout << ans.size() << '\n';
    for (auto x : ans)
        cout << x << '\n';
}

看起来代码很多，但实际上三个差不多，主要是得枚举字符。。当然还有更智慧的写法。