题解：P10612 [Baltic2001] Box of Mirrors

· · 题解

可能更好的阅读体验

题目

题解

由于光路可逆，我们只需观察左下两侧，分别编号为 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 [email protected]
 * 我还期待着名为奇迹的魔法，哪怕会凋零会消散只会是一场浮华，我笑纳！

         __    __                             __         _
   _____/ /_  / /_________  ___              / /______  (_)______  __
  / ___/ __ \/ __/ ___/ _ \/ _ \   ______   / //_/ __ \/ / ___/ / / /
 / /  / /_/ / /_/ /  /  __/  __/  /_____/  / ,< / /_/ / / /__/ /_/ /
/_/  /_.___/\__/_/   \___/\___/           /_/|_|\____/_/\___/\__, /
                               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);
}

// :\ */