Richness of binary words
题目链接：
http://acm.hust.edu.cn/vjudge/contest/126823#problem/B
Description
For each integer i from 1 to n, you must print a string s i of length n consisting of letters ‘a’ and ‘b’ only. The string s i must contain exactly i distinct palindrome substrings. Two substrings are considered distinct if they are different as strings.
Input
The input contains one integer n (1 ≤ n ≤ 2000).
Output
You must print n lines. If for some i, the answer exists, print it in the form “ i : s i” where s i is one of possible strings. Otherwise, print “ i : NO”.
Sample Input
input output
4
1 : NO
2 : NO
3 : NO
4 : aaaa
##题意：
要求输出n个长度为n的字符串(只能放a或b)：
要求Si中不同回文子串的个数恰为i.
##题解：
本质就是找出一种构造方式使得回文子串个数不会再增加.
参考2015-ICPC合肥现场赛H题：
http://blog.csdn.net/snowy_smile/article/details/49870109
http://blog.csdn.net/keshuai19940722/article/details/49839359
##代码：
``` cpp
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define LL long long
#define eps 1e-8
#define maxn 210000
#define mod 100000007
#define inf 0x3f3f3f3f
#define IN freopen("in.txt","r",stdin);
using namespace std;
int n;
int main(int argc, char const *argv[])
{
//IN;
while(scanf("%d", &n) != EOF)
{
if(n == 1) {
printf("1 : a\n");
continue;
}
if(n == 2) {
printf("1 : NO\n");
printf("2 : ab\n");
continue;
}
if(n < 8) {
for(int i=1; i<n; i++)
printf("%d : NO\n", i);
printf("%d : ", n);
for(int i=1; i<=n; i++)
putchar('a');
printf("\n");
continue;
}
if(n == 8) {
for(int i=1; i<7; i++)
printf("%d : NO\n", i);
printf("7 : aababbaa\n");
printf("8 : ");
for(int i=1; i<=n; i++)
putchar('a');
printf("\n");
continue;
}
char str[] = "abaabb";
for(int i=1; i<=7; i++)
printf("%d : NO\n", i);
for(int i=8; i<=n; i++) {
printf("%d : ", i);
for(int j=1,cur=0; j<=n; j++) {
if(j <= i-8) putchar('a');
else {
if(cur == 6) cur = 0;
putchar(str[cur++]);
}
}
printf("\n");
}
}
return 0;
}