题解：CF1063E Lasers and Mirrors

· · 题解

用时：11 分 25 秒。

考虑到只要最优解法只要不是什么都不放，就会至少有一条光线出轨，故猜测答案是 n - 1。

容易发现可以在最后一行直接让一条光线出轨，然后这一列就变成空列了，我们可以把原来需要到这一列的光线引过来。反复这样做一定能在 O(n) 次内归位。

一个小问题是这要求 a 数组构成恰好一个环。这也是不难的，我们在最后一行给它调整成一个环即可。

/* 省选：2026.3.7 */
/* YMao99! */
/* Hatsune Miku x Kasane Teto */
#include <bits/stdc++.h>
#define lowbit(x) ((x) & (-(x)))
using namespace std;

const int N = 1010;
int n, a[N]; char ans[N][N];

int main()
{
    #ifndef LOCAL
//  freopen("cactus.in", "r", stdin);
//  freopen("cactus.out", "w", stdout);
    #endif
    #ifdef LOCAL
//  freopen("text.in", "r", stdin);
//  freopen("prog.out", "w", stdout);
    #endif
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);

    cin >> n;
    for(int i = 1; i <= n; ++i) cin >> a[i];
    for(int i = 1; i <= n; ++i)
        for(int j = 1; j <= n; ++j)
            ans[i][j] = '.';

    // 判断答案是否有可能是 n 
    bool flag = true;
    for(int i = 1; i <= n; ++i) flag &= (i == a[i]);
    if(flag)
    {
        cout << n << '\n';
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
                cout << '.';
            cout << '\n';
        }
        return 0;
    }

    // 记录每个点属于哪个环 
    vector < int > id(n + 1); int idx = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(!id[i])
        {
            ++idx; int p = i;
            while(!id[p]) id[p] = idx, p = a[p];
        }
    }

    // 初始化 
    vector < bool > vis(n + 1); int last_pos = 0;
    for(int i = 1; i <= n; ++i)
    {
        if(vis[id[i]]) continue;
        a[last_pos] = a[i], a[i] = 0;
        ans[n][i] = '\\'; vis[id[i]] = true;
        last_pos = i; 
    }

    // 构造 
    for(int i = n - 1; i >= 1; --i)
    {
        int ID = 0, pos = 0;
        for(int j = 1; j <= n; ++j) if(a[j] == 0) ID = j;
        for(int j = 1; j <= n; ++j) if(a[j] == ID) pos = j;
        if(pos && ID)
        {
            if(pos < ID) ans[i][pos] = ans[i][ID] = '/';
            else ans[i][pos] = ans[i][ID] = '\\';
            a[ID] = ID, a[pos] = 0;
        }
    }

    cout << n - 1 << '\n';
    for(int i = 1; i <= n; ++i)
    {
        for(int j = 1; j <= n; ++j)
            cout << ans[i][j];
        cout << '\n';
    }

    return 0;
}
/*

*/