第 5 场 小白入门赛

A. 十二生肖

思路：

• [鼠, 牛, 虎, 兔, 龙, 蛇, 马, 羊, 猴, 鸡, 狗, 猪]

时间复杂度：\(O(1)\)

print(5)

B. 欢迎参加福建省大学生程序设计竞赛

思路：

• 用map存一下，然后输出一下不同数对的个数

时间复杂度：\(O(n)\)

signed main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int n;
    std::cin >> n;

    std::map<std::pair<int, int>, bool> mp;
    for (int i = 0; i < n; i++) {
        int x, y;
        std::cin >> x >> y;
        mp[{x, y}] = true;
    }

    std::cout << mp.size() << "\n";

    return 0;
}

C. 匹配二元组的数量

思路：

• 直接将式子转化为 \(a_i \times i = a_j \times j\)​ ，然后统计数对的个数即可

时间复杂度：\(O(n)\)

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

    int n;
    std::cin >> n;

    std::map<i64, int> cnt;
    std::vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
        cnt[1LL * a[i] * i]++;
    }

    int ans = 0;
    for (auto [x, y] : cnt) {
        ans += y / 2;
    }
    std::cout << ans << "\n";

    return 0;
}

D. 元素交换

思路：

• 只可能有两种排列，一种是010101010101010101....，还有一种是10101010101010101010....
• 然后我们只需要分别统计两种不一样的数的个数，然后取min，即为最小值

时间复杂度：\(O(n)\)

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

    int n;
    std::cin >> n;

    std::vector<int> a(2 * n + 1);
    for (int i = 1; i <= 2 * n; i++) {
        std::cin >> a[i];
    }

    std::vector<int> zero(2 * n + 1), one(2 * n + 1);
    for (int i = 1; i <= 2 * n; i++) {
        if (i & 1) {
            zero[i] = 1;
        } else {
            one[i] = 1;
        }
    }

    int A = 0, B = 0;
    for (int i = 1; i <= 2 * n; i++) {
        if (zero[i] != a[i]) A++;
        if (one[i] != a[i]) B++;
    }
    
    std::cout << std::min(A / 2, B / 2) << "\n";

    return 0;
}

E. 下棋的贝贝

思路：

时间复杂度：\(O(\sqrt n)\)

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

    i64 n;
    std::cin >> n;

    i64 t = 0;
    while (t * t < n) t++;

    if (t * t - n <= t - 1) {
        std::cout << n * 4 - t * 4 << "\n";
    } else {
        std::cout << n * 4 - (2 * t - 1) * 2 << "\n";
    }

    return 0;
}

F. 方程

思路：

• \(n\)​ 比较大，需要用矩阵快速幂来解决

• 这个式子可以递推得到 \(f_n=k \times f_{n-1} - f_{n-2}\) ，然后构造 \(a\) 矩阵，和 \(res\) 矩阵 \[ B=\left[ \begin{array}{} n-1 \\ n-2 \end{array} \right] \space\space\space \times \space\space\space A=\left[ \begin{array}{} k & -1 \\ 1 & 0 \end{array} \right] \space\space\space =\space\space\space C\left[ \begin{array}{} k \times f_{n-1} - f_{n-2} \\ n-1 \end{array} \right] \]

  这样矩阵 \(A \times B \Rightarrow C(f_n)\)

时间复杂度：\(O(logn)\)

constexpr int P = 1E9 + 7;
void mul(i64 c[][2], i64 a[][2], i64 b[][2]) {
    i64 tmp[2][2] = {0};
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                tmp[i][j] = (tmp[i][j] + a[i][k] * b[k][j]) % P;
            }
        }
    }
    memcpy(c, tmp, sizeof tmp);
}

void solve() {
    i64 n, k;
    std::cin >> n >> k;

    i64 f1 = k, f2 = ((k * k - 2) % P + P) % P;
    if (n == 1) {
        std::cout << f1 << "\n";
    } else if (n == 2) {
        std::cout << f2 << "\n";
    } else {
        i64 a[2][2] = {{k, -1}, {1, 0}};
        auto power = [](i64 a[2][2], i64 b) {
            i64 res[2][2] = {0};
            res[1][1] = res[0][0] = 1;
            for (; b; b /= 2) {
                if (b & 1) {
                    mul(res, res, a);
                }
                mul(a, a, a);
            }
            memcpy(a, res, sizeof res);
        };
        power(a, n - 2);
        i64 res = (a[0][0] * f2 + a[0][1] * f1) % P;
        std::cout << (res + P) % P << "\n";
    }
}