Codeforces Round 1015 (Div. 1 + Div. 2) (opens new window)

A - Max and Mod

Question

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

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

如果无解则输出 $-1$

Solution

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

• 对于$i = 2$，$\max(p_1, p_2) = n$并且$n \bmod 2 = 1$
• 对于$i \geq 3$，$\max(p_{i - 1}, p_i) = i - 1$并且$(i - 1) \bmod i = 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 \leq i \leq n$，使得 $\max(p_{i - 1}, p_i) = n$ 并且它必须满足 $\max(p_{i - 1}, p_i) \bmod i = i - 1$ 。然而，一个偶数对另一个偶数取模永远不能产生奇数结果，导致矛盾。

Code

点击查看

#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)$，满足： $$ \min(a[1],a[2],\cdots,a[i])=\gcd(a[i+1],a[i+2],\cdots,a[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

点击查看

#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

点击查看

#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

点击查看

#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