题解 AT_arc132_a Permutation Grid

简要题意：

给定两个数列 $R$ 和 $C$ ，$R$ 和 $C$ 内均有 $n$ 个元素，要求根据 $R$ 和 $C$ 对一个 $n\times n$ 的矩阵进行染色，使得第 $i$ 行有 $R_i$ 个黑色块，第 $j$ 列有 $C_j$ 个黑色块。最后，$R$ 和 $C$ 均为 $1-n$ 的一个排列。

反思分析：

有个伸臂和一个神犇在赛时没有看到最后一个条件导致两个人想出了各种各样复杂又奇葩的做法，我不说是谁

有了排列那这不成水题了，我们以样例为例（这什么话）把它按顺序重新排列一下，就会变成这样（我们用$W$表示白色，$B$表示黑色）：

$R=5,2,3,4,1\Rightarrow R=1,2,3,4,5$

$C=4,2,3,1,5\Rightarrow C=1,2,3,4,5$

$
\begin{matrix}
& 1& 2& 3& 4& 5&\
1& W& W& W& W& B\
2& W& W& W& B& B\
3& W& W& B& B& B\
4& W& B& B& B& B\
5& B& B& B& B& B
\end{matrix}
$

我们稍加观察，然后惊奇地发现，坐标为$x,y$的块是黑色当且仅当$R_x+C_y>n$，然后我们恢复原序列
$
\begin{matrix}
& 4& 2& 3& 1& 5&\
5& B& B& B& B& B\
2& B& W& W& W& B\
3& B& W& B& W& B\
4& B& B& B& W& B\
1& W& W& W& W& B
\end{matrix}
$
发现这个性质仍然存在！

我们可以通过简单地平移来证明这种做法的正确性，而代码也就相应的非常好写了：

#include <iostream>
#include <cstdio>
using namespace std;

namespace SHAWN {
    const int N = 1e5 + 7;
    int r[N],c[N];
    int n, q;
    int work()
    {
        cin >> n;
        for (int i = 1; i <= n; ++i) { cin >> r[i]; }
        for (int i = 1; i <= n; ++i) { cin >> c[i]; }
        cin >> q;
        for (int i = 1, x, y; i <= q; ++i) {
            cin >> x >> y;
            if (r[x] + c[y] > n) { cout << '#'; }
            else { cout << '.'; }
        }
        return 0;
    }
}

signed int main() {
    ios :: sync_with_stdio(false);
    cin.tie(nullptr);
    return SHAWN :: work();
}