#P2410. [SDOI2009] 最优图像

    ID: 1418 远端评测题 2000ms 250MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>SPFA最短路各省省选2009山东O2优化Special Judge

[SDOI2009] 最优图像

题目背景

小 E 在好友小 W 的家中发现一幅神奇的图画,对此颇有兴趣。

题目描述

这幅画可以被看做一个包含 n×mn \times m 个像素的黑白图像,为了方便起见,我们用 00 表示白色像素,11 表示黑色像素。小 E 认为这幅图画暗藏玄机,因此他记录下了这幅图像中每行、每列的黑色像素数量,以回去慢慢研究其中的奥妙。

有一天,小 W 不慎将图画打湿,原本的图像已经很难分辨。他十分着急,于是找来小 E,希望共同还原这幅图画。根据打湿后的图画,他们无法确定真正的图像,然而可以推测出每个像素原本是黑色像素的概率 pi,j%p_{i,j}\%。那么,一个完整的图像的出现概率就可以定义为:

$$\prod\limits_{i = 1}^n \prod\limits_{j = 1}^{m} p_{i, j}\% \times [s_{i, j} = 1] $$

其中 si,js_{i,j} 表示在还原后的图像中,像素是白色(00)还是黑色(11),[si,j=1][s_{i, j} = 1] 表示若 si,j=1s_{i, j} = 1,则该表达式的值为 11,否则为 00。换句话说,一个完整图像出现概率就等于其所有黑色像素的出现概率之积。显然,图像的黑色像素不能包含概率为 00 的像素。

然而,小 E 对此也无能为力。因此他们找到了会编程的小 F,也就是你,请你根据以上信息,告诉他们最有可能是原始图像的答案是什么。

输入格式

第一行是两个整数 n,mn, m,表示图像大小。

22 到第 (n+1)(n + 1) 行,每行 mm 个整数,第 (i+1)(i + 1) 行的第 jj 个整数 pi,jp_{i, j} 表示第 ii 行第 jj 列的像素是黑色的概率。

接下来一行有 nn 个整数,第 ii 个整数 aia_i 表示第 ii 行中黑色像素的个数。

接下来一行有 mm 个整数,第 ii 个整数 bib_i 表示第 ii 列中黑色像素的个数。

输出格式

本题存在 Special Judge

输出 nn 行每行一个长度为 mm 的只含字符 0 和字符 1 的字符串,表示答案。

输入数据保证至少存在一个可能的图像。如果有多种最优图像,任意输出一种即可。

2 2
90 10
20 80
1 1
1 1
10
01

提示

样例输入输出 1 解释

共有两种可能的图像:

01
10
10
01

前者的出现概率是 0.1×0.2=0.020.1×0.2=0.02,后者的出现概率是 0.9×0.8=0.720.9×0.8=0.72,故后者是最优图像。


数据规模与约定

  • 对于 20%20\% 的数据,保证 n,m5n, m \leq 5
  • 对于 100%100\% 的数据,保证 1n,m1001 \leq n, m \leq 1000pi,j1000 \leq p_{i, j} \leq 1000aim0 \leq a_i \leq m0bin0 \leq b_i \leq n

感谢

https://www.luogu.com.cn/user/23118
spj。