E. [THUPC 2021 初赛] 棋盘

远端评测题

1000ms

512MiB

该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

有一个 $n$ 行 $m$ 列的棋盘，共有 $n m$ 个格子。请你在格子内放入棋子（每个格子可以放入至多一个棋子），使得对于所有 $1 \le i \le m$ ，第 $i$ 列里恰好包含 $a_i$ 个棋子。另外，棋盘上的任意两颗棋子都不能边相邻。

请判断是否存在一种合法方案。如果存在，请输出任意一个合法方案。

输入的第一行包含两个正整数 $n, m$ ，保证 $n \le 300, m \le 300$ 。
输入的第二行包含 $m$ 个非负整数 $a_1, a_2, \ldots , a_m$ ，保证 $0 \le a_i \le n$ 。

如果无解，输出一个字符串 No。
如果有解，第一行输出一个字符串 Yes，接下来 $n$ 行每行输出一个长度为 $m$ 的字符串，表示你构造的棋盘方案。其中 0 表示空格，1 表示放入棋子的格子。

3 4
2 1 2 1

3 4
2 3 3 3

No

【题目来源】

来自 2021 清华大学学生程序设计竞赛暨高校邀请赛（THUPC2021）初赛。