Journey to Un‘Goro 贪心，找规律，搜索（沈阳）

题意 ：

• 让我们构造一个长度为n的只包含’b’和‘r’的字符串，要求所构造的字符串的子序列满意的个数最多
• 满意的定义：对于序列[l,r]，其中’r’出现的个数是奇数，那么就是满意的
• 按字典序输出前100个

思路 ：

• 找最大对数，肯定是全r最优，直接计算即可
• 首先需要求$[l,r]$内‘r’的个数，可以想到前缀和
• 我们定义数组$g[N]$，$g[i]$表示字符串前i位里r出现的个数
• 那么对于序列$[l,r]$，r出现的个数就是$g[r]-g[l-1]$
• 只有$g[r]$和$g[l-1]$的奇偶性不一致时，r出现的个数会是奇数，该字符串才满意
• 设这些前缀和中有x个奇数，y个偶数，则满足$x+y=n$，且此时我们的答案就是$x\ast y$
• 则由均值不等式$x+y\ge 2\sqrt{xy}$得到$xy\le (\frac{x+y}{2}{)}^2$，当且仅当x=y时取等号
• 即$x=y=\frac{n}{2}$时，答案最大
• 因为只需要输出前100个，搜索即可
• x*y为$\frac{n+1}{2}\ast \frac{n+2}{2}$，x和y分别不能超过$\frac{n+2}{2}$
• dfs传入四个参数，当前字符串的第i位，当前字符串的前缀和为奇数的个数，为偶数的个数，前i-1位r的个数
• dfs时首先判断已经输出字符串的个数和前缀和分别为奇数偶数的个数
• 然后是判断当前这位是否已经第n位
• 再根据前i-1位r的个数分别dfs
• 观察样例1，n=1时，输出"r"，第0位以前的‘r’的个数的前缀和是0，偶数，因此dfs第一次传入参数在第二个位置应为1
• 字典序最小表现在每次dfs都是先放b后放r的
• 注意要开long long，因为输出个数时溢出了

#include <iostream> #include <algorithm> #include <cstring> #include <queue> #define debug(a) cout << #a << " = " << a << endl; #define x first #define y second using namespace std; typedef long long ll;const int N = 1e5 + 10;ll n; ll out; ll cnt = 0; char s[N];// 字符串中第i位，前缀和偶数个数，前缀和奇数个数，字符串前i-1位r的个数 void dfs(ll i, ll even, ll odd, ll last) {// 输出100个，或者奇数或偶数数量超限if (cnt >= 100 || even > out || odd > out)return ;// 一个字符串完成if (i == n){cnt ++ ;cout << s << endl;return ;}if (last % 2 == 0) // 字符串前i-1位r的个数是偶数{s[i] = 'b';dfs(i + 1, even + 1, odd, last); // 在第i位放'b'，前缀和为偶数的个数加一，为奇数的个数不变s[i] = 'r';dfs(i + 1, even, odd + 1, last + 1);}else // 字符串前i-1位r的个数是奇数{s[i] = 'b';dfs(i + 1, even, odd + 1, last);s[i] = 'r';dfs(i + 1, even + 1, odd, last + 1);} }int main() {ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);cin >> n;cout << ((n + 1) / 2) * ((n + 2) / 2) << endl;// LL ans = 1;// LL tmp = 1;// for(int i = 2; i <= n; i ++ )// {// if(i % 2) tmp ++;// ans += tmp;// }// m = (n + 2) / 2;// cout << ans << endl;out = (n + 2) / 2;dfs(0, 1, 0, 0);return 0; }

总结

以上是生活随笔为你收集整理的Journey to Un‘Goro 贪心，找规律，搜索（沈阳）的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。