题解 P3593 【[POI2015]TAB】

under 题解 P3593

本篇题解代码已在 darkbzoj AC（平均 128ms 每测试点），但在洛谷全 TLE。

在本机可过极限数据（131 MB，生成代码附于文末）。因无人 AC，猜测可能是洛谷数据出锅，烦请各位管理员核实。

qbxt 的例题，跑来水做一发，结果没想到是道坑题!

上面本来有两张表情，但是洛谷图床不能在外链访问，所以……

发掘题目信息

矩阵中的数两两不同
操作：交换任意整行 / 整列
元素值域 [-1e6, 1e6]，整数

对于原矩阵中同一行中的元素：

考虑行交换，交换后显然仍在同一行内；
考虑列交换，交换后顺序改变，但仍在同一行内。

原矩阵中同一列中元素的情况类似。

因此直接判断原矩阵同一行/列中的元素在变换后矩阵内是否均仍在同一行/列，复杂度 $O(Tnm)$，可以通过本题。细节见代码。

~~你以为这就完了吗？当然没有。~~

坑点

每组数据第二个矩阵中的元素可能在第一个矩阵中并未出现，但可能在上一组数据中出现过，需要进行处理。考虑 memset 的巨大常数，选用清零较快的 std::bitset。
如果边读边做，发现数据 NIE 后应该把当前组数据读完，而不是直接做下一组数据。
别忘了给个偏移量

~~你以为这就完了吗？当然没有。~~

爆零后的探索

我在洛谷 TLE 后猜测是算法常数过大，于是在本地测试了极限数据。

发现效率瓶颈在读入：scanf 10s+, getchar 3s+, fread ~0.35s。然而，这份使用了 fread 的代码仍然在洛谷不能通过本题。

darkbzoj AC 代码：

#include<bitset>
#include<cstdio>
#include<cstring>

struct IO {
  inline char gc() {
    static char buf[10000000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000000,stdin),p1==p2)?EOF:*p1++;
  }

  template<typename T>
  inline IO operator>>(T &n) {
    n=0; bool s=0; char c=gc();
    while(c<'0'||c>'9') s|=c=='-',c=gc();
    while(c>='0'&&c<='9') n=(n<<3)+(n<<1)+(c^48),c=gc();
    if(s) n=-n;
    return *this;
  }
} cin;

std::bitset<2000003> vis;
int T, N, M, nr[1003], nc[1003], r[2000003], c[2000003];

bool solve() {
  vis.reset();
  memset(nr, 0, sizeof nr);
  memset(nc, 0, sizeof nc);
  bool f = 1;
  cin >> N >> M;
  for (int i = 1, t; i <= N; ++i)
    for (int j = 1; j <= M; ++j) {
      cin >> t;
      t += 1000000;
      vis.set(t);
      r[t] = i, c[t] = j;
    }
  for (int i = 1, t; i <= N; ++i)
    for (int j = 1; j <= M; ++j) {
      cin >> t;
      if (!f) continue;
      t += 1000000;
      if (!vis[t]) { f = 0; continue; }
      if (!nr[r[t]]) nr[r[t]] = i;
      else if (nr[r[t]] != i) f = 0;
      if (!nc[c[t]]) nc[c[t]] = j;
      else if (nc[c[t]] != j) f = 0;
    }
  return f;
}

int main() {
  for (cin >> T; T; --T)
    puts(solve() ? "TAK" : "NIE");
  return 0;
}

极限数据生成代码（T = 10，N = M = 1000，均 TAK）：

#include<cstdio>

int main() {
  puts("10");
  for (int T = 10; T; --T) {
    puts("1000 1000");
    int t = 0;
    for (int i = 1; i <= 1000; ++i) {
      for (int j = 1; j <= 1000; ++j)
        printf("%d ", ++t);
      puts("");
    }
    t = 0;
    for (int i = 1; i <= 1000; ++i) {
      for (int j = 1; j <= 1000; ++j)
        printf("%d ", ++t);
      puts("");
    }
  }
  return 0;
}