Codeforces Round 1011 (Div. 2)

2025-03-22

这场原本有点窃喜，上了65分，但是今天中午直接掉快一百分。。该加训了孩子们。周末打了两天 wzry 。。。

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

比较简单的一集，赛时写出了ABCD，official rank 742。

E 似乎过题人数没有比 D 少很多，之后再看看吧。

A

翻转后如果不相等，那么你一定可以通过一次操作，使得它们的大小关系反过来。

若相等，则为回文串，如果不是全为一样的字符，则一次操作也是够的。

void ChatGptDeepSeek()
{
    int n, k;
    cin >> n >> k;
    string s;
    cin >> s;
    vector<int> cnt(25 + 1);
    for (auto c : s)
        cnt[c - 'a']++;
    if (*max_element(cnt.begin(), cnt.end()) == n)
    {
        cout << "NO\n";
    }
    else
    {
        string t = s;
        reverse(t.begin(), t.end());
        if (k)
            cout << "YES\n";
        else if (s < t)
            cout << "YES\n";
        else
            cout << "No\n";
    }
}

B

有点难受了。我B怎么写了半小时。。。

其实有个简单的思路就是，不管咋样，都把数组合并成长度为 4 的，即把 \([4,n]\) 给合并，就会好讨论很多了。

我的略微有点麻烦。。。

void ChatGptDeepSeek()
{
    /*
    要满足最后一次操作为0
    那么在这前一次 里面不能有0
    在这前两次 就必须要有0

    0 0 -> 1
    0 1 -> 2

    实际上就是把数组里的0变没

    如果有0 就合并他们


    */
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    if (count(a.begin(), a.end(), 0) == n)
    {
        cout << "3\n";
        cout << "3 " << n << '\n';
        cout << "1 2\n";
        cout << "1 2\n";
        return;
    }
    vector<pair<int, int>> ans;
    int l = 0;
    vector<int> b;
    for (int i = 0; i < a.size(); i++)
    {
        if (a[i] == 0)
        {
            int j = i + 1, cnt = 1;
            while (j < a.size() && a[j] == 0)
            {
                j++;
                cnt++;
            }
            if (b.empty())
            {
                if (j == a.size())
                {
                    ans.push_back({1, n - 1});
                    ans.push_back({1, 2});
                    b.push_back(1);
                    break;
                }
                else
                {
                    if (cnt == 1)
                    {
                        ans.push_back({1, 2});
                    }
                    else
                    {
                        ans.push_back({i + 1, i + cnt});
                        b.push_back(1);
                    }
                }
            }
            else
            {
                if (cnt == 1)
                {
                    ans.push_back({b.size(), b.size() + cnt});
                }
                else
                {
                    ans.push_back({b.size() + 1, b.size() + cnt});
                    b.push_back(1);
                }
            }
            i = j - 1;
        }
        else
            b.push_back(1);
    }
    // if (ans.empty())
    //     ans.push_back({1, n});
    if (b.size() > 1)
        ans.push_back({1, b.size()});
    cout << ans.size() << '\n';
    for (auto [x, y] : ans)
        cout << x << " " << y << '\n';
    // cout << '\n';
}

C

\((x+k)+(y+k)=(x+k)\oplus (y+k)\)

对于 \(x+y=x\oplus y\) ，那么 \(x\) 和 \(y\) 必定不能有同为 \(1\) 的位 。所以 \(x\ne y\) 时显然不能成立。

所以有一种很简单的构造方式就是，使得 \(x\) , \(y\) 中较大的一个数字先达到 \(100000\) 的形式，这样它的最高位为 \(1\) ， 而另一个数字只会小于它。

void ChatGptDeepSeek()
{
    /*
    (x+k) + (y+k) = (x+k)^(y+k)


    */
    int x, y;
    cin >> x >> y;
    if (x == y)
    {
        cout << "-1\n";
        return;
    }
    if (x < y)
        swap(x, y);
    long long n = 1LL << (__lg(x) + 1);
    long long k = n - x;
    assert((x + k) + (y + k) == ((x + k) ^ (y + k)));
    cout << k << '\n';
}

D

如果倒着看呢？就是你每次选的时候，数量必须满足 \(cnt(k+1)\le i\) ，只要你能一直满足这个条件，那么就可以一直随便拿。

也就是在 \(k+1\) 之后可以拿第一个，在 \(2k+2\) 之后可以拿第二个。

其实就可以直接贪心了，若当前位置可以多拿一个，则直接把这个拿走。否则比较一下之前拿了的，如果当前的值是比拿了的最小值大的话，那么可以把那个扔掉换成这个。

void ChatGptDeepSeek()
{
    int n, k;
    cin >> n >> k;
    vector<int> d(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> d[i];
    reverse(d.begin() + 1, d.end());
    priority_queue<int, vector<int>, greater<>> pq;
    for (int i = k + 1; i <= n; i++)
    {
        // cerr<<d[i]<<'\n';
        if (1LL * ((int)pq.size() + 1) * (k + 1) <= i)
            pq.push(d[i]);
        else
        {
            pq.push(d[i]);
            // cerr << pq.top() << '\n';
            pq.pop();
        }
    }
    // cerr<<'\n';
    long long ans = 0;
    while (!pq.empty())
    {
        ans += pq.top();
        // cerr<<ans<<'\n';
        pq.pop();
    }
    // cerr<<'\n';
    cout << ans << '\n';
}

E

六百六十六啊，怎么不看题解能写出来的啊。而且没有很久。大概三十多分钟。而且前面又是在进行无效思考。。

速度还是最重要的因素之一，只有简单题速度足够快且保证正确率，才能留下更多空间去思考后面的题，才能有机会写出更多的题目。

实际上如果这题能想到考虑 \(\sum a\) 和 \(\sum b\) 的值的关系，就很好做了。由于是对同一个数字取模，所以 \(sum_a \equiv sum_b \pmod{k}\) 。

所以 \(k \mid sum_a-sum_b\) ，于是我们的 \(k\) 一定是 \(sum_a-sum_b\) 的一个因子，直接进行枚举即可。枚举因子的复杂度是 \(\sqrt{sum_a-sum_b}\) ，\(sum_a-sum_b\) 的最大值大概是 \(10^{10}\) ，但是一个数字的因子的数量实际上是很少的，相比它自身的范围。应该大概是 \(\log n\) 个因子吧。这个不需要证明，你只需要感觉就行，显然比 \(n\) 少很多吧。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    sort(a.begin() + 1, a.end());
    sort(b.begin() + 1, b.end());
    if (a == b)
    {
        cout << "998244353\n";
        return;
    }
    /*
    k的最小的可能的值是 b中最大值+1
    但这远远不够的

    如果b中没有对应的a 那么必然要模了
    并且模了之后 对应的值的数量还不能变的

    那么比k最小值还小的数字 自然不可能会变了
    但这个根本不够

    x%k=A
    suma%k = sumb%k
    k | suma - sumb
    也就是说 可行的 k 的数量是有限的

    值是 1e10 枚举因子范围 1e5
    因子数量应该只有log个
    */
    long long s = 0;
    for (int i = 1; i <= n; i++)
    {
        s += a[i] - b[i];
    }
    if (s < 0)
    {
        cout << "-1\n";
        return;
    }
    auto check = [&](long long x)
    {
        if (x <= b[n] || x > 1000000000)
            return false;
        vector<int> c = a;
        for (int i = 1; i <= n; i++)
            c[i] %= x;
        sort(c.begin() + 1, c.end());
        return c == b;
    };
    for (long long i = 1; i * i <= s; i++)
    {
        if (s % i == 0)
        {
            if (check(i))
            {
                cout << i << '\n';
                return;
            }
            if (check(s / i))
            {
                cout << s / i << '\n';
                return;
            }
        }
    }
    cout << "-1\n";
}