CF1521E Nastia and a Beautiful Matrix

,

Description

https://www.luogu.com.cn/problem/CF1521E

Solution

发现构造题和贪心题的交集很大啊！

最开始我有一种非常 naive 的想法：按字符数量降序排序，二分一下，把奇数行依次填，填满填偶数行的奇数位。

后来 test2 都过不去，关键在于，如果有两个大小差不多的东西，后面的一个如果填偶数行，很快就会和自己的奇数行出现在对角线上。

改进一下，二分之前的步骤不变，先填奇数行的偶数位，再填奇数行的奇数位，最后填偶数行的奇数位。这样如果不合法一定要大小 $>O(n^2/2)$ (具体下界我也不知道，感性理解一下应该是这个。)

就可以过了，复杂度 $O(n\log n )$。题解好像有证明充要条件不用二分的做法，感觉很高妙。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
int m,k;
struct yyy {
	int x,id;
}c[maxn],d[maxn];
bool cmp(yyy x,yyy y) {return x.x>y.x;}
int a[1005][1005];
bool calc(int i,int j) {
	int res=(a[i][j]>=1)+(a[i][j+1]>=1)+(a[i+1][j]>=1)+(a[i+1][j+1]>=1);
	if (a[i][j]==a[i+1][j+1]&&a[i][j]) return 0;
	if (a[i][j+1]==a[i+1][j]&&a[i][j+1]) return 0;
	if (res==4) return 0;
	return 1;
}
pair<int,int> p[500005];
bool check(int n) {
	int i,j,l;
	for (i=1;i<=k;i++) d[i]=c[i];
	for (i=1;i<=n+1;i++) for (j=1;j<=n+1;j++) a[i][j]=0;
	
	int tot=0;
	for (i=1;i<=n;i+=2) {
		for (j=2;j<=n;j+=2) p[++tot]=mk(i,j);
	}	
	for (i=1;i<=n;i+=2) {
		for (j=1;j<=n;j+=2) p[++tot]=mk(i,j);
	}
	for (i=2;i<=n;i+=2) {
		for (j=1;j<=n;j+=2) p[++tot]=mk(i,j);
	}
	i=1;
	for (l=1;l<=k;l++) {
		int x=d[l].x;
		while (x&&i<=tot) x--,a[p[i].fi][p[i].se]=d[l].id,i++;
		if (x) return 0;
	}
	for (i=1;i<n;i++) for (j=1;j<n;j++) if (calc(i,j)==0) return 0;	
	return 1;
}
void solve(void) {
	int i,j;
	read(m);read(k);
	for (i=1;i<=k;i++) read(c[i].x),c[i].id=i;
	sort(c+1,c+1+k,cmp);
	if (m==1) return printf("1\n%d\n",c[1].id),void();
//	cerr<<check(6)<<endl;return ;
	int l=1,r=sqrt(m*2)+5,mid;
	while (l+1<r) {
		mid=l+r>>1;
		if (check(mid)) r=mid;
		else l=mid;
	}
	printf("%d\n",r);
	check(r);
	for (i=1;i<=r;i++,put()) for (j=1;j<=r;j++) printf("%d ",a[i][j]);
}
signed main(void){
	int T;
	read(T);
	while (T--) solve();
	return 0;
}