ABC279C哈希字符串排序

矩阵a的每一列和矩阵b的每一列一一对应即可。

#include <bits/stdc++.h>
using namespace std;
const int N=400005, mo=1e9+7;
int n, m, i, j, k, s;
char a[N];
map <int, int> f;
int main(){
    scanf("%d%d", &n, &m);
    for(i=0; i<n; i++){
        scanf("%s", a+m*i);
    }
    for(j=0; j<m; j++){
        for(s=0, i=0; i<n; i++){
            s = s*771ll + a[m*i+j] % mo;
        }
        f[s]++;//字符串a每一列哈希值统计
    }
    for(i=0; i<n; i++){
        scanf("%s", a+m*i);
    }
    for(j=0; j<m; j++){
        for(s=0, i=0; i<n; i++){
            s = s*771ll + a[m*i+j] % mo;
        }
        if(--f[s] < 0) i = j = N;//出现新的或者不够无解
    }
    printf("%s\n", i<N?"Yes":"No");
    return 0;
}

#include <bits/stdc++.h>
#define N 400005
using namespace std;
int n, m, i, j, k, p[N], q[N];
char a[N], b[N];
int cmpa(int i, int j){
    for(k=0; k<n; k++){
        if(a[m*k+i] != a[m*k+j]){
            return a[m*k+i] == '#';
        }
    }
    return 0;
}
int cmpb(int i, int j){
    for(k=0; k<n; k++){
        if(b[m*k+i] != b[m*k+j]){
            return b[m*k+i] == '#';
        }
    }
    return 0;
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=0; i<n; i++){
        scanf("%s", a+m*i+1);
    }
    for(i=0; i<n; i++){
        scanf("%s", b+m*i+1);
    }
    for(i=1; i<=m; i++){
        p[i] = q[i] = i;
    }
    sort(p+1, p+m+1, cmpa);//按照列索引排序
    sort(q+1, q+m+1, cmpb);
    for(i=0; i<n; i++){
        for(j=1; j<=m; j++){
            if(a[i*m+p[j]] != b[i*m+q[j]]){
                i = j = N;
            }//排序后每一列相等
        }
    }
    printf("%s\n", i<N?"Yes":"No");
    return 0;
}

有同学直接判断行、列#数量一样就过了；更有同学直接判断行数量一样就过了，数据有点太水。