p6502题解

· · 题解

这道题可以用哈希来做，因为 n 和 m 的范围比较大，还需要二分和前缀和寻找答案。

但是输入是是行在前，求哈希是要列在前，需要转换。

求哈希需要用到 Ascii 码，但是 Ascii 中有很多浪费的元素，所以将 Ascii 的 256 为改成 131 位是容错率最小的。

所以哈希数组的转换公式为：

has_{i,j}$ = $has_{i,j-1}$ × 131+ $c_{i,j}

与大家不同的是，我用的是单哈希，别人是双哈希。

#include<bits/stdc++.h>
using namespace std;
char c[5005][5005];//原方阵
int n,m;
unsigned long long has[5005][5005],data[5005];//防止爆内存
bool check(int mid)
{
    for(int i=1;i<=m;i++){data[i]=has[i][n-mid];}//把哈希转换到每一列
    sort(data+1,data+m+1);//从小到大排序
    for(int i=2;i<=m;i++)
    {
        if(data[i]==data[i-1]){return 0;}//排序后如果相邻两个相同，就不是正确答案
    }
    return 1;
}
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++){cin>>c[i][j];}
    }
    for(int j=1;j<=m;j++)//因为是判断列，所以把列放在前面
    {
        for(int i=n;i>0;i--)
        {
            has[j][n-i+1]=has[j][n-i]*131+c[i][j];//哈希转换
        }
    }
    int l=0,r=n-1;
    while(l<r)//二分
    {
        int mid=(l+r+1)/2;//如果是(l+r)/2会死循环
        if(check(mid)){l=mid;}//判断check
        else{r=mid-1;}
    }
    cout<<l<<endl;
    return 0;
}