题解：AT_arc181_c [ARC181C] Row and Column Order

xyz105 · 2024-08-05 08:41:38 · 题解

题目描述

给定两个长度为 n 的排列 P,Q。试构造出一个 N\times N 的 01 矩阵，要求满足：

• 对于每个 i，将该矩阵的上数第 i 行看成长度为 N 的 01 字符串 S_i，则有 S_{P_1}<S_{P_2}<\cdots<S_{P_N}。
• 对于每个 i，将该矩阵的左数第 i 列看成长度为 N 的 01 字符串 T_i，则有 T_{Q_1}<T_{Q_2}<\cdots<T_{Q_N}。

称两个字符串 A,B 为小于关系当且仅当 A 的字典序比 B 小。

解题思路

场上唐了没想出来。在此 Orz @STUDENT0。

先处理出对于所有 i，该矩阵的上数第 i 行在字典序意义下应该是第几小的，记作 P\_rk_i。读入时令所有 P\_rk_{P_i}=i 即可。对于左数第 i 列也同理，令所有 Q\_rk_{Q_i}=i。

接下来就是本题最关键的部分。如果两个长为 N 的 01 字符串 A,B 满足 A\subsetneq B（即对于每一位 i 有 A_i\le B_i，如果 A_i 为 1 则 B_i 必为 1，B_i 为 1 时 A_i 不一定为 1，注意 A,B 不能相同），那么字典序意义下 A<B 也必然满足。

构造方法：令第 i 行代表的 01 串 S_i 中有 P\_rk_i 个 1，并且这 P\_rk_i 个 1 所在的列的 Q\_rk 值应该是前 P\_rk_i 大的（n-Q\_rk+1 是前 P\_rk_i 小的）。

正确性证明：

1. 对于两行 a,b 满足 P\_rk_a<P\_rk_b，即要求第 a 行代表的串小于第 b 行，不难发现如果第 j 列满足 Q\_rk_j 值是前 P\_rk_a 大的，那么 Q\_rk_j 值也是前 P\_rk_b 大的，反之则不一定。于是行方面符合题意。
2. 对于两列 a,b 满足 Q\_rk_a<Q\_rk_b，即要求第 a 列代表的串小于第 b 列，不难发现某一列的 Q\_rk 值越大，就越有更多的行在这一列设为 1，同上述分析可得列方面符合题意。

参考代码

代码写法整体较简单。

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

int n, p[510], q[510];

char res[510][510];

int main()
{
    cin >> n;
    for (int i = 1, i1; i <= n; i++) cin >> i1, p[i1] = i;
    for (int i = 1, i1; i <= n; i++) cin >> i1, q[i1] = i;
    memset(res, '0', sizeof(res));
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            if (p[i] >= n - q[j] + 1) res[i][j] = '1';
    for (int i = 1; i <= n; i++)
        res[i][n + 1] = '\0', printf("%s\n", res[i] + 1);

    return 0;
}