自动搬运

查看原文

来自洛谷，原作者为

	KingGojianOfYue 这个人很懒，除了写了的什么都没写

搬运于2025-08-24 23:17:35，当前版本为作者最后更新于2025-06-06 19:49:27，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

难度可能有些虚高吧。

前两个数据点可以自己比较容易进行构造，所以直接考虑构造 $n=2333$，$L=10^5$ 的即可。

发现 $n^{\frac{3}{2}}\approx112687>10^5$，$1$ 的个数占比约为 $\frac{1}{\sqrt{n}}$。考虑将这个 $n\times n$ 的正方形分为 $n^{\frac{3}{2}}$ 个 $1\times\sqrt{n}$ 矩形，每个矩形中有且仅有 $1$ 个 $1$。我们将第 $i$ 个元素为 $1$ 的矩形看作 $i$。这样，我们就可以将问题转化为：构造 $n$ 个 $\sqrt{n}$ 元组 $(x_{i,1},x_{i,2},\dots,x_{i,\sqrt{n}})$，满足：

• 任意一个 $\sqrt{n}$ 元组的任意一个元素均为 $[1,\sqrt{n}]$ 中的整数；
• 最多存在某一个位置相同的元素取值相等。

然后构造就简单得多了：将块长设为 $47$（多的那部分不用管了，弄成 $0$ 即可），将其分为 $47$ 组，每组 $47$ 行，对于第 $i$ 组中的第 $k$ 行的第 $j$ 个矩形，将这个矩形中第 $(i\times j+k)\bmod 47$ 个数变为 $1$ 即可。共有 $47^3=103823$ 个 $1$ 符合题意。

代码：

#include<bits/stdc++.h>
#define puts(x) printf(x);printf("\n")
using namespace std;
bitset<2500>e;
int n,L;
int main()
{
    scanf("%d%d",&n,&L);
	if(n==4){
		puts("1100");
		puts("1001");
		puts("0110");
		puts("0011");
		return 0;
	}else if(n==10){
		puts("0011000000");
		puts("0110000000");
		puts("1100000000");
		puts("1001000000");
		puts("1000110000");
		puts("0100011000");
		puts("1000001100");
		puts("0100000110");
		puts("1000000011");
		puts("0100100001");
		return 0;
	}
	for(int i=0;i<47;++i){
		for(int k=0;k<47;++k){
			for(int j=1;j<=2333;++j)e[j]=false;
			for(int j=0;j<47;++j){
				e[j*47+1+(i*j+k)%47]=true;
			}
			for(int j=1;j<=2333;++j){
				if(e[j]==true)putchar('1');
				else putchar('0');
			}
			putchar('\n');
		}
	}
	for(int i=47*47+1;i<=2333;++i){
		for(int j=0;j<2333;++j){
			putchar('0');
		}
		putchar('\n');
	}
	return 0;
}/*

*/