我的第一篇，不喜勿喷

中文翻译：​​
在这个经济环境下，我们都知道找工作有多难。然而，刚毕业的大学生Mirko很幸运——他现在被克罗地亚语言研究所聘为符文学家。他的朋友Slavko认为符文学不是科学，因此对Mirko相信符文学感到愤怒。在一个雾蒙蒙的圣诞节，Mirko的笔记本电脑坏了。由于他不擅长电脑，就交给Slavko修理。调皮的Slavko决定破坏Mirko正在处理的某个文件。

这个文件包含一个R行C列的矩阵。矩阵的每个元素都是一个字母。矩阵中没有两列是相同的。为了捉弄这个"伪科学家"Mirko，Slavko决定从表格顶部删除尽可能多的行，同时不破坏"没有相同列"的规则。

🔍 输入输出格式

输入格式
•第一行：两个整数R和C（2 ≤ R, C ≤ 1000），表示矩阵的行数和列数
•接下来R行：每行包含C个小写字母，表示矩阵的内容
输出格式
•一个整数，表示可以从矩阵顶部删除的最大行数，且删除后矩阵中没有两列相同

🧠 解题思路

这道题的关键在于找到一个最大的k，使得删除前k行后，剩下的(R-k)行矩阵中所有列都是唯一的。

方法一：哈希+二分查找（最优解）
1.​预处理列哈希​：为每一列计算从底部到顶部的滚动哈希值
2.​二分查找​：在0到R-1范围内二分查找最大的k
3.​检查唯一性​：对于每个中间值mid，检查删除前mid行后剩余矩阵的列是否唯一
​时间复杂度​：O(RC + C log C log R)
​空间复杂度​：O(RC)

方法二：逐行检查（暴力法）
1.从最后一行开始向上检查
2.每次删除一行后检查列是否唯一
3.找到第一个使列不唯一的行时停止
​时间复杂度​：O(R²C)
​空间复杂度​：O(RC)

代码实现

#include <iostream>
#include <algorithm>
#include <ctime>
using namespace std;

const int MAX = 1005;
const unsigned long long BASE = 911382629;
const unsigned long long MOD = 1e18 + 3;
const double TIME_LIMIT = 0.9 * CLOCKS_PER_SEC;

char c[MAX][MAX];
unsigned long long has[MAX][MAX], data[MAX];
int R, C;

bool check(int mid) {
    for (int j = 1; j <= C; ++j) {
        data[j] = has[j][R - mid];
    }
    sort(data + 1, data + C + 1);
    for (int j = 2; j <= C; ++j) {
        if (data[j] == data[j - 1]) {
            return false;
        }
    }
    return true;
}

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

    cin >> R >> C;
    for (int i = 1; i <= R; ++i) {
        for (int j = 1; j <= C; ++j) {
            cin >> c[i][j];
        }
    }

    // 计算列的哈希值
    for (int j = 1; j <= C; ++j) {
        for (int i = R; i > 0; --i) {
            has[j][R - i + 1] = (has[j][R - i] * BASE + c[i][j]) % MOD;
        }
    }

    // 二分查找最大可删除行数
    int left = 0, right = R - 1;
    while (left < right) {
        int mid = (left + right + 1) / 2;
        if (check(mid)) {
            left = mid;
        } else {
            right = mid - 1;
        }
    }

    cout << left << endl;
    return 0;
}

pythn也是有的

import sys

def main():
    BASE = 911382629
    MOD = 10**18 + 3

    # 快速读取输入
    input = sys.stdin.read().split()
    ptr = 0
    R = int(input[ptr])
    ptr += 1
    C = int(input[ptr])
    ptr += 1

    # 读取矩阵（1-based索引）
    matrix = [[''] * (C + 1)]  # 第0行 unused
    for i in range(1, R + 1):
        row = [''] + list(input[ptr])  # 第0列 unused
        matrix.append(row)
        ptr += 1

    # 计算列的哈希值 (j表示列, i表示从底部开始数的行数)
    # has[j][i] 表示第j列从底部起i行的哈希值
    has = [[0] * (R + 1) for _ in range(C + 1)]  # has[列][行计数]
    for j in range(1, C + 1):
        for i in range(1, R + 1):
            # 矩阵中实际行号是 R - i + 1 (从底部开始数)
            char_code = ord(matrix[R - i + 1][j])
            has[j][i] = (has[j][i - 1] * BASE + char_code) % MOD

    # 二分查找最大可删除行数
    left, right = 0, R - 1
    while left < right:
        mid = (left + right + 1) // 2
        # 检查当前mid是否满足条件：所有列的哈希值唯一
        seen = set()
        duplicate = False
        for j in range(1, C + 1):
            h = has[j][R - mid]
            if h in seen:
                duplicate = True
                break
            seen.add(h)
        if not duplicate:
            left = mid
        else:
            right = mid - 1

    print(left)

if __name__ == "__main__":
    main()

方法	时间复杂度	空间复杂度	适用情况
哈希+二分	O(RC + C log C log R)	O(RC)	大数据量最优解
暴力法	O(R²C)	O(RC)	小数据量简单实现

🌟 总结

这道题考察了哈希技术和二分查找的结合应用。关键在于：
1.如何高效地表示和比较列的唯一性
2.如何快速确定最大可删除行数
使用滚动哈希预处理每列，再结合二分查找，可以高效解决这个问题。对于R和C达到1000的数据规模，这种方法能够在合理时间内完成计算。

如果这篇题解帮你解决了问题，别忘了点个赞👍让我知道！