CF1063E Lasers and Mirrors

发布于 2021-05-08  1.79k 次阅读


题目链接

分析

首先需要特判不需要放置镜子答案就为 $n$ 的情况,该情况直接输出即可。

考虑如果你想通过放置镜子使得第 $i$ 个发射器能够匹配上第 $j$ 个接收器,最简单地,你可以在某一行的 $i,~j$ 两列同时放置相对的镜子,使得 $i$ 发射器的信号在两次反射后被 $j$ 接收器接收。

显然这种方法会影响到 $j$ 发射器:当 $j$ 发射器对应的镜子在 $i$ 发射器对应的镜子之后时 $j$ 发射器将无法将信号成功发送至 $j$ 接收器。

由于房间有 $n$ 行,你可以给每一个发射器单独安排一行来放置上面方案中所说的两个镜子。记 $i$ 发射器被分配到的行为第 $a_i$ 行,$i$ 发射器对应的接收器编号为 $to_i$,则显然仅当 $a_{to_i} > a_i$ 时 $to_i$ 不会被 $i$ 影响到。

容易发现上面的不等式关系形成了若干个环,如果直接按照上面所说的方法进行构造则每个环中一定会有一个发射器无法与其对应的接收器匹配上。

考虑指定 $1$ 发射器无法匹配,则我们可以留出一个空列。我们可以先用上面的操作让 $1$ 原来在的环上的点全部匹配成功。

接着依次考虑其他环。对于每一个环,找出一个符合条件的 $p$ 使得 $to_p < to_{to_p}$,即 $a_{to_p}$ 行 $to_p$ 列上的镜子是 /。让除 $p$ 以外的其他在环上的点先正常匹配。然后再尝试让 $p$ 匹配,将 $p$ 发射器的激光反射到 $1$ 列上,在从 $1$ 列向上到 $a_{to_p}$ 行再向右反射,可以刚好反射到 $a_{to_p}$ 行 $to_p$ 列上的 / 镜子上,刚好射入 $to_p$ 接收器。

这样的构造方法可以让除了 $1$ 以外的其他所有发射器均匹配成功,答案为 $n-1$。

代码

/**
 * @author Macesuted (macesuted@qq.com)
 * @copyright Copyright (c) 2021
 */

#include <bits/stdc++.h>
using namespace std;

namespace io {

// fread

}  // namespace io
using io::getch;
using io::getstr;
using io::putch;
using io::putstr;
using io::read;
using io::write;

#define maxn 1005

int a[maxn];
bool vis[maxn];
vector<int> mirror[maxn];
int tail = 1;
char out[maxn][maxn];

void work(int p) {
    int tp = a[p];
    while (tp != p) {
        if (tp < a[tp])
            mirror[tail].push_back(-tp), mirror[tail].push_back(-a[tp]);
        else
            mirror[tail].push_back(tp), mirror[tail].push_back(a[tp]);
        vis[tp] = true;
        tp = a[tp];
        tail++;
    }
    return;
}

int main() {
    int n = read<int>();
    bool check = true;
    for (register int i = 1; i <= n; i++) a[i] = read<int>();
    for (register int i = 1; i <= n; i++)
        if (i != a[i]) check = false;
    if (check) {
        write(n), putch('\n');
        for (register int i = 1; i <= n; i++) {
            for (register int j = 1; j <= n; j++) putch('.');
            putch('\n');
        }
        return 0;
    }
    write(n - 1), putch('\n');
    work(1);
    for (register int i = 2; i <= n; i++)
        if (!vis[i] && i != a[i]) {
            int rec = tail, p = i;
            while (a[p] > a[a[p]]) p = a[p];
            work(p);
            mirror[tail].push_back(1), mirror[tail].push_back(p);
            mirror[rec].push_back(-1);
            vis[p] = true;
            tail++;
        }
    for (register int i = 1; i <= n; i++)
        for (register int j = 1; j <= n; j++)
            out[i][j] = '.';
    for (register int i = 1; i <= n; i++)
        for (vector<int>::iterator j = mirror[i].begin(); j != mirror[i].end(); j++)
            out[i][abs(*j)] = *j < 0 ? '/' : '\\';
    for (register int i = 1; i <= n; i++) {
        for (register int j = 1; j <= n; j++) putch(out[i][j]);
        putch('\n');
    }
    return 0;
}

我缓慢吐出一串啊吧啊吧并不再想说话