CS Academy Palindromic Tree

题目链接：https://csacademy.com/contest/round-45/task/palindromic-tree/

题目大意：给出数字N，构造一个长度为N的由0和1组成的字符串使得其不同的回文子字符串数量最小。N <= 300。

解题思路：一下思路纯粹自己比赛之后瞎想出来，无法给出严谨证明。

试着试着发现了1001 0110 0这个序列，然后发现他是8，继续往后写，1001 0110 010 100 010 100 …… 恩，然后就发现规律了。但是当N = 8的时候应该是 11010011。

具体过程大概就是，以1001 0110 为基序列，每次往后写的时候都要保证不出现新的长度为3和5的回文串。

代码：

 1 const int maxn = 1e6 + 5;
 2 int n;
 3 
 4 void solve(){
 5     if(n < 8){
 6         printf("%d
", n);
 7         for(int i = 0; i < n; i++) printf("1");
 8         puts("");
 9         return;
10     }
11     if(n == 8){
12         printf("7
");
13         puts("11010011");
14         return;
15     }
16     printf("%d
10010110", 8);
17     char str[8] = "010110";
18     for(int i = 0; i < n - 8; i++){
19         printf("%c", str[i % 6]);
20     }
21     puts("");
22 }
23 int main(){
24     scanf("%d", &n);
25     solve(); 
26 }

题目：

Palindromic Tree

Time limit: 1000 ms
Memory limit: 256 MB

Generate a binary string of length

Standard input

The first line contains a single integer

Standard output

On the first line print the number of distinct palindromic substrings.

On the second line print the generated string.

Constraints and notes

Input	Output	Explanation
3	3 111	There are
6	6 100001	There are