题目链接在这里：Problem - D - Codeforces

看到一段区间内的奇偶问题就应该想到前缀和 通过前缀和是否相同来判断奇偶

我们设一个字符串 偶数个r的前缀有a个 奇数个r的前缀有b个 (a+b==n)

这题要区间内个数为奇数，所以我们统计的结果即为a*b 现在要让其最大，即a和b越接近的时候值越大

构造的话一位一位构造进行搜索加一点剪枝就行

 1 #include "bits/stdc++.h"
 2 using namespace std;
 3 typedef long long LL;
 4 const LL MAX=1e5+5;
 5 LL n,cnt,flag,fuck;
 6 char s[MAX];
 7 void dfs(LL now,LL la,LL a,LL b){//a even b odd
 8     if (flag) return;
 9     if (a>fuck || b>fuck) return;
10     if (now==n+1){
11         printf("%s\n",s+1);
12         cnt++;
13         if (cnt==100){
14             flag=true;exit(0);
15         }
16             return;
17     }
18     //cout<<now<<' '<<la<<' '<<a<<' '<<b<<endl;
19     s[now]='b';
20     if (la==0)
21         dfs(now+1,la,a+1,b);
22     else dfs(now+1,la,a,b+1);
23     s[now]='r';
24     if (la==0)
25         dfs(now+1,1,a,b+1);
26     else dfs(now+1,0,a+1,b);
27 }
28 int main(){
29     freopen ("d.in","r",stdin);
30     //freopen ("d.out","w",stdout);
31     LL i,j;
32     scanf("%lld",&n);
33     printf("%lld\n",(n/2+1)*(n-(n)/2));
34     fuck=max(n/2+1,n-n/2);
35     flag=false;cnt=0;
36     dfs(1,0,1,0);
37     return 0;
38 }