夏晓光(loveJY)的博客

QAQ

构造题,关键是想到我们要去构造那个矩阵

一开始想了个鬼畜构造法就是向整体减一然后剩下来非零的数跑一个空一个删一个的过程

就是参照样例一的构造QAQ

这样不一定有解,比如5 1 1 1 1

我们整体减1之后就直接暴毙了

于是我们可以考虑去掉整体减一,直接跑空删的过程,显然也是过不了这个数据的

所以我们想是不是没有很好利用到n+1和$2^n$数量级的差异啊?

我们线性基一下,每一次都至少钦定一个位置是0,然后其他的1再想办法放入剩下n个空位置

于是有很显然的想法,第(i,i)为0,然后剩下的我们怎么构造呢?

随机填充??不太能行吧?QAQ

说完我就写了一下,第三个样例都过不了/cy

而且存在卡的定法,就是一堆1,只要随到两组两个1在同一个pos就没了

确定性构造其实很简单,首先从大到小排序,我们还是钦定那个位置是0,然后从i+1行开始填1,一直填$a_i$个1,超过了n+1就回到1

证明:

如果我们存在两行相同,设为i,j两行,其中j>i,那么因为$a_i>1$我们必然有(j,j)位置左边那个数为1,因为j-1行满足了(j-1,j-1)为0

然后我们显然(j-i,i)也必然要是1,而又因为我们第(i,i)个位置是0,第(j,i)个位置也是0,所以这个j-1位置上的数必然要满足大于$a_i$位置上的数,所以在$j-i-1<i-1+n-j$时候就成立了

而当大于时,即中间空白更多的时候,我们会神奇的发现$(j -1,j)$位置上的数至少要为2(选取i,j为第一行最后一行时)

那么$(j-2,i)$位置上的数也至少要为2,所以他也会在j行有一个1,然后i行又要多出1.....

这样反推下去你会发现我们每一行位置上都要有一个1,而(i,i)位置绝对是0,所以就矛盾了,所以两行的数在大于时也不能相同

code:

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 1e3 + 7;
int n, l, tot;
struct rec {
	int a, id;
	bool operator<(const rec &x)const {
		return a > x.a;
	}
} a[MAXN];
int ans[MAXN][MAXN];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; ++i) {
		scanf("%d", &a[i].a);
		a[i].id = i;
	}
	sort(a + 1, a + n + 1);
	for(int i = 1; i <= n; ++i) {
		int p = i % (n + 1);
		if(p == 0)p = 1;
		for(int cnt = 1; cnt <= n + 1; ++cnt) {
			p = p % (n + 1) + 1;
			ans[p][a[i].id] = 1;
			a[i].a--;
			if(a[i].a == 0)break;
		}
	}
	printf("%d\n", n + 1);
	for(int i = 1; i <= n + 1; ++i) {
		for(int j = 1; j <= n; ++j) {
			printf("%d", ans[i][j]);
		}
		puts("");
	}
	return 0;
}