自动搬运

查看原文

来自洛谷，原作者为

	红黑树 https://rbtr.ee

搬运于2025-08-24 22:59:38，当前版本为作者最后更新于2024-08-08 01:34:04，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可能更好的阅读体验

题目

题解

由于光路可逆，我们只需观察左下两侧，分别编号为 $1$ 到 $n + m$。

对于一面镜子 $\left(i, j\right)$，观察它对光路的改变。

我们假设不加这面镜子前，从 $i$ 开始的光线会到达 $b_i$。那么加上这面镜子之后，相当于交换了 $b_i$ 和 $b_{n + j}$。当然有个前提是当前 $\left(i, j\right)$ 右上方不能有任何镜子。

我们现在求出 $b$，看看能不能倒推出上一步的 $b'$，这样我们就推出一面镜子的位置。当 $b_i = i$ 对于所有 $i$ 均满足时，说明没有镜子了，可以结束程序。

现在我们试图找到上一步的 $b'$，我们需要更加具象的东西。让 $i$ 到 $b_i$ 连边。如果产生了自环，说明 $b_i = i$，任务完成了。假设有一条链 $u \to v \to w$，如果删去 $v$，映射关系变成 $u \to w$ 和 $v \to v$，此时 $b_u = w$，我们确实地让自环数量变多了，也就找到了一面镜子。

因此我们选择一个直接相邻的两个点 $\left(i, j\right)$，加镜子 $\left(i, j - n \right)$，消去这条边即可。如果 $b_i = j$ 或者 $b_j = i$，那么这两个点直接相邻。

但我们现在需要找到尽可能靠后加入的镜子，根据上述描述，越靠后的镜子 $i$ 越小，$j$ 越大（右上方）。于是我们可以直接从小到大枚举 $i$，然后从大到小枚举 $j$，判断这两点是否直接连接即可。

代码

/* C++17 is required!
 * By Koicy (https://koicy.ly)
 * Email n@rbtr.ee
 * 我还期待着名为奇迹的魔法，哪怕会凋零会消散只会是一场浮华，我笑纳！

         __    __                             __         _
   _____/ /_  / /_________  ___              / /______  (_)______  __
  / ___/ __ \/ __/ ___/ _ \/ _ \   ______   / //_/ __ \/ / ___/ / / /
 / /  / /_/ / /_/ /  /  __/  __/  /_____/  / ,< / /_/ / / /__/ /_/ /
/_/  /_.___/\__/_/   \___/\___/           /_/|_|\____/_/\___/\__, /
                               SIGN                         /___*/
#define __NO_MAIN__ false
#define __ENABLE_RBLIB__ true
constexpr bool _MTS = false, SPC_MTS = false;
constexpr char EFILE[] = "";
#include <bits/stdc++.h>
#define FULL(arg) arg.begin(), arg.end()

// :/

using namespace std;
using tp = long long int;
using vetp = basic_string<tp>;
[[maybe_unused]] constexpr tp ZERO = 0, ONE = 1, INF = -1ull >> 2;
signed STRUGGLING(unsigned long long int);
void MIST();
#if !__NO_MAIN__
int main(int argc, char* argv[]) {
  unsigned long long int t = 0, _t = 1;
  MIST();
  if (_MTS && !SPC_MTS) cin >> _t;
  while (t < _t || SPC_MTS) {
    if (STRUGGLING(++t) != 0) return 0;
  }
  return 0;
}
#endif
#ifdef XCODE
#define bg(...){bin<<"[#"<<__LINE__<<'@'<<++_LT[__LINE__]<<':';BG(__VA_ARGS__);}
size_t _LT[21777]; template<typename _Type>void BG(const _Type&_cur){cout<<' '<<
_cur << ']' << " <<:" << endl; } template<typename _Type,typename... _Other>void
BG(const _Type& _cur, const _Other& ..._other) {cout<< ' '<<_cur;BG(_other...);}
#else
#define bg(...)
#define dputs(...)
#endif

// :/

// :/

signed STRUGGLING([[maybe_unused]] unsigned long long int TEST_NUMBER) {
  tp n, m; cin >> n >> m;
  vetp c(2 * n + 2 * m + 1, 0);
  for (tp i = 1; i <= 2 * n + 2 * m; ++i) cin >> c[i];
  vetp b(n + m + 1, 0);
  for (tp i = 1; i <= n + m; ++i) {
    tp x = i <= n ? 1 + n + m + n : n + 1 + n * 2 + m * 2;
    x -= i;
    b[i] = c[x];
  }
  vector a(n + 1, vetp(m + 1, 0));
  for (tp i = 1; i <= n; ++i) {
    for (tp j = n + m; j > n; --j) {
      if (b[i] == j || b[j] == i) {
        swap(b[i], b[j]);
        a[i][j - n] = 1;
      }
    }
  }
  for (tp i = 1; i <= n; ++i) {
    for (tp j = 1; j <= m; ++j) cout << a[i][j] << ' ';
    cout << '\n';
  }
  return 0;
}

void MIST() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}

// :\ */