题目描述

难度分:$2600$

输入$n(1 \leq n \leq 10^3)$和长为$n$的数组$a(1 \leq a[i] \leq n)$。

你需要执行如下操作至多$n+1$次：

• 选择$a$的一个子序列，把子序列中的元素全部减一。

假设你操作了$k$次，这$k$个子序列，对应的下标集合必须互不相同。

你需要把所有$a[i]$都变成$0$。输出操作次数，和具体操作方案。

用长为$n$的01字符串$s$表示具体操作方案，$s[i]=1$表示$a[i]$在子序列中。

输入样例$1$

5
5 5 5 5 5

输出样例$1$

6
11111
01111
10111
11011
11101
11110

输入样例$2$

5
5 1 1 1 1

输出样例$2$

5
11000
10000
10100
10010
10001

输入样例$3$

5
4 1 5 3 4

输出样例$3$

5
11111
10111
10101
00111
10100

算法

构造

难得一道会做的周五茶，虽然有几个细节错了好几次，但总算是$AC$掉了。

没办法一眼，需要自己找一下突破口，尝试一下构造的方法。注意到$n \leq 1000$且$a[i] \leq 1000$，所以时间复杂度估计就是$O(n^2)$。尝试从最大值开始入手，由于要求每个子序列都不一样，所以每次都在所有子序列的不同位置上加一。

即所有序列存储在二维字符数组$s$中，由于题目中提到$n+1$个操作序列一定可以达成目的，所以我们先假设$n$个子序列可以达成目的（因为刚好想到了一种对角线填数的构造方法），用以下方法开始构造：

设$mx=max_{i \in [1,n]}a[i]$，令列$i$的初始填$1$位置是$p[i]=i$（即还要构建一个长度为$O(n)$的数组$p$），遍历$i \in [1,n]$，只要此时$a[i] \gt 0$，就令$s[p[i]][i]=$1，$a[i]$自减，并更新$p[i]=(p[i]+1)\%n$，即在列上循环填。每遍历完一轮$[1,n]$，数组的最大值$mx$就会减小$1$。周而复始直到$mx=0$。这样可以构造出来一个$n$轮操作的方案。

但是未必是合法的，所以用哈希表检查一下$n$个子序列有没有重的。如果没有重，直接输出方案就结束了。但如果有重，说明需要$n+1$次操作才能达成目的，我们找到所有重复的子序列方案，假设方案$seq$出现了$cnt$次，那么我们遍历$seq$，只要发现$seq[i]=$1，$s[n+1][i]=$0，就把$seq[i]$的$1$搬到$s[n+1][i]$。然后跳到下一个相同的$seq$继续这个流程，但是从刚才搬运的位置$i$之后继续检查是否有满足$seq[j]=$1，$s[n+1][j]=$0的位置$j$，有就搬运$1$到$s[n+1]$。注意我们对$seq$这个内容的串只需要修改$cnt-1$次，这样已经足够让这些原本相同的串都互不相同。

复杂度分析

时间复杂度

每一轮操作让$a$数组的最大值减小$1$，一共$O(n)$轮，每一轮可以对$O(n)$列填一个$1$。相当于最终要让$a$数组的和从$\Sigma_{i \in [1,n]}a[i]$变成$0$，而$a[i] \leq n$，因此算法的时间复杂度就是$O(n^2)$。

即使存在后续“搬运$1$构造第$n+1$个序列”的操作，也还是$O(n^2)$级别的修正答案，不影响时间复杂度。

空间复杂度

空间消耗主要在于检验序列是否重复时的哈希表，它的映射关系是“方案字符串$\rightarrow$ 该方案对应的行索引列表”，$key$的空间是$O(n^2)$，$O(n)$级别的序列都要存，每个序列的长度是$O(n)$级别；$value$的空间是$O(n)$，即每一行的编号都要存。因此，整个算法的额外空间复杂度为$O(n^2)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 1001;
int n, a[N], b[N];
char s[N][N];

int main() {
    scanf("%d", &n);
    int mx = 0;
    for(int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        b[i] = a[i];
        mx = max(mx, a[i]);
        for(int j = 0; j < n; j++) {
            s[i][j] = s[i + 1][j] = '0';
        }
    }
    if(mx == 1) {
        puts("1");
        for(int i = 0; i < n; i++) {
            printf("%d", a[i]);
        }
    }else {
        vector<int> p(n);
        for(int j = 0; j < n; j++) {
            p[j] = j;
        }
        while(mx > 0) {
            for(int j = 0; j < n; j++) {
                if(b[j] > 0) {
                    b[j]--;
                    s[p[j]][j] = '1';
                    p[j] = (p[j] + 1) % n;
                }
            }
            mx--;
        }
        bool ok = true;
        unordered_map<string, vector<int>> counter;
        for(int i = 0; i < n; i++) {
            string row;
            for(int j = 0; j < n; j++) {
                row.push_back(s[i][j]);
            }
            counter[row].push_back(i);
            if(counter[row].size() > 1) {
                ok = false;
            }
        }
        if(ok) {
            printf("%d\n", n);
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    printf("%c", s[i][j]);
                }
                puts("");
            }
        }else {
            printf("%d\n", n + 1);
            for(auto&[k, v]: counter) {
                if(v.size() > 1) {
                    for(int j = 0, i = 0; j < n; j++) {
                        if(k[j] == '1' && s[n][j] == '0') {
                            if(i < v.size() - 1) {
                                s[v[i]][j] = '0';
                                s[n][j] = '1';
                                i++;
                            }
                        }
                    }
                }
            }
            ok = true;
            for(int i = 0; i <= n; i++) {
                for(int j = 0; j < n; j++) {
                    printf("%c", s[i][j]);
                }
                puts("");
            }
        }
    }
    return 0;
}