直播预告

直播时间：3月9日（周六）下午4点-6点
直播地址： B站ACGO官方账号
直播内容：排位赛#5复盘（欢迎观看大型翻车现场）
主讲人：アイドル老师

---

ACGO 第五次排位赛题解

T1、 Acgo社区

题目解析

考虑使用一种数据结构来高效维护用户 $A$ 和用户 $B$ 之间的关系。

使用 map<int, set<int>> user 来维护每位用户关注的所有其他用户：

user[A] 表示用户 $A$ 关注的所有用户的集合。

如果满足条件 user[A] 中存在 $B$ 且 user[B] 中存在 $A$ 则说明 $A$ 和 $B$ 目前属于互相关注的状态。

AC代码

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, q;
        cin >> n >> q;
        map<int, set<int>> fans;
        for (int i = 0; i < q; ++i) {
            int t, a, b;
            cin >> t >> a >> b;
            if (t == 1)
                user[a].insert(b);
            else if (t == 2)
                user[a].erase(b);
            else
                cout << (user[a].count(b) and user[b].count(a) ? "Yes" : "No") << '\n';
        }
    }
    return 0;
}

复杂度分析

对于每个操作时间复杂度为 $O(\log{N})$，总时间复杂度为 $O(Q\log{N})$。

---

T2、添加元素让数组变为好数组

提示

$A \oplus A = 0$

题目解析

任意数字与自己异或的结果为 $0$。

令原数组和为 $sum$，异或和为 $xsum$，那么显然我们可以在数组后添加两个元素：$xsum$ 和 $sum+xsum$。

这样对于添加元素后的数组的和为 $(sum+xsum) \times 2$，异或和为 $sum+xsum$，满足题目要求。

AC代码

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        auto sum = 0LL, xsum = 0LL;
        for (int i = 0; i < n; ++i) {
            int x; cin >> x;
            sum += x;
            xsum ^= x;
        }
        cout << 2 << '\n';
        cout << xsum << ' ' << sum + xsum << '\n';
    }
    return 0;
}

复杂度分析

遍历一遍数组求得 $sum$ 和 $xsum$，时间复杂度 $O(n)$。

---

T3、替换子串使两串相等

题目解析

两种操作本质上就是可以把 $s$ 中的 'a' 向右移动，'c' 向左移动。

所以把 $s$ 和 $t$ 中的所有字符 'b' 去掉之后，两个字符串应该是相同的。

另外，由于 'a' 不能向左移动，'c' 不能向右移动，所以要检查字符串 $s$ 和 $t$ 中，对应的字符 'a' 和字符 'b' 的下标。

对于字符 'a'，在 $s$ 中每个字符 'a' 在字符串 $t$ 中都应该 有一个下标大于等于 它的 'a' 与之对应；
相对对应的，在 $s$ 中每个字符 'c' 在字符串 $t$ 中都应该 有一个下标小于等于 它的 'c' 与之对应。

AC代码

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        string s, t;
        cin >> s >> t;
        string a, b;
        for (auto &x : s)
            if (x != 'b') a.push_back(x);
        for (auto &x : t)
            if (x != 'b') b.push_back(x);
        if (a != b) {
            cout << "NO" << '\n';
            continue;
        }
        auto check = [&]() {
            vector<int> idx;
            for (int i = 0; i < n; ++i)
                if (s[i] != 'b') idx.push_back(i);
            for (int i = 0, j = 0; i < n; ++i) {
                if (t[i] == 'b') continue;
                if (t[i] == 'a' and i < idx[j]) return false;
                if (t[i] == 'c' and i > idx[j]) return false;
                ++j;
            }
            return true;
        };
        cout << (check() ? "YES" : "NO") << '\n';
    }
    return 0;
}

复杂度分析

检查 $s$ 和 $t$ 去掉所有字符 'b' 之后是否相等时间复杂度为 $O(n)$。
检查 $s$ 中字符 'a' 和 'b' 相对于在字符串 $t$ 中的位置时间复杂度为 $O(n)$。

---

T4、使两方格相等的最少操作次数

题目解析

方格 $A$ 的状态可以用 $(P, Q)$ 来表示，其中 $P = (P_1, P_2, \ldots, P_H)$ 是代表 行 原始位置的排列，而 $Q = (Q_1,Q_2, \ldots, Q_W)$ 是代表 列 原始位置的排列。

一开始 $P = (1, 2, \ldots, H), Q = (1, 2, \ldots, W)$；交换相邻的行或列相当于交换 $P$ 或 $Q$ 中相邻的两个元素。

另外，当前方格中 $(i, j)$ 上的整数可以从 $A$ 的初始状态的 $(i, j)$ 上的整数获得。

例如，对于题目中第一个样例转换的过程，状态 $(P, Q)$ 变化为

$$\begin{aligned} &P = (1, 2, 3, 4), Q = (1, 2, 3, 4, 5)\\ \rightarrow &P = (1, 2, 3, 4), Q = (1, 2, 3, 5, 4)\\ \rightarrow &P = (1, 3, 2, 4), Q = (1, 2, 3, 5, 4)\\\rightarrow &P = (1, 3, 2, 4), Q = (1, 3, 2, 5, 4).\\ \end{aligned}$$

$(P, Q)$ 的总数是 $P$ 的排列的数量和 $Q$ 的排列的数量的乘积即 $H!W! \leq 5!\times 5! = 14400$。

因此，我们对这 $H!W!$ 个 $(P, Q)$，即 $(1, 2, \ldots, H)$的排列 $P$ 和 $(1, 2, \ldots, W)$ 的排列 $Q$ 中的每一个，执行以下操作：

• 首先，根据当前的 $(P, Q)$ 和 $A$ 构造方格 $C$ 并判断和方格 $B$ 是否相等。
• 如果相等，求从初始状态到达当前 $(P, Q)$ 的最小操作次数。

如果没有任意一对 $(P, Q)$ 和 $A$ 构造出的方格 $C$ 与方格 $B$ 相同，那么就不可能使方格 $A$ 和方格 $B$ 相等，输出 $-1$。

从初始状态到达当前状态 $(P, Q)$ 所需的最小操作数是以下操作之和：

• 通过重复交换相邻元素从初始序列 $(1, 2, \ldots, H)$ 得到排列 $P$ 所需的最少操作次数；
• 通过重复交换相邻元素从初始序列 $(1, 2, \ldots, W)$ 得到排列 $Q$ 所需的最小操作次数；

从排列 $(1, 2, \ldots, N)$ 开始，通过重复交换相邻的两个元素得到所需的排列 $A = (A_1, A_2, \ldots, A_N)$ 所需的运算次数为排列 $A$ 中的 逆序对 的数量，即

• $1 \leq i \lt j \leq N$，$A_i \gt A_j$ 的 $(i, j)$ 的个数。

因此，从初始状态到 $(P, Q)$ 所需的操作次数就是 $P$ 的 逆序对 的数量与 $Q$ 的 逆序对 的数量之和。

AC代码

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

int count(vector<int> &a) {
    int n = a.size(), res = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i] > a[j]) ++res;
    return res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int>> a(n, vector<int>(m));
        vector<vector<int>> b(n, vector<int>(m));
        for (auto &row : a)
            for (auto &x : row) cin >> x;
        for (auto &row : b)
            for (auto &x : row) cin >> x;
        vector<int> row(n), col(m);
        iota(begin(row), end(row), 0);
        iota(begin(col), end(col), 0);
        int res = 100;
        do {
            do {
                vector<vector<int>> c(n, vector<int>(m));
                for (int i = 0; i < n; ++i)
                    for (int j = 0; j < m; ++j)
                        c[i][j] = a[row[i]][col[j]];
                if (c != b) continue;
                res = min(res, count(row) + count(col));
            } while (next_permutation(begin(col), end(col)));
        } while (next_permutation(begin(row), end(row)));
        cout << (res < 100 ? res : -1) << '\n';
    }
    return 0;
}

复杂度分析

枚举所有的 $(P, Q)$ 时间复杂度为 $O(H!W!)$；
构造方格 $C$ 并判断是否和 $B$ 相等的时间复杂度为 $O(HW)$；
求 $P$ 的逆序对数量时间复杂度为 $O(H^2)$；
求 $W$ 的逆序对数量时间复杂度为 $O(W^2)$；
因此总的时间复杂度为 $O(H!W! \times (HW + H^2 + W^2))$。

---

T5、照片装裱

题目解析

我们可以把所有的照片和相框的宽度和长度放在一块，并按照宽度从大到小排序，如果一个照片和一个相框的宽度相同，则将相框放在前面。

接下来准备一个容器 $S$，并遍历排序后的照片和相框：

• 若当前为相框 $(C_i, D_i)$，则将 $D_i$ 放入 $S$ 中。
• 若当前为照片 $(A_i, B_i)$，则从 $S$ 中找最小的大于等于 $B_i$ 的元素，并将其从 $S$ 中删除。如果无法找到这样的元素，说明这个照片无法找到一个相框来装裱，答案为 $\tt{No}$。

如果成功遍历完所有的元素，答案为 $\tt{Yes}$。

如果使用一个普通数组充当容器 $S$，那么以上算法的时间复杂度为 $O(NM)$，但是我们可以使用 std::multiset 作为 $S$ 来解决这个问题，时间复杂度为： $O((N + M)\log{(N + M)})$。

AC代码

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

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n, m;
        cin >> n >> m;
        vector<pair<int, int>> a(n), b(m);
        for (auto &[w, l] : a) cin >> w;
        for (auto &[w, l] : a) cin >> l;
        for (auto &[w, l] : b) cin >> w;
        for (auto &[w, l] : b) cin >> l;
        vector<tuple<int, bool, int>> arr;
        for (auto &[w, l] : a)
            arr.emplace_back(w, 0, l);
        for (auto &[w, l] : b)
            arr.emplace_back(w, 1, l);
        sort(arr.rbegin(), arr.rend());
        auto check = [&]() {
            multiset<int> st;
            for (auto &[w, t, l] : arr) {
                if (t) st.insert(l);
                else {
                    auto obj = st.lower_bound(l);
                    if (obj == end(st)) return false;
                    st.erase(obj);
                }
            }
            return true;
        };
        cout << (check() ? "Yes" : "No") << '\n';
    }
    return 0;
}

---

T6、方格染色

题目解析

涂黑的一组方格与棋子移动的方法相关，因此只需计算到达每个方格的方案数即可。

若我们忽略解法的复杂度我们可以使用以下这种动态规划的方法来解决这个问题：

vector<int> dp(n);
for (int i = 0; i < n; ++i)
    for (int j = i + A[i]; j < n; j += A[i])
        dp[j] += dp[i];

当 $A_i$ 较大时，对 $j$ 的迭代不会重复很多次，所以这种方法似乎是合理的，但如果以 $A_i=[1,1,\dots,1]$ 为例，则需要花费 $O(N^2)$ 的时间，所以这种算法无法通过本题。

考虑在 $A_i$ 相同的情况下集体更新。具体来说，在从 $i$ 开始的转换过程中，如果存在 $j$ 使得 $A_i=A_j$，那么之后在 $j$ 的循环过程中将它们全部相加。

时间复杂度

上述方法可以在 $O(N\sqrt N)$ 的时间复杂度内完成。

如果每个 $A_i$ 在更新的过程中全部重复掉，那么对于每个 $A_i$ 只需要将其移动一次，之后让 $A_j$ 代替 $A_i$ 更新。

最坏的情况是没有 "一起更新"，并且 $A_i$ 的值尽可能的小。

在这种情况下，$A$ 就像这个样子 $[1, 2, 2, 3, 3, 3, 4, \cdots]$，而那么 $j$ 的调用次数为：

$$\frac{N}{1} + \frac{N}{2} + \frac{N}{2} + \frac{N}{3} + \frac{N}{3} + \frac{N}{3} + \frac{N}{4} + \cdots$$

即：

$$N \times \big(1 + 2 \times \frac{1}{2} + 3 \times \frac{1}{3} + 4 \times \frac{1}{4} + \cdots + M \times \frac{1}{M} + \cdots\big)$$

上式中 $1 + 2 + 3 + 4 + \cdots + M = \frac{M \times (M + 1)}{2} = N$ 所以 $O(M) = O(\sqrt{N})$

那么我们可以由上式得到：

$$O \big(N \times \big( \overbrace{1 + 1 + 1 + \cdots + 1}^{M} + \cdots\big)\big) = O(N\sqrt{N})$$

故整体算法时间复杂度为 $O(N\sqrt{N})$。

AC代码

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

constexpr int MOD = 998244353;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        int n; cin >> n;
        vector<int> arr(n);
        for (auto &x : arr) cin >> x;
        vector<int> dp(n), f(n);
        dp[0] = 1;
        for (int i = 0; i < n; ++i)
            for (int j = i + arr[i]; j < n; j += arr[i]) {
                dp[j] = (dp[j] + (dp[i] + f[i]) % MOD) % MOD;
                if (arr[j] == arr[i]) {
                    f[j] = (dp[i] + f[i]) % MOD;
                    break;
                }
            }
        int res = 0;
        for (int i = 0; i < n; ++i)
            res = (res + dp[i]) % MOD;
        cout << res << '\n';
    }
    return 0;
}