💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🍥 本次T2，T3属于敢猜就能过的题

1️⃣ 充分利用异或的性质，从后往前遍历。

2️⃣ 只要你敢猜，你就能AC，这题有大佬可以评论区证明下吗？这边给出了一个基于 1 奇偶性的大常数做法，比较耗时

3️⃣ 只要你敢猜，你就能AC，直接取出现次数最多的那个，证明本文用较为数学的方法尝试了一下，当然也可以根据轮换对称性什么的。

🪵 01.LYA的异或魔法

问题描述

LYA是一位魔法学院的学生，她最近学会了一种特殊的异或魔法。她有一排魔法石，每块魔法石上都刻着一个数字。LYA想要通过她的异或魔法，让所有魔法石上的数字变得相同。

她的异或魔法可以这样使用：

• 选择一个位置 和一个数值 （，）。
• 对于所有位置 （），将第 个魔法石上的数字与 进行异或操作。

LYA想知道最少需要使用多少次魔法，才能让所有魔法石上的数字相同。你能帮助她解决这个问题吗？

输入格式

第一行输入一个整数 （），表示测试用例的数量。

对于每个测试用例：

• 第一行输入一个整数 （），表示魔法石的数量。
• 第二行输入 个整数 （），表示每块魔法石上的初始数字。

保证所有测试用例中 的总和不超过 200000。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最少需要使用的魔法次数。

样例输入

2
4
1 1 2 2
5 
1 2 3 4 5

样例输出

1
4

数据范围

• 
• 
• 
• 所有测试用例中 的总和不超过 200000

题解

从后向前遍历。

我们的目标是让所有数字变成最后一个数字。

关键思路如下：

1. 从倒数第二个元素开始，向前遍历数组。
2. 对于每个元素，如果它与最后一个元素不同（考虑之前的异或操作），就需要进行一次魔法操作。
3. 每次操作后，需要更新当前位置之前所有元素的异或状态。

原因是异或操作具有以下性质：

• 交换律：
• 结合律：
• 自反性：，

参考代码

• Python

def solve():
    n = int(input())
    a = list(map(int, input().split()))
    cnt = 0  # 操作次数
    s = 0    # 当前异或和
    
    # 从倒数第二个元素开始向前遍历
    for i in range(n - 2, -1, -1):
        if (a[i] ^ s) != a[-1]:
            cnt += 1
            s ^= a[i] ^ s ^ a[-1]
    
    print(cnt)

# 处理多组测试数据
t = int(input())
for _ in range(t):
    solve()

• Java

import java.util.Scanner;

public class Main {
    public static void solve(Scanner scanner) {
        int n = scanner.nextInt();
        int[] a = new int[n];
        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextInt();
        }
        
        int cnt = 0;  // 操作次数
        int s = 0;    // 当前异或和
        
        // 从倒数第二个元素开始向前遍历
        for (int i = n - 2; i >= 0; i--) {
            if ((a[i] ^ s) != a[n - 1]) {
                cnt++;
                s ^= a[i] ^ s ^ a[n - 1];
            }
        }
        
        System.out.println(cnt);
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        while (t-- > 0) {
            solve(scanner);
        }
        scanner.close();
    }
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int i = 0; i < n; ++i) {
        cin >> a[i];
    }
    
    int cnt = 0;  // 操作次数
    int s = 0;    // 当前异或和
    
    // 从倒数第二个元素开始向前遍历
    for (int i = n - 2; i >= 0; --i) {
        if ((a[i] ^ s) != a[n - 1]) {
            cnt++;
            s ^= a[i] ^ s ^ a[n - 1];
        }
    }
    
    cout << cnt << "\n";
}

int main() {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

📝 02.K小姐的魔法矩阵

问题描述

K小姐是一位魔法学院的教授，她最近发明了一种神奇的魔法矩阵。这个矩阵有 行 列，每个元素都是一个非负整数。然而，由于一次实验事故，K小姐不小心遗忘了矩阵中的具体数值。幸运的是，她还记得每一行和每一列的异或和。

现在，K小姐需要你的帮助来重建这个魔法矩阵。你能根据她记住的信息恢复原始矩阵吗？

输入格式

第一行包含两个正整数 和 （），分别表示矩阵的行数和列数。

第二行包含 个非负整数 （），表示每一行的异或和。

第三行包含 个非负整数 （），表示每一列的异或和。

输出格式

如果能够恢复矩阵，首先输出一行 "YES"，然后输出 行，每行包含 个整数 （），表示恢复后的矩阵元素。

如果无法恢复矩阵，则只需输出一行 "NO"。

可以证明，如果能恢复矩阵，一定存在一种解使得矩阵元素的值在 到 之间。

如果存在多个解决方案，您可以输出任意一个，系统会自动判定是否正确。

样例输入

3 3
0 7 6
2 15 12

样例输出

YES
1 2 3
4 5 6
7 8 9

数据范围

• 
• 
• 

题解

本题有一种更简单的办法，前 行 和 列全0，然后根据行异或结果填入最后一列，同理根据列异或结果填入最后一行，然后计算右下角的元素是否和给出的一致，如果是则输出 Yes ，否则 No

这样写不太容易证明正确性，有一种（我赌你的枪里没有子弹的感jio）

有会证明的大佬可以评论区留下你的痕迹！！！

我们接下来给出一种按照考虑异或结果中 1 的奇偶性来做的做法

如果某一列的当前位数是1， 那么可以暂且当做那一列要放一个1上去

然后构造的时候，我们把行列都是1的先填上去，并消去位数，然后显然，此时可能还有余量

直接把剩下的1消去即可，因为前面已经判过剩下的个数了所以剩下的个数一定是偶数个，直接贪心填入不影响结果。

这个常数比较大，Cpp 和Java 在机考中不一定能通过

参考代码

• Python

import sys

def solve():
    # 读取矩阵的行数和列数
    n, m = map(int, input().split())
    
    # 读取每行的异或和
    row_xor = [0] + list(map(int, input().split()))
    
    # 读取每列的异或和
    col_xor = [0] + list(map(int, input().split()))
    
    # 初始化结果矩阵和辅助数组
    result_matrix = [[0 for _ in range(m+1)] for _ in range(n+1)]
    
    # 对每一位进行处理
    for bit in range(63):
        bit_value = 1 << bit
        row_ones_count = 0
        col_ones_count = 0
        
        # 统计该位上1的数量
        for i in range(1, n+1):
            if row_xor[i] & bit_value:
                row_ones_count += 1
        for j in range(1, m+1):
            if col_xor[j] & bit_value:
                col_ones_count += 1
        
        # 检查奇偶性是否匹配
        if row_ones_count % 2 == col_ones_count % 2:
            # 填充矩阵
            for x in range(1, n+1):
                for y in range(1, m+1):
                    if (row_xor[x] & bit_value) and (col_xor[y] & bit_value):
                        result_matrix[x][y] |= bit_value
                        row_xor[x] ^= bit_value
                        col_xor[y] ^= bit_value
                        col_ones_count -= 1
                        row_ones_count -= 1
            
            # 处理剩余的1
            for x in range(1, n+1):
                for y in range(1, m+1):
                    if (row_xor[x] & bit_value) and row_ones_count:
                        result_matrix[x][y] |= bit_value
                        row_xor[x] ^= bit_value
                        row_ones_count -= 1
            
            for x in range(1, n+1):
                for y in range(1, m+1):
                    if (col_xor[y] & bit_value) and col_ones_count:
                        result_matrix[x][y] |= bit_value
                        col_xor[y] ^= bit_value
                        col_ones_count -= 1
        else:
            print("NO")
            return
    
    # 输出结果
    print("YES")
    for i in range(1, n+1):
        print(*result_matrix[i][1:])

if __name__ == "__main__":
    solve()

• Java

import java.util.*;

public class Main {
    static long[][] resultMatrix = new long[1001][1001];

    public static void solve() {
        Scanner scanner = new Scanner(System.in);
        
        // 读取矩阵的行数和列数
        int rowCount = scanner.nextInt();
        int colCount = scanner.nextInt();