自动搬运

查看原文

来自洛谷，原作者为

	namespace_std 万物皆可构造。

搬运于2025-08-24 22:15:19，当前版本为作者最后更新于2020-01-01 18:25:15，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

构造的思路是爆搜出来的...

经过推导（或者搜索），我们发现：

令 $s = 00101100101100101 ...$ （ $001011$ 无限循环），当 $|s|>8$ 时一定存在且仅存在 $8$ 个本质不同的回文串。

同时，又由于当串为 $000...0$ 时显然本质不同的回文子串个数为 $n$。

我们发现，当字符串长度 $\geq 8$ 时 $n < m$ 的情况才存在解， 而且如果 $n \neq m$，并且 $m < 8$，一定无解。

又由于每在$s$的开头插入一个 $0$ ，就会多出一个回文串 $00...00$，所以我们可以：

$1)$ 对于 $n < 8$ ，我们只需要判断是否满足 $n = m$ 。

$2)$ 对于 $n = 8$ ，特判 $m = 7$ 。这个可以搜一下或者直接手玩。

$3)$ 对于 $n > 8$ ，我们特判掉 $n = m$ 和 $m \leq 8$，然后记 $len = n-m+8$，显然此时有 $8 < len \leq n$。

于是拼接一个长度为 $n - len$ 的全 $0$ 串和一个长度为 $len$ 的形如 $0010110010110 ...$ 的串即可。

AC代码：

#include<cstdio>
#include<cstdlib>
int n,m;
char v[1111111];
void constr(int n,int m)
{
	register int i;
    if(m==n)
	{
		puts("Yes");
		for(i=1;i<=n;i++)putchar('0');
		puts("");
		return;
	}if(n==8&&m==7)return(void)puts("Yes\n00101100");
	if(m<8)return(void)puts("No");
	int d=n-m+8;
	puts("Yes");
	for(i=1;i<=d;i+=6)v[i]='0';
	for(i=2;i<=d;i+=6)v[i]='0';
	for(i=4;i<=d;i+=6)v[i]='0';
	for(i=3;i<=d;i+=6)v[i]='1';
	for(i=5;i<=d;i+=6)v[i]='1';
	for(i=6;i<=d;i+=6)v[i]='1';
	for(i=d+1;i<=n;i++)putchar('0');
	v[d+1]=0;
	puts(v+1);
}
void exec()
{
	scanf("%d%d",&n,&m);
	constr(n,m);
}
int main()
{
	int T;
	scanf("%d",&T);
	while(T--)exec();
}