暑假集训Day29 D (构造+前缀和)

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

我们设一个字符串偶数个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
",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/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 }

未来是什么样，未来会发生什么，谁也不知道。但是我知道，起码从今天开始努力，肯定比从明天开始努力，要快一天实现梦想。千里之行，始于足下！ ——《那年那兔那些事儿》