The 2020 ICPC Asia Shenyang Regional Programming Contest D题 Journey to Un‘Goro（搜索剪枝）

The 2020 ICPC Asia Shenyang Regional Programming Contest D题

题意就不多加赘述了。首先我们可以知道全为rrrrr的情况可以很快的算出题意中的最大满意度。那么我们如何来构造前100小的字典序序列呢？

错误思路：
一开始我觉得肯定是brbrbr*序列 然后从后往前翻转br emmmm搞了一段时间发现错了（（显然 。

通过暴力打表发现，每种合法的方案中r,b都有数量限制。任何一方的数量超过了限制都不可取。记限制Lim=(n+1)-(n+1)/2 就类似于任何一方至多只能是N/2+1 有了这个限制可以在爆搜的时候节约很多没必要的搜索。
如何考虑最小字典序呢？ 显然，一开始尽量放b的搜索即可。另一个trik就是两个相邻且相同的数，我们应该放置它为b，否则放置r。一开始在序列中插入一个0，每次dfs记录长度和 0，1的个数，优先放与上一个状态结尾一样的数字，即优先保证字典序最小。注意一开始0的数量为1 .

总结：思维能力是真的很重要

vector<ll>s= {0};
ll lim;
ll n;
ll op=0;
void dfs(ll cnt,ll cnt0,ll cnt1)
{if(cnt0>lim||cnt1>lim)return ;if(cnt==n){for(int i=1; i<=n; i++){if(s[i]==s[i-1])printf("b");elseprintf("r");}op++;printf("\n");return ;}ll vis=s[cnt];if(vis==0){s.push_back(0);dfs(cnt+1,cnt0+1,cnt1);s.pop_back();if(op==100)return;s.push_back(1);dfs(cnt+1,cnt0,cnt1+1);s.pop_back();if(op==100)return ;}else{s.push_back(1);dfs(cnt+1,cnt0,cnt1+1);s.pop_back();if(op==100)return;s.push_back(0);dfs(cnt+1,cnt0+1,cnt1);s.pop_back();if(op==100)return ;}
}
signed main()
{read(n);lim=(n+1)-(n+1)/2;if(n==1){printf("1\n");printf("r");return 0;}ll ans=0;for(int i=1; i<=n; i++){ans++;ll le=n-i;ans=ans+le/2;}printf("%lld\n",ans);dfs(0,1,0);
}