题解 | #牛客周赛 Round 111#

牛客周赛 Round 111

第一次尝试倒开 qwq，没想到还意外的挺成功的，最后也是成功 ak 了喵 qwq

这里写的都是我赛时的做法，并非最佳做法，但是还是希望能帮到你 qwq，提供一个参考喵

A 小红的阶梯

直接判断就好了 qwq

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

B 小红的数组取数

简单推下式子

\begin{align} \sum_{i = 1}^{n}(a_i - a_x) - \sum_{i = 1}^{n}(b_i - b_y) &= \sum_{i = 1}^{n}a_i - n \times a_x - \sum_{i = 1}^{n}b_i + n\times b_y\\ &= \sum_{i = 1}^{n}(a_i - b_i) + n\times(b_y - a_x) \end{align}

我们要使这个式子尽可能大。

可以发现第一项是固定的，是两个数组和的差值；而第二项要尽可能大，让 $b_y - a_x$ 尽可能大就好了，也就是选最大的 $b_y$ 和最小的 $a_x$ 。我这里用的是 $\mathtt{std::min\_element}$ 和 $\mathtt{std::max\_element}$ ，感觉方便一点。

void solve() {
    int n;
    std::cin >> n;
     
    std::vector<int> a(n), b(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
    for (int i = 0; i < n; i++) {
        std::cin >> b[i];
    }
     
    std::cout << std::min_element(a.begin(), a.end()) - a.begin() + 1 << " " << std::max_element(b.begin(), b.end()) - b.begin() + 1 << "\n";
}

C 小红抽卡

这是一个比较经典的问题。

题目要求是需要把第 $x$ 个元素放到第一位，但是这个 $k$ 特别大，我们一次次手动模拟肯定是会超时的。能不能不改变数组呢？

当然是可以的！我们可以观察一下，假设我们一开始数组头的位置是在 $p$ ，每次把第 $x$ 个元素搬到前面去，就相当于在模 $x$ 的意义下，让 $p$ 往左移一格，也就是 $\mathtt{p = (p - 1 + x) \mod {x}}$ （这里 $\mathtt{+x}$ 是为了不让下标出现负数），这样的话，每移动 $x$ 次， $p$ 其实都会回到开始的位置，那么我们只需要先把 $k$ 模上 $x$ （每左移 $x$ 格就回到原点），再在模 $x$ 的意义下让 $p$ 减去 $k$ （在模 $x$ 的意义下左移 $k$ 格），得到的就是最终的数组头的下标，这里用取模的话，建议数组使用 $0-index$ 的下标，会方便很多！

输出的时候，先把 $[0, x - 1]$ 的元素输出完，再输出没有输出过的元素就好了，因为题目里的操作只会对 $[0, x - 1]$ 的元素造成影响。

void solve() {
    i64 n, k, x;
    std::cin >> n >> k >> x;
    k %= x;
     
    std::vector<int> a(n);
    for (int i = 0; i < n; i++) {
        std::cin >> a[i];
    }
     
    int p = (x - k) % x;
    std::vector<int> vis(n);
    while (!vis[p]) {
        std::cout << a[p] << " ";
        vis[p] = 1;
        p = (p + 1) % x;
    }
     
    p = 0;
    while (vis[p]) {
        p++;
    }
    while (p < n) {
        std::cout << a[p] << " ";
        p++;
    }
     
    std::cout << "\n";
}

D 小红的好数对

（update : 这题好像题面没说清楚qwq，但是根据样例 $2$ （样例 $2$ 貌似也是赛后加的 qwq），题意应该是把 $a_i = a_j$ 时的 $(i, j)$ 和 $(j, i)$ 认作两种不同的拼接方式）

这题挺好的 qwq，很多写法，这里提供的是 $dp$ 写法，从除法的本质入手，感觉挺对的 qwq

我们要让拼接之后的数是 $11$ 的倍数，我们不妨思考一下，怎么样才能让拼接后的数是 $11$ 的倍数。

我们可以回顾一下我们小时候学的列竖式除法的计算过程，对于第一位，除以 $11$ ，余了一个数，再把后面一位抄下来，再除 ...... 其实这样想就不难发现，我们只要让 $A$ 模 $11$ 的余数的后面接上 $B$ （前面的位不会对结果产生任何影响），如果这样产生的新的数还能被 $11$ 整除，那么这个数也就一定能被 $11$ 整除。

而 $A$ 模完 $11$ 之后，得到的余数一定是在 $[0, 10]$ 之间的，那么我们就可以 $dp$ 啦，记 $pre_{i, j}$ 表示在 $i$ 之前的所有数里（不包含第 $i$ 个数），有多少个数模 $11$ 的余数是 $j$ ， $suf_{i, j}$ 表示在 $i$ 之后的，其他都和前面一样。对于 $pre$ 数组，每次转移的时候，先把前面第 $i - 1$ 个位置的所有 $dp$ 值全部搬过来，然后再更新这一位的余数所带来的影响， $suf$ 数组同理。

然后我们再遍历一遍原数组，对于每一位 $i$ ，我们遍历所有 $11$ 的余数，计算这些余数后面拼接 $a_i$ 之后的数值，看看能不能被 $11$ 整除，可以的话，我们就直接加上 $pre_{i - 1}$ 的对应数值。然后我们还要倒着跑一遍，一样的计算。（注意： $A$ 和 $B$ 拼接的顺序不同，结果也会不同！这两个数不一定都会被 $11$ 整除！我就在这里获得了 $Wrong~Answer$ ， $50$ 分的好成绩 qwq ）

对于数的拼接，我们记前面的数为 $x$ , 接在后面的数为 $y$ ，且 $y$ 在十进制下的长度为 $len$ （也就是这个数有多少位），那么拼接起来的数就是 $x\times 10^{len} + y$ 。可以快速幂优化一下，但是不优化应该也没问题 qwq，应该还是能过的。

i64 power(i64 a, i64 b) { // 快速幂
    i64 res = 1;
    for (; b; a *= a, b >>= 1) {
        if (b & 1) {
            res *= a;
        }
    }
    return res;
}
 
void solve() {
    int n;
    std::cin >> n;
     
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
     
    std::vector<std::vector<int>> pre(n + 1, std::vector<int>(10 + 1));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= 10; j++) {
            pre[i][j] = pre[i - 1][j];
        }
        pre[i][a[i] % 11]++;
    }
     
    std::vector<std::vector<int>> suf(n + 2, std::vector<int>(10 + 1));
    for (int i = n; i >= 1; i--) {
        for (int j = 0; j <= 10; j++) {
            suf[i][j] = suf[i + 1][j];
        }
        suf[i][a[i] % 11]++;
    }
     
    i64 ans = 0;
    for (int i = 2; i <= n; i++) { // 顺着跑一遍
        int len = 0, x = a[i];
        while (x) {
            len++;
            x /= 10;
        }
         
        for (int j = 0; j <= 10; j++) {
            if ((1LL * j * power(10, len) + a[i]) % 11 == 0) {
                ans += pre[i - 1][j];
            }
        }
    }
     
    for (int i = n - 1; i >= 1; i--) { // 倒着跑一遍
        int len = 0, x = a[i];
        while (x) {
            len++;
            x /= 10;
        }
 
        for (int j = 0; j <= 10; j++) {
            if ((1LL * j * power(10, len) + a[i]) % 11 == 0) {
                ans += suf[i + 1][j];
            }
        }
    }
     
    std::cout << ans << "\n";
}

E 小芳的排列构造

构造题。

由于下面的讨论会用到 $n \ge 2$ 这个条件，这里我们先分类讨论一下 $n = 1$ 时的答案：

$n = 1$ 时，只有 $1$ 这一个数， $1$ 在算 $L(a)$ 的时候会被考虑一次，算 $R(a)$ 的时候也会被考虑一次，所以答案只能是 $L(a) + R(a) = 1 + 1 = 2$ ，其他的数都不行，此时数组为 $[1]$ 。

否则 $n\ge 2$ ，我们先考虑最大和最小能达到的和是多少。

总体分析一下，首先 $n$ 一定会被考虑两次，算 $L(a)$ 会被考虑到，算 $R(a)$ 也会被考虑到，因为 $n$ 大于 $[1, n - 1]$ 的所有数。

然后对于其他数，一定 至多被考虑一次，因为无论怎么放，总有一边有 $n$ 这个数存在，所以不能大于这一边的所有数。而对于数 $n - 1$ ，它一定会被考虑到一次，因为一边有 $n$ 这个数，不会被考虑到，另一边的所有数都一定小于 $n - 1$ ，所以有一个固定的贡献。其他的数如果放到 $n$ 与 $n - 1$ 的外侧，就可能产生一次贡献，否则一定不会产生贡献，因为一侧有 $n$ ，另一侧有 $n - 1$ ，都不会让这些数产生贡献。

那么，答案最小的情况就是， $n$ 产生两次贡献， $n - 1$ 产生一次贡献，其他数都不产生贡献，此时答案为 $2\times n + (n - 1) = 3n - 1$ ；答案最大的情况是， $n$ 产生两次贡献，其他数均产生一次贡献，此时答案为 $2\times n + (n - 1) + (n - 2) + \cdots + 2 + 1 = \frac{n(n+1)}{2} + n$ 。

所以答案的范围就是 $[3n - 1, \frac {n(n + 1)}{2} + n]$ 。

然后我们考虑怎么构造对应值的数组。

首先数组的初态是 $[n, n - 1]$ ，这样数组能产生最小贡献。

如果 $k$ 在上面说的范围内，我们可以开一个变量 $dif = k - (3n - 1)$ 表示还需要多少贡献才能到 $k$ ，于是我们可以贪心地从 $[1, n - 2]$ 这个范围内从大到小取数，可以证明是一定能凑出来的，这一部分的严谨数学证明放在了整篇题解的结尾。每取一个数，如果小于等于当前的 $dif$ ，就把它加到数组的最后面，并且让 $dif$ 减去这个数，否则放到 $n$ 和 $n - 1$ 之间。这样构造， $n - 1$ 后面的数是递减的，每个都会产生一次贡献，其他的数不会产生贡献。

void solve() {
	i64 n, k;
	std::cin >> n >> k;
	
    if (n == 1) {
		std::cout << 1 << "\n";
		return;
	}
    
	if (k < 3 * n - 1 || k > n * (n + 1) / 2 + n) {
		std::cout << -1 << "\n";
		return;
	}
	
	std::vector<int> ans;
	ans.push_back(n);
	
	i64 dif = k - 3 * n + 1;
	std::vector<int> f; // 开个辅助数组，不然真的往中间插复杂度太高了
	for (int i = n - 2; i >= 1; i--) {
		if (i <= dif) {
			f.push_back(i);
			dif -= i;
		} else {
			ans.push_back(i);
		}
	}
	
	ans.push_back(n - 1);
	for (int i = 0; i < f.size(); i++) {
		ans.push_back(f[i]);
	}
	
	for (int i = 0; i < n; i++) {
		std::cout << ans[i] << " \n"[i == n - 1];
	}
}

F 小红的排列构造

构造题。

先来考虑最少和最多需要多少次才能把数组还原成顺序。

首先是最小次数，很明显，一次最多改变两个数的位置，也最多能使两个数回到自己的位置上，对于 $n$ 是偶数的情况，最少需要 $\frac{n}{2}$ 次，此时数组为，把 $[1, 2,\cdots, n - 1, n]$ 数组，第一个和最后一个交换，第二个和倒数第二个交换 ...... ，而对于 $n$ 是奇数的情况，在进行完和偶数一样的操作后，中间的数还满足 $a_i = i$ ，所以还需要再加一次，假设中间三个数从小到大是 $a, b, c$ ，那么可以排成 $b, c, a$ ，这样只比原来多一次，总结一下，可以化成一个式子，也就是 $\lceil\frac{n}{2}\rceil$ 次。

然后是最大次数，因为题目意思是一定会采取最优方式交换，那么最优方式最劣的情况就是 $n -1$ 次，每次让一个数回到位置上，剩下的不会回到位置上，在交换完第 $n - 1$ 个数后，最后一个数会自动归位，所以是 $n - 1$ 次，此时数组可能是 $[2, 3, 4,\cdots, n - 1, n, 1]$ ，这种应该是 $n - 1$ 次的，**但是我们下面的构造不会这么构造 **。

这样就能筛选掉所有的无解的情况。

否则有解，我们考虑从初态，也就是最小次数的情况开始扩展。

记变量 $dif = k - \lceil\frac{n}{2}\rceil$ ，表示还要多加多少次数，由于按照上面的构造方式，现在第一个只和最后一个交换，第二只和倒数第二个交换 ...... 那么，只要交换 $a_1$ 和 $a_2$ ，就能让次数加一，因为，你最后一定要换回来再和最后面的交换，这样不断交换最终能达到最大的 $n - 1$ 次。

void solve() {
    int n, k;
    std::cin >> n >> k;
     
    if (k < (n + 1) / 2 || k > n - 1) {
        std::cout << -1 << "\n";
        return;
    }
     
    std::vector<int> a(n);
    std::iota(a.begin(), a.end(), 1); // 这个函数表示把数组 a 的所有元素填充为 [1, 2, ..., n]
     
    for (int i = 0; i < n / 2; i++) { // 先和后面的交换
        std::swap(a[i], a[n - 1 - i]);
    }
    std::swap(a[n / 2], a[(n + 1) / 2]); // n 为奇数就多交换一次，n 为偶数时这两个下标是相等的
     
    for (int i = 0; i < k - (n + 1) / 2; i++) { // 补充次数
        std::swap(a[i], a[i + 1]);
    }
     
    for (int i = 0; i < n; i++) {
        std::cout << a[i] << " \n"[i == n - 1];
    }
}

结尾附上 E 题，对于 $[0, \frac{n(n+1)}{2}]$ 内的所有数都能被 $[1, n]$ 选部分个数恰好一次求和所得到的证明喵 qwq，证明由 yanami_anna 提供，太强啦 qwq，"贪心一定要证明啊！".jpg alt