D. Journey to Un'Goro

求奇数个r段最多的方案
显然考虑前缀和
s[i]表示前i个位置r的数量
我们一段是奇数r 那么显然s[i]-s[j]为奇数
我们要让pair<i,j>数量最多
显然可以轻松算的答案是多少
肯定是一人一半
ans=up(n+1,2)*((n+1)/2)
考虑如何输出方案
字典序最小 考虑搜索
我们要记录 当前步数 奇数个数cnt1 偶数个数cnt0 来方便是不是合法的 然后还要记录当前状态s[i]是奇数还是偶数
当cnt1>up(n+1,2)||cnt0>up(n+1,2)我们就返回 这样既保证了合法性又剪枝了
然后字典序我们优先填‘b’即可
复杂度我也不知道 但

那他就是100n的！

int n,cnt;
string s;
void dfs(int now,int cnt0,int cnt1,int st){
    if(cnt0>up(n+1,2)||cnt1>up(n+1,2))return;
    if(now==n){
        cout<<s<<endl;
        cnt++;
        if(cnt==100){
            exit(0);
        }
        return;
    }
    s.push_back('b');
    dfs(now+1,cnt0+(st^1),cnt1+st,st);
    s.pop_back();
    s.push_back('r');
    st^=1;
    dfs(now+1,cnt0+(st^1),cnt1+st,st);
    s.pop_back();
}
void solve(){
    cin>>n;
    int ans=up(n+1,2)*((n+1)/2);
    cout<<ans<<endl;
    dfs(0,1,0,0);
}