题解 P3492 【[POI2009]TAB-Arrays】

_zy_ · 2021-05-04 15:20:17 · 题解

题目传送门

题目大意：

判断一个 nm 的矩阵能否通过整行整列更改成目标矩阵。

我们很显然能知道的是：

对于一行数而言：

如果通过整行更改只改变了位置，并不会有什么其它改变；
而整列更改则会改变这一行数的顺序，并不会引起其他变化。

总之，不论怎么变换，一行数到底是由哪几个数组成，是不会变化的！

一列数同理。

所以我们只需要 Judge 目标矩阵的每一行,每一列是不是在原矩阵中出现过即可。

考虑每一列，每一行的数字组成映射成为一个数字。

显然可以构造：

K= \sum_{i=1}^{n(m)}+\prod_{i=1}^{n(m)}

来映射这一行或这一列的数字组成。

然后用 map 来存储。

时间复杂度 O_{Tmn}.

小细节：

不要忘记开 long long ，亲测 40。

不要忘记清空（数据应该没有卡这一部分。

目标数组没有出现所有在原矩阵的值也不可以。

~~分行列~~(~~其实题目中说明了元素两两不同，这个其实没有必要~~)

//Updating

代码如下：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<queue>
#include<map>
#define int long long 
#define N 10010
#define MOD 10000007
using namespace std;
int re() {
    int p=0,f=1; char i=getchar();
    while(i<'0'||i>'9') {if(i=='-')  f=-1;i=getchar();}
    while(i>='0'&&i<='9')   p=p*10+i-'0',i=getchar();
    return f*p;
}
int T,n,m,cnt;
int a[N][N],f[N];
map<int , bool > v_x,v_y,u_x,u_y;
bool Judge() 
{
    u_x.clear();
    u_y.clear();
    for(int i=1;i<=n;i++)
    {
        int mul=1,sum=0;
        for(int j=1;j<=m;j++)   {
            mul*=a[i][j];
            mul%=MOD;
            sum+=a[i][j];
        }
        u_x[sum+mul]=1;
        if(!v_x[mul+sum])   return false;
    }
    for(int j=1;j<=m;j++)
    {
        int mul=1,sum=0;
        for(int i=1;i<=n;i++)
        {
            mul*=a[i][j];
            mul%=MOD;
            sum+=a[i][j];
        }
        u_y[sum+mul]=1;
        if(!v_y[mul+sum])   return false;
    }
    for(int i=1;i<=cnt;i++)
        if(!u_x[f[i]]&&!u_y[f[i]])  return false;
    return true;
}
signed main()
{
    T=re();
    while(T--)
    {
        memset(f,0,sizeof(f));
        v_x.clear(); v_y.clear();
        cnt=0;
        n=re(); m=re();
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)   a[i][j]=re();
        for(int i=1;i<=n;i++)
        {
            int mul=1,sum=0;
            for(int j=1;j<=m;j++)   {
                mul*=a[i][j];
                mul%=MOD;
                sum+=a[i][j];
            }
            f[++cnt]=mul+sum;
            v_x[mul+sum]=1;
        }
        for(int j=1;j<=m;j++)
        {
            int mul=1,sum=0;
            for(int i=1;i<=n;i++)
            {
                mul*=a[i][j];
                mul%=MOD;
                sum+=a[i][j];
            }
            f[++cnt]=mul+sum;
            v_y[mul+sum]=1;
        }
        for(int i=1;i<=n;i++)
            for(int j=1;j<=m;j++)   a[i][j]=re();
        if(Judge()) printf("TAK\n");
        else printf("NIE\n");
    }
}

如果有不妥之处，请不要吝啬您的评论.

双倍经验

qwq