建个网站大概多少钱,品牌推广方案,广州市网站建设在哪里,怎么样模仿网站从今天开始博主会每天做一道算法题备战蓝桥杯#xff0c;并分享博主做题的思路#xff0c;有兴趣就加入我把#xff01;
算法题目#xff1a;
有一个长度为 N 的字符串 S #xff0c;其中的每个字符要么是 B#xff0c;要么是 E。
我们规定 S 的价值等于其中包含的子…从今天开始博主会每天做一道算法题备战蓝桥杯并分享博主做题的思路有兴趣就加入我把
算法题目
有一个长度为 N 的字符串 S 其中的每个字符要么是 B要么是 E。
我们规定 S 的价值等于其中包含的子串 BB 以及子串 EE 的数量之和。
例如BBBEEE 中包含 22 个 BB 以及 22 个 EE所以 BBBEEE 的价值等于 44。
我们想要计算 S 的价值不幸的是在我们得到 S 之前约翰将其中的一些字符改为了 F。
目前我们只能看到改动后的字符串 S对于其中的每个 F我们并不清楚它之前是 B 还是 E。
请你计算改动前的 S 有多少种可能的价值并将所有可能价值全部输出。
输入格式
第一行包含一个整数 N。
第二行包含改动后的字符串 S。
输出格式
第一行输出一个整数 K表示改动前的 S 的可能价值的数量。
接下来 K 行按照升序顺序每行输出一个可能价值。 输入样例1
4
BEEF输出样例1
2
1
2输入样例2
9
FEBFEBFEB输出样例2
2
2
3输入样例3
10
BFFFFFEBFE输出样例3
3
2
4
6 思路
我们看字符串的F和E太过于麻烦我们给抽象成01字符串更清晰的看出关系 现在有这样一段字符串 xx01xxx0010xxx011xx110 这段字符串中有四段x组成的子字符串而这四段子字符串都是相互独立的修改其中任意一端都不会影响到其他三段的数值所以我们可以把这四段各自对应的情况拿出来单独讨论最后再合并到一起就能求出答案
步骤:
第一步先分析每一段连续的x的价值有哪些。 第二步再分析所有段的价值之和有哪些 k为x的数量 情况1xxxxx 长度为五的x最多有四个相邻对所以最大值是4最小值自然是0 取值012……k-1 情况20xxxxx/1xxxxx/xxxxx0/xxxxx1 当我们x全取取相邻相同的数时最大值就是k最小值是0 取值012……k 情况30xxxxxx0/1xxxxxx1 最多就是都取成一样的 k1个 最少 0个 但是我们中间画五个x最少是0个但是如果中间是偶数呢大家自己模拟一下最少就会有一个所以情况三就要分情况 最多 k1
最少 k1是偶数0 k1是奇数1 大家自己画图模拟一下很明了 现在要最大和最小都有了自然要考虑中间的数能不能取到每当我们改变一个数就会改变两个数对的值所以可以取值的数就是公差为2的等差数列 所以取值k1,k-1,k-3,……,0/1(取决于k的奇偶性) 第四种情况 0xxxxx1/1xxxxx0 最多k个和左边或者右边相同 最小依旧是分情况讨论 k是偶数 0个 k是奇数 1个 都是画图通俗易懂 取值每改变一个x影响周围的两数对所以取值依旧是公差为2的等差数列 k,k-2,k-4,……,1/0(取决k的奇偶性)
现在我们把每一种情况和段落都分析完了可以进行合并了
问题1如果我们合并两个公差为2的等差数列会得到什么样的结果 答案会得到一个新的公差为2的等差数列最小值是两个数列的最小值相加最大值是两个数列的最大值相加 问题二如果我们合并一个公差为2的等差数列和一个公差为1的等差数列会得到什么样的结果 答案会得到一个公差为一的等差数列最小值最大值同上 最终做法 第一步先求中间段。 第二步再求两边的段 第三步合并第一步和第二步的结果 题解代码
#include iostream
#include cstring
#include algorithmusing namespace std;int n;
string s;int main()
{cin n s;if (s string(n, F)){cout n endl;for (int i 0; i n; i )cout i endl;}else{int l 0, r n - 1;while (s[l] F) l ;while (s[r] F) r -- ;int low 0, high 0;auto str s;for (int i l; i r; i ){if (str[i] F){if (str[i - 1] B) str[i] E;else str[i] B;}if (i l str[i] str[i - 1]) low ;}str s;for (int i l; i r; i ){if (str[i] F) str[i] str[i - 1];if (i l str[i] str[i - 1]) high ;}int ends l n - 1 - r, d 2;if (ends) high ends, d 1;cout (high - low) / d 1 endl;for (int i low; i high; i d)cout i endl;}return 0;
}
这是完全根据题解写的代码其实其中一种思路大家可以参考一下也可以自己按照思路写代码如果看不懂的话可以在评论区指出或者私信博主
对大家有帮助的话不要吝啬手里的点赞关注呀以后每天博主都会带来优质内容。
