Codeforces Round 1015 (Div. 12) A-E 题解

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

A - Max and Mod

Question

给定一个整数 $n$，你需要构造一个长度为 $n$ 的排列，满足

• 对于 $\mathrm{\forall }i,2\le i\le n$，$max(p_i,p_{i-1})\equiv i-1(\mathrm{mod}i)$

如果无解则输出 $-1$

Solution

当$n$是奇数时，我们可以构造 $p=[n,1,2,\dots ,n-1]$

• 对于$i=2$，$max(p_1,p_2)=n$并且$nmod2=1$
• 对于$i\ge 3$，$max(p_{i-1},p_i)=i-1$并且$(i-1)modi=i-1$

试证明当 $n$ 是偶数时没有解决方案。显然， $n$ 不能放置在 $p_1,p_2$ 或 $p_n$

如果 $n$ 放置在位置 $3\sim n-1$，让 $x$ 为 $n$ 的位置，则我们有$max(p_{x-1},p_x)=max(p_x,p_{x+1})=n$

因此，必须存在一个偶数 $2\le i\le n$，使得 $max(p_{i-1},p_i)=n$ 并且它必须满足 $max(p_{i-1},p_i)modi=i-1$ 。然而，一个偶数对另一个偶数取模永远不能产生奇数结果，导致矛盾。

Code

::: details

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    if (n % 2 == 0) {
        cout << -1 << '\n';
    }
    else {
        cout << n << ' ';
        for (int i = 1; i < n; i++) {
            cout << i << ' ';
        }
        cout << '\n';
    }
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int T; cin >> T;
    while (T--)  solve();
    return 0;
}

:::

B - MIN = GCD

Question

给定一个长度为 $n$ 的数组 $a$，现在你可以重拍 $a$，使得存在一个 $i,(1\le i<n)$，满足：

输出 Yes 或 No

• $n\le {10}^5$

Solution

我们设 $x=min(a_i)$，想要让这个式子成立，肯定需要把 $x$ 放在最小值的那一边，然后需要在 $a$ 中挑出一些数使得这些数的 $gcd=x$

我们把 $x$ 的倍数挑出来组成这些数，如果 $x$ 的倍数的 $gcd=x$，就是 Yes，如果 $a$ 中出现了多个 $x$，显然也是 Yes

Code

::: details

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll gcd(ll a, ll b) {
    return b == 0 ? a : gcd(b, a % b);
}

void solve() {
    int n; cin >> n;
    vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }
    int min_i = min_element(a.begin() + 1, a.end()) - a.begin();
    ll g = 0;
    for (int i = 1; i <= n; i++) {
        if (i == min_i) continue;
        if (a[i] % a[min_i] == 0) {
            g = gcd(g, a[i]);
        }
    }
    cout << (g == a[min_i] ? "Yes" : "No") << '\n';
}

int main() {
    freopen ("B.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::

C - You Soared Afar With Grace

Question

给定两个长度为 $n$ 的数组 $a,b$，你最多操作 $n$ 次，每次操作如下：

• 选择一对 $i,j$ 交换 $a_i,a_j$，同时交换 $b_i,b_j$

输出方案

Solution

暴力模拟就好了

枚举每一个 $a_i$，去 $b$ 中找 $a_i$ 这个数的位置，假设这个位置为 $y$，执行 $(y,n+1-i)$ 的交换操作就好了

最后操作完之后查看是否满足要求，若不满足则输出 -1

Code

::: details

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n; cin >> n;
    vector<int> a(n + 1);
    vector<int> b(n + 1);

    for (int i = 1; i <= n; i++) cin >> a[i];
    for (int i = 1; i <= n; i++) cin >> b[i];

    vector<int> b_id(n + 1);
    for (int i = 1; i <= n; i++)
        b_id[b[i]] = i;

    vector<pair<int, int>> ans; 

    auto swap = [&] (int x, int y) {
        if (x == y) return ;
        ans.push_back({x, y});
        int tmp = a[x];
        a[x] = a[y]; a[y] = tmp;

        tmp = b[x];
        b[x] = b[y]; b[y] = tmp;

        b_id[b[x]] = x; b_id[b[y]] = y;
    };

    int same = 0, same_i = 0;
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[i]) {
            same += 1;
            same_i = i;
        }
    }
    if (same > 1 || (same == 1 && n % 2 == 0)) {
        cout << -1 << '\n';
        return ;
    }
    if (same == 1) {
        swap(same_i, (n + 1) / 2);   
    }
    for (int i = 1; i <= n; i++) {
        if (a[i] == b[n + 1 - i]) continue;
        swap(b_id[a[i]], n + 1 - i);
    }

    int flg = 1;
    for (int i = 1; i <= n; i++) 
        if (a[i] != b[n + 1 - i]) flg = 0;
    
    if (flg == 0) {
        cout << -1 << '\n';
        return ;
    }

    cout << ans.size() << '\n';
    for (auto [x, y] : ans) {
        cout << x << ' ' << y << '\n';
    }

    return ;
} 

int main() {
    freopen ("C.in", "r", stdin);
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::

D - Arcology On Permafrost

Question

给定三个整数 $n,m,k$

现在需要你构造一个长度为 $n$ 的数组 $a$，需要满足操作后的 $mex$ 最大，操作如下：

你可以从 $a$ 中依次删除长度为 $k$ 的字段至多 $m$ 次，让删除后 $a$ 的 mex 最小

• $n\le {10}^5,m\cdot k<n$

Solution

先思考给定一个数组 $a$，怎样取才能使得 mex 最小

思路肯定是先把 $0$ 取完，如果发现 $0$ 取不完，考虑取 $1$，如果发现 $1$ 取不完，就考虑取 $2$，以此类推

假设最后的 mex 是 $x$，那么小于 $x$ 的书需要至少出现 $m+1$ 次，所以 $x$ ，是满足 $x\cdot (m+1)\le n$ 最大的 $x$

但是也要考虑到 $k$ 的大小，如果 $k$ 太大，一次能同时删除两个 $0$，显然这种构造不太好，所以说 $0$ 之间的跨度必须要大于 $k$

所以贪心地放，肯定是 $0,1,2,3\cdots x-1,0,1,\cdots$，这样循环放比较好，所以得到不等式 $x\ge k$

于是得到 $x=max(\lfloor \frac{n}{m+1}\rfloor ,k)$

Code

::: details

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n, m, k; cin >> n >> m >> k;
    int p = max(n / (m + 1), k);
    for (int i = 0; i < n; i++)
        cout << i % p << ' ';
    cout << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    int T; cin >> T;
    while (T--) solve();
    return 0;
}

:::

E - Blossom

Question

给定一个长度为 $n$ 的排列 $a$，其中有一些缺失值用 $-1$ 表示

将排列的值定义为所有非空子段的 mex 的总和

找到填充 $a$ 中缺失元素可以形成的所有可能有效排列的值之和，对 ${10}^9+7$ 取模。

Solution