题解 P5890 【小欧与回文串构造】
namespace_std
·
·
题解
构造的思路是爆搜出来的...
经过推导（或者搜索），我们发现：
令 s = 00101100101100101 ... （ 001011 无限循环），当 |s|>8 时一定存在且仅存在 8 个本质不同的回文串。
同时，又由于当串为 000...0 时显然本质不同的回文子串个数为 n。
我们发现，当字符串长度 \geq 8 时 n < m 的情况才存在解，
而且如果 n \neq m，并且 m < 8，一定无解。
又由于每在s的开头插入一个 0 ，就会多出一个回文串 00...00，所以我们可以：
$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();
}
```