【BZOJ1142】[POI2009] Tab(这道SB题居然卡常)

点此看题面

大致题意: 给定两个\(n\times m\)的矩阵,保证同个矩阵中元素两两不同,问能否交换若干次行和列由第一个矩阵得到第二个矩阵。

前言

\(SB\)题,本来只想水一水,结果被BZOJ卡常了。

好不容易卡过,一怒之下就来水篇博客发泄一下。

以下是我的提交记录:

  • 洛谷:\(AC\)(这种\(SB\)题,随便用\(STL\)写写就过了)
  • BZOJ:\(TLE\)(。。。。。。我错了,我不用\(STL\)了,赶紧去改成离散化)
  • BZOJ:\(TLE\)(。。。。。。改成离散化依旧\(T\)掉了,猛然警觉之前偷懒没写读优)
  • 洛谷:\(WA\)(。。。。。。突然想起来之前为什么偷懒,是因为有负数)
  • 洛谷:\(WA\)(。。。。。。为什么它\(WA\)的一模一样?好家伙,原来负数读优写错了)
  • 洛谷:\(AC\)(终于过了,这还不稳过我倒立吃&@*#¥@#【某陈年**】)
  • BZOJ:\(AC\ 37408ms/40000ms\)(呼,总算过了,差点就。。。。。。)

于是我就被一道水题再次搞得心态爆炸。

题解

显然,无论怎么交换,同一行的数依然同一行,同一列的数依然同一列。

因此只要标记一下哪些数同一行/同一列,就可以了。

代码

#pragma GCC optimize(2)
#pragma GCC optimize("inline")
#include<bits/stdc++.h>
#define Tp template<typename Ty>
#define Ts template<typename Ty,typename... Ar>
#define Reg register
#define RI Reg int
#define Con const
#define CI Con int&
#define I inline
#define W while
#define N 1000
using namespace std;
int n,m,a[N+5][N+5],P1[N+5],P2[N+5],dc,dv[N*N+5],p1[N*N+5],p2[N*N+5];
class FastIO
{
	private:
		#define FS 100000
		#define tc() (A==B&&(B=(A=FI)+fread(FI,1,FS,stdin),A==B)?EOF:*A++)
		#define tn (x<<3)+(x<<1)
		#define D isdigit(c=tc())
		int f;char c,*A,*B,FI[FS];
	public:
		I FastIO() {A=B=FI;}
		Tp I void read(Ty& x) {x=0,f=1;W(!D) f=c^'-'?1:-1;W(x=tn+(c&15),D);x*=f;}
}F;
int main()
{
	RI Tt,i,j,x,t,f;F.read(Tt);W(Tt--)
	{
		F.read(n),F.read(m),dc=0;
		for(i=1;i<=n;++i) for(j=1;j<=m;++j) F.read(a[i][j]),dv[++dc]=a[i][j];
		sort(dv+1,dv+dc+1),dc=unique(dv+1,dv+dc+1)-dv-1;//离散化
		#define GV(x) lower_bound(dv+1,dv+dc+1,x)-dv
		for(i=1;i<=n;++i) for(j=1;j<=m;++j) a[i][j]=GV(a[i][j]),p1[a[i][j]]=i,p2[a[i][j]]=j;//记录每个数在哪一行/哪一列
		f=1,F.read(t),dv[x=GV(t)]^t&&(f=0),P1[1]=p1[x],P2[1]=p2[x];//记下第二个矩阵中第一行、第一列在第一个矩阵中对应行列
		for(j=2;j<=m;++j) F.read(t),dv[x=GV(t)]^t&&(f=0),p1[x]^P1[1]&&(f=0),P2[j]=p2[x];//记下第二个矩阵中每一列对应列
		for(i=2;i<=n;++i)
		{
			F.read(t),dv[x=GV(t)]^t&&(f=0),P1[i]=p1[x],p2[x]^P2[1]&&(f=0);//记下该行对应行
			for(j=2;j<=m;++j) F.read(t),dv[x=GV(t)]^t&&(f=0),(p1[x]^P1[i]||p2[x]^P2[j])&&(f=0);
		}
		for(i=1;i<=dc;++i) p1[i]=p2[i]=0;puts(f?"TAK":"NIE");
	}return 0;
}
上一篇:vue 常规错误及解决 一


下一篇:U8数据库表结构