题解 | 牛客周赛 111

自己好久没写题解了，写一下记录一下吧。

这场还是蛮有意思的一场，赛时一个小时不到就切完了。

A.小红的阶梯

模拟一下即可

void solve(){
    int a,b,c;cin >> a >> b >> c;
    cout << (a == b - 1 && b == c - 1 ? "Yes" : "No") << "\n";
}

B.小红的数组取数

由于是的目标最大化，所以选择被减数最小的数字移除，减数最大的数字移除即可。

void solve(){
    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];
    cout << (min_element(a.begin()+1,a.end()) - a.begin()) << " " << (max_element(b.begin()+1,b.end()) - b.begin()) << "\n";
}

C.小红抽卡

可以发现，这题的 $n$ 是没有什么用的，改变的位置永远都是 $1\sim x$ 位置的值，并且每次循环右移一次。

然后由于操作具有周期性（即每 $x$ 轮后与不操作 $x$ 轮的数组完全相同），所以将操作数取模即可。

using i64 = long long;
void solve(){
    i64 n,k,x;cin >> n >> k >> x;
    vector<int> a(n);
    for (int i = 0;i < n;i ++) cin >> a[i];
    k %= x;
    rotate(a.begin(),a.begin()+x-k,a.begin()+x);
    for (int i = 0;i < n;i ++) cout << a[i] << " \n"[i==n-1];
}

D.小红的好数对

个人认为本场最难的题。

首先，我们先解剖每一步操作的本质：

设操作二元组为 $(x,y)$ ，则 $z=x\times 10^{|y|} + y$ ，其中 $|y|$ 表示 $y$ 的数位长度。

那么现在题目要求使得 $z \equiv 0\pmod{11}$ （即能被 $11$ 整除）。

又因为 $10\equiv -1\pmod{11}$ ，所以原式可以变为 $z\equiv(-1)^{|y|}x+y\pmod{11}$ 。

所以我们可以用 $cnt_{0/1,x}$ 表示当前数字前共有 $cnt_{0/1,x}$ 个长度为奇数/偶数且对 $11$ 取模后为 $x$ 值的个数。

于是分别讨论作为二元组的 $x$ 和 $y$ 的情况即可。

using i64 = long long;
void solve(){
    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 ++) b[i] = to_string(a[i]).size() & 1,a[i] %= 11;// b[i] 用于标记当前数字位数的奇偶性
    vector<vector<i64>> cnt(2,vector<i64>(11));
    i64 ans = 0;
    for (int i = 1;i <= n;i ++){
        ans += cnt[1][a[i]];
        ans += cnt[0][(11-a[i]) % 11];
        if (b[i]) {
            ans += cnt[0][a[i]] + cnt[1][a[i]];
        } else {
            ans += cnt[0][(11-a[i])%11] + cnt[1][(11-a[i])%11];
        }
        cnt[b[i]][a[i]] ++;
    }
    cout << ans << "\n";
}

E.小芳的排列构造

由于这题要从两边看，所以首先先思考一下合法 $k$ 的上界值为多少，显然当其为递增/递减序列时最大，即为 $(1+2+\cdots+n) + n$ ，其下界为当两边为最大值，中间为最小值时，只能看到最外边两个，即 $3k-1$ 。

那么可以考虑贪心构造，将一部分移到两个最大值的外面，呈单调形式分布即可。

具体实现上，只需从大值开始枚举到小值。可以证明，只要不超过合法值域，一定存在正确解。

using i64 = long long;
void solve(){
    i64 n,k;
    cin >> n >> k;
    if (k < 3*n - 1 || k > n + (1 + n) * n / 2) {
        cout << -1 << "\n";
        return;
    }
    vector<bool> vis(n+1);
    vis[n] = vis[n-1] = 1;
    k -= n*3 - 1;
    for (int i = n-2;i >= 1;i --){
        if (k >= i) k -= i,vis[i] = 1;
    }
    assert(k == 0);
    for (int i = 1;i <= n-1;i ++) {
        if (vis[i]) cout << i << ' ';
    }
    for (int i = 1;i <= n-1;i ++) {
        if (!vis[i]) cout << i << " ";
    }
    cout << n << "\n";
}

F.小红的排列构造

题目要求构造一个 $a_i \neq i$ 的排列，且恢复为升序排列恰好为 $k$ 步。

那么同上一题一样，考虑上下界。

由于 $a_i \neq i$ ，所以次数下界必定为 $\lceil \frac{n}{2}\rceil$ 次，否则必然不符合条件。

对于操作次数上界，显然每次都至少可以使一个元素回到正确的位置，并且当其为最后一步时，必定恰好 $2$ 个元素回到正确位置，因此次数上界为 $n-1$ 。

对于每次操作，其本质上就是不断从一个位置开始跳，每次跳到当前位置上数字的值，求回到原本出发点所需的步数。其实这个过程与交换操作是等价的，并且每次操作后的步数恰好为数字个数 $-1$ 。

一种实现方式：我们只需不断构造步数所需为 $1$ 的数字对，直到当剩余步数 $k'+1$ 与当前剩余数字个数相等，我们就将这剩余的数字错位方式即可。

void solve(){
    int n,k;
    cin >> n >> k;
    if (k >= n || k < (n+1) / 2) cout << -1 << '\n';
    else {
        vector<int> a(n);
        for (int i = 0,j = n-1;i < j;i++,j --){
            if (j - i == k) {
                iota(a.begin()+i,a.begin()+j+1,i+1); // 递增填充函数
                rotate(a.begin()+i,a.begin()+j,a.begin()+j+1);
                break;
            } else {
                a[i] = j+1,a[j] = i+1;
                k--;
            }
        }
        for (int i = 0;i < n;i ++) cout << a[i] << " \n"[i==n-1];
    }
}

好了，这样你就切掉这一场周赛了，感觉自己又~~摸了一天~~变强了。