2020ICPC沈阳站 D-Journey to Un'Goro
2021/9/1 23:09:06
本文主要是介绍2020ICPC沈阳站 D-Journey to Un'Goro,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
题目链接:2020ICPC沈阳站 D-Journey to Un'Goro
题目大意:
给定一个整数\(n(n\leq 1e5)\)表示一个只由字符\(r\)和\(b\)构成的字符串序列的长度,对于该序列的任意一个子序列,当该子序列中\(r\)的个数为奇数时,则称该子序列为“满意”。要求构造一系列这样的字符串序列使得其中“满意”的子序列个数最大,输出最大个数,另外,这样的序列一般不唯一,题目要求按字典序输出前\(100\)个构造的序列。
题解:
这里要从序列前缀中\(r\)个数的奇偶性上去考虑。
设\(P_i\)表示长度为\(i\)的字符序列前缀中\(r\)的个数,那么由题意可知子序列\((i, j)\)中\(r\)的个数为\(P_j - P_{i-1}\),当且仅当\(P_j\)与\(P_i-1\)的奇偶性不同时,\(P_j-P_{i-1}\)为奇数。
那么题目就转化为构造这样的字符串序列,使得序列\(P_0, P_1, P_2...P_n\)中满足\(P_i\)和\(P_j\)的奇偶性不同的对数最大,设序列\(P_0, P_1, P_2...P_n\)中奇数个数为\(X\),偶数个数为\(Y\),则满足\(P_i\)和\(P_j\)的奇偶性不同的对数为\(XY\),很容易想明白\(XY=\lfloor(n+1)/2\rfloor\times\lceil(n+1)/2\rceil\),其实就是\(X\)和\(Y\)各取一半时乘积最大。
而同时发现题目只要求输出前\(100\)个序列,因此可以搜索+剪枝过掉,在\(dfs\)时分别记录当前偶数个数\(cnt_0\)和奇数个数\(cnt_1\),当\(max\{cnt_0,cnt_1\}>\lceil(n+1)/2\rceil\)时就剪掉。
#include <iostream> #include <cstdio> using namespace std; int n, cnt, limit; char S[100010]; void dfs(int k, int cnt0, int cnt1, bool st) { if (cnt0 > limit || cnt1 > limit) return; if (k == n) { printf("%s\n", S); if (++cnt >= 100) exit(0); return; } S[k] = 'b'; dfs(k + 1, cnt0 + (st ^ 1), cnt1 + st, st); st ^= 1; S[k] = 'r'; dfs(k + 1, cnt0 + (st ^ 1), cnt1 + st, st); } int main() { scanf("%d", &n); long long ans = 1ll * ((n + 1) / 2) * ((n + 2) / 2); limit = (n + 2) / 2; printf("%lld\n", ans); dfs(0, 1, 0, 0); return 0; }
这篇关于2020ICPC沈阳站 D-Journey to Un'Goro的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26解决google chrome helper 内存占用较高!
- 2024-04-01got an unexpected keyword argument
- 2024-03-30维多利亚的秘密 golang入坑系统
- 2024-03-29mongodb sort by date
- 2024-03-29go swagger
- 2024-03-25mongodb cdc
- 2024-03-25how to use go in vscode
- 2024-03-22mongooseserverselectionerror: connect econnrefused ::1:27017
- 2024-03-21pymongo insert_many
- 2024-03-18projection mongodb