Teza Round 1 (Codeforces Round 1015, Div. 1 + Div. 2)

打得不是很好的一把，做出C题的人一大半都做出了D，我没写出来。这个D确实挺简单的。

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

A

直接猜就行， $n$ 为偶数时一定不行，为奇数时可以。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    if (n & 1)
    {
        // n 1 2
        cout << n << " ";
        for (int i = 1; i <= n - 1; i++)
            cout << i << " ";
        cout << '\n';
    }
    else
        cout << "-1\n";
}

B

$gcd([a_{i+1},a_{i+2},...,a_n]\le min([a_{i+1},a_{i+2},...,a_n])$ , 所以整个数组的最小值只能放在前半部分。

我们可以取所有的最小值的倍数的 $gcd$ ，若不等于最小值，则不可能存在合法的方案。

void ChatGptDeepSeek()
{
    int n;
    cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    sort(a.begin() + 1, a.end());
    ll g = 0;
    for (int i = 2; i <= n; i++)
        if (a[i] % a[1] == 0)
            g = __gcd(g, a[i]);
    if (g == a[1])
        cout << "Yes\n";
    else
        cout << "No\n";
}

C

发现如果有 $a_i=x $ , $b_i=y$ ，则必须存在 $a_j=y$ ， $b_j=x$ ，我们把这样对称的点放到对称的位置即可。

只有 $n$ 为奇数时，必须出现一个 $a_i=b_i$ 的位置。

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];
    }

    /*
    必然是有 x y
    就會有 y x 不然就不行
    若n為奇數 則肯定會有一個位置兩邊是相同的 這個一定要放在中間
    */
    vector<int> p1(n + 1), p2(n + 1);
    for (int i = 1; i <= n; i++)
    {
        p1[a[i]] = i;
        p2[b[i]] = i;
    }
    {
        int cnt = 0;
        for (int i = 1; i <= n; i++)
        {
            if (a[i] == b[i])
                cnt++;
            if (p1[b[i]] != p2[a[i]])
            {
                cout << "-1\n";
                return;
            }
        }
        if ((n & 1) && cnt > 1)
        {
            cout << "-1\n";
            return;
        }
        if ((n % 2 == 0) && cnt)
        {
            cout << "-1\n";
            return;
        }
    }
    vector<pair<int, int>> ans;
    if (n & 1)
    {
        for (int i = 1; i <= n; i++)
        {
            if (a[i] == b[i])
            {
                if (i != (n + 1) / 2)
                {
                    ans.push_back({i, (n + 1) / 2});

                    swap(a[i], a[(n + 1) / 2]);
                    swap(b[i], b[(n + 1) / 2]);
                    p1[a[i]] = i;
                    p2[b[i]] = i;
                    break;
                }
            }
        }
    }
    for (int i = 1; i <= n / 2; i++)
    {
        int j = n - i + 1;
        if (b[j] != a[i])
        {
            int k = p1[b[i]];
            // swap(k,j)
            swap(a[j], a[k]);
            swap(b[j], b[k]);
            ans.push_back({k, j});
            p1[a[k]] = k;
            p2[b[k]] = k;
        }
        // for (int j = 1; j <= n; j++)
        //     cerr << a[j] << " \n"[j == n];
        // for (int j = 1; j <= n; j++)
        //     cerr << b[j] << " \n"[j == n];
    }
    // {
    //     vector c = a;
    //     reverse(c.begin() + 1, c.end());
    //     assert(c == b);
    // }
    cout << ans.size() << '\n';
    for (auto [l, r] : ans)
        cout << l << " " << r << '\n';
}

D

我们如果能将数组分成 $m+1$ 段，且每一段的长度大于等于 $k$ ，那么答案就会是每一段的长度。否则答案不可能大于 $n-mk<k$ ，可以构造成每段都是 $[0,k-1]$ ，这样可以保证答案取到 $n-mk$ 。

void ChatGptDeepSeek()
{
    int n, m, k;
    cin >> n >> m >> k;

    for (int i = 0; i < n; i++)
        cout << i % (n - m * k < k ? k : n / (m + 1)) << " \n"[i + 1 == n];
}