⏰ 时间：2024/08/26
🔄 输入输出：ACM格式
⏳ 时长：100min

本试卷分为单选，多选，编程三部分，这里只展示编程题。

1. 第一题

题目描述

小红有一个大小为 $n\times n$ 的 01 矩阵，小红每次操作可以选择矩阵的一个元素进行反置。小红想知道，最少需要多少次操作，可以让矩阵变成一个单位矩阵，即只有主对角线上有 1，其他位置都是 0（即形如：

$$\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right]$$

）。请你帮助小红解决这个问题。

若当前数字为 0，反置后为 1；若当前数字为 1，翻转后为 0。

输入描述

第一行输入一个整数 $n$，表示矩阵的大小 $(1\le n\le 1000)$。
此后 $n$ 行，第 $i$ 行输入 $n$ 个整数 $a_{i,1},a_{i,2},\dots ,a_{i,n}$，表示矩阵中第 $i$ 行第 $j$ 列的元素 $(a_{i,j}=0\text{ 或 }1)$。

输出描述

在一行上输出一个整数，代表最少需要多少次操作。

题解

模拟即可。

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    int ans = 0;
    
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            int x;
            cin >> x;
            if (i == j) {
                if (x != 1) ans++;
            } else {
                if (x != 0) ans++;
            }
        }
    }
    
    cout << ans << endl;
    return 0;
}

2. 第二题

题目描述

小红定义 $f(x)$ 表示数字 $x$ 的因子个数，例如 $f(6)=4$（6 的因子有 $1,2,3,6$）。

认为一个完美三元组 $(i,j,k)$ $(1\le i<j<k\le n)$ 需要满足：$f(a_i)-f(a_j)=f(a_k)$。

小红给你一个长度为 $n$ 的数组 $a_1,a_2,\dots ,a_n$，请你帮助她求出有多少个不同的完美三元组。

当完美三元组中存在在一个位置数字不同，即认为是不同的方案。例如：$(1,2,3)$ 和 $(1,2,4)$ 为两种方案。

输入描述

第一行输入一个整数 $n$ $(3\le n\le 10^5)$，代表数组中的元素数量。
第二行输入 $n$ 个数字 $a_1,a_2,\dots ,a_n$ $(1\le a_i\le 10^6)$ 表示数组元素。

输出描述

在一行上输出一个整数，代表三元组数量。

题解

给定范围 $a_i\le 10^6$，可以预计算所有数字 $1$ 到 $10^6$ 的因子个数，这可以通过简单的整除操作来实现。具体地，对于每个整数 $i$，将其倍数的因子个数递增，即 $\text{divisor\_count}[j]+=1$，其中 $j$ 是 $i$ 的倍数。在获取了所有元素的因子个数后，问题可以转化为在数组中寻找满足 $f(a_i)-f(a_j)=f(a_k)$ 的三元组。使用两次遍历来分割问题，将当前位置 $j$ 的左侧部分视为前缀，右侧部分视为后缀。分别用计数数组来记录前缀和后缀中因子个数的频率。

对于每个位置 $j$，更新右侧部分的计数，移除当前元素的计数，并遍历所有可能的 $f(a_i)$ 值来验证是否存在满足条件的 $f(a_k)$。具体来说，对于每个前缀中的 $f(a_i)$，计算 $f(a_k)=f(a_i)-f(a_j)$，并检查后缀中是否存在该值。如果存在，将前缀中 $f(a_i)$ 的数量与后缀中 $f(a_k)$ 的数量相乘，并将结果加到总计数中。

#include <bits/stdc++.h>

using namespace std;
using i64 = long long;

const int MAX_N = 1e5 + 5;
const int MAX_A = 1e6 + 5;
const int MAX_DIVISORS = 240 + 5;

int n;
vector<int> numbers;
vector<int> divisor_count(MAX_A, 0);        // 约数个数表
vector<int> divisor_counts;                 // 输入数组中每个元素的约数个数
vector<int> prefix_counts(MAX_DIVISORS, 0); // 前缀中约数个数的计数
vector<int> suffix_counts(MAX_DIVISORS, 0); // 后缀中约数个数的计数

// 预计算每个数的约数个数
void compute_divisors() {
    for (int i = 1; i < MAX_A; ++i) {
        for (int j = i; j < MAX_A; j += i) {
            divisor_count[j]++;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    compute_divisors();

    cin >> n;
    numbers.resize(n);
    divisor_counts.resize(n);
    unordered_map<int, int> total_counts; // 统计每种约数个数的总数

    for (int i = 0; i < n; ++i) {
        cin >> numbers[i];
        divisor_counts[i] = divisor_count[numbers[i]];
        total_counts[divisor_counts[i]]++;
    }

    for (int d = 1; d < MAX_DIVISORS; ++d) {
        suffix_counts[d] = total_counts[d];
    }

    i64 total_triplets = 0;
    for (int j = 0; j < n; ++j) {
        int div_count_j = divisor_counts[j];
        suffix_counts[div_count_j]--;

        // 枚举可能的 div_count_i
        for (int div_count_i = 1; div_count_i < MAX_DIVISORS; ++div_count_i) {
            if (prefix_counts[div_count_i] > 0) {
                int div_count_k = div_count_i - div_count_j;
                if (div_count_k >= 1 && div_count_k < MAX_DIVISORS) {
                    if (suffix_counts[div_count_k] > 0) {
                        total_triplets += (i64)prefix_counts[div_count_i] * suffix_counts[div_count_k];
                    }
                }
            }
        }

        prefix_counts[div_count_j]++;
    }

    cout << total_triplets << endl;

    return 0;
}

3. 第三题

题目描述

小红有一个六边形形状的 01 字符串生成器，一共有 $A,B,C,D,E,F$ 六个部分，每一个部分初始会随机生成一个状态 $0$ 或 $1$，随后，按照 $A,B,C,D,E,F$ 的顺序形成一个 01 字符串，然后显示在蓝色部分的屏幕上。

初始时，小红随机让生成器生成了一个字符串 $S$，但这个并不是小红喜欢的，所以她想将 $S$ 变成目标串 $T$。为此，每次她可以执行以下操作之一：

• 对 $A$ 的状态取反，但该操作会同步把 $B$ 和 $F$ 的状态取反；
• 对 $B$ 的状态取反，但该操作会同步把 $A$ 和 $C$ 的状态取反；
• 对 $C$ 的状态取反，但该操作会同步把 $B$ 和 $D$ 的状态取反；
• 对 $D$ 的状态取反，但该操作会同步把 $C$ 和 $E$ 的状态取反；
• 对 $E$ 的状态取反，但该操作会同步把 $D$ 和 $F$ 的状态取反；
• 对 $F$ 的状态取反，但该操作会同步把 $E$ 和 $A$ 的状态取反。

小红想知道，要将 $S$ 变成 $T$ 至少需要执行几次操作。

注意：若当前字符为 0，取反后为 1；若当前字符为 1，取反后为 0。

输入描述

每个测试文件中包含多组测试数据。

第一行输入一个整数 $T$ $(1\le T\le 10^5)$，代表数据组数，每组测试数据描述如下：

• 第一行输入一个长度为 $6$ 且只由 $0$ 和 $1$ 构成的字符串 $S$，代表初始串。
• 第二行输入一个长度为 $6$ 且只由 $0$ 和 $1$ 构成的字符串 $T$，代表目标串。

输出描述

对于每一组测试数据，在一行上输出一个整数，代表把 $S$ 变为 $T$ 的最小操作次数；如果无法变成目标串，则直接输出 -1。

题解

考虑采用BFS的方法。BFS适合用于寻找无权图中最短路径的情况，这里每个状态都可以视为图中的一个节点，而每次操作产生的新状态则构成与当前状态的边。我们需要记录已经访问过的状态，以避免重复计算和无效循环。

在具体实现中，我们首先检查初始状态 $S$ 是否已经等于目标状态 $T$，如果相等，则无需任何操作，返回 $0$。接下来，将初始状态入队，设定操作计数为 $0$，并维护一个哈希表以标记访问过的状态。然后，进行状态转移，对于当前状态的每一种操作，通过取反相应的部分生成新的状态，并检查是否已达到目标状态。如果达到了目标状态，则返回当前操作计数加一。如果未达到，且该状态未被访问，则将其入队并继续探索。

如果在遍历所有可能的状态后仍未找到目标状态，则返回 $-1$，表示无法通过有效的操作将 $S$ 转换为 $T$。

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> ops = {
    {0, 1, 5},
    {0, 1, 2},
    {1, 2, 3},
    {2, 3, 4},
    {3, 4, 5},
    {0, 4, 5}
};

string flip(const string& s, const vector<int>& positions) {
    string result = s;
    for (int pos : positions) {
        result[pos] = (result[pos] == '0') ? '1' : '0';
    }
    return result;
}

int bfs(const string& start, const string& target) {
    if (start == target) return 0;
    
    queue<pair<string, int>> q;
    unordered_map<string, bool> visited;

    q.push({start, 0});
    visited[start] = true;

    while (!q.empty()) {
        auto [current, steps] = q.front();
        q.pop();

        for (const auto& op : ops) {
            string next = flip(current, op);
            if (next == target) return steps + 1;
            if (!visited[next]) {
                visited[next] = true;
                q.push({next, steps + 1});
            }
        }
    }

    return -1;
}

int main() {
    int T;
    cin >> T;
    while (T--) {
        string S, T;
        cin >> S >> T;
        cout << bfs(S, T) << endl;
    }
    return 0;
}