题目链接
题目大意
要你一构造一个长度为\(n\)的只包含\(b,r\)字符的串，使得子串中\(r\)的数量为奇数的最多
题目思路
问的qls，确实有点秒
把字符r设为1，b设为0，那么子串中r的数量就是前缀和之差，即前缀和差为奇数
那么n+1个前缀和里，奇数和偶数的个数应该尽可能相近，即前缀的奇数偶数各分一半
注意是n+1个前缀，然后爆搜即可
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
//typedef pair<int,int> pii;
#define fi first
#define se second
#define debug printf("aaaaaaaaaaa\n");
const int maxn=6e5+5,inf=0x3f3f3f3f,mod=998244353;
const ll INF=0x3f3f3f3f3f3f3f3f;
ll n;
char s[maxn];
int cnt=0;
void dfs(int now,int cnt1,int cnt2,int flag){
// now代表第几位，cnt1代表有几个奇数，cnt2代表有几个偶数，flag=0，现在为偶数 flag=1现在为奇数
if(cnt==100) return ;
if(n%2){ //n为奇数
if(cnt1+(n-cnt1-cnt2)<n/2||cnt2+(n-cnt1-cnt2)<n/2||cnt1>n/2+1||cnt2>n/2+1) return ;
}else{
if(cnt1+(n-cnt1-cnt2)<n/2||cnt2+(n-cnt1-cnt2)<n/2||cnt1>n/2||cnt2>n/2) return ;
}
if(now==n){
cnt++;
for(int i=1;i<=n-1;i++){
cout<<s[i];
}
cout<<‘\n‘;
return ;
}
s[now]=‘b‘;
if(flag){
dfs(now+1,cnt1+1,cnt2,flag);
}else{
dfs(now+1,cnt1,cnt2+1,flag);
}
s[now]=‘r‘;
if(flag){
dfs(now+1,cnt1,cnt2+1,flag^1);
}else{
dfs(now+1,cnt1+1,cnt2,flag^1);
}
}
int main(){
cin>>n;
n++;
cout<<(n/2)*(n-n/2)<<‘\n‘;
dfs(1,0,1,0);
return 0;
}