首页 > 试题广场 >

吐泡泡

[编程题]吐泡泡
  • 热度指数：482 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M
  • 算法知识视频讲解
\hspace{15pt}小鱼儿会吐出两种泡泡：大泡泡 \texttt{，小泡泡 \texttt{；两种泡泡的变化规则如下：
\hspace{23pt}\bullet\,任意两个相邻的小泡泡会融合成一个大泡泡；
\hspace{23pt}\bullet\,任意两个相邻的大泡泡会相互爆炸，变成空白（即消失）。
\hspace{15pt}上述合并与爆炸过程自左至右依次进行，直至无法再进行任何操作。

\hspace{15pt}例如，对于初始泡泡序列 \texttt{，经过一段时间后会变成 \texttt{。


输入描述:
\hspace{15pt}第一行输入一个整数 T\left(1\leqq T\leqq 10\right) 代表数据组数。
\hspace{15pt}接下来 T 行，每行一个仅由 'O' 和 'o' 构成的字符串 s，字符串长度不超过 10^5。


输出描述:
\hspace{15pt}每组输出仅包含一行，输出一行字符串代表小鱼儿吐出的泡泡经过融合以后所剩余的泡泡。
示例1

输入

1
ooOOoooO

输出

oO

说明


示例2

输入

1
OOOOOOOOOOOOOOOooooooooooooooooooOOoOoOoOOOoOoOoOOoOooOoOOoOoOoOoOoOoOoOoOoOooOoOoOOoooOOOOoOOoooOOoOOOOOooOoOOOoOOoooOoOOOooOooooOoOooOoOooOoOooOoOOOOOOOOOOOOOOoOoOoOooOOoOooOoOOoOoOOOOooooOOOOOooooooOOOOOOoooooOoOooOoOoOoooOoOOOOoOoOoOOOOOOOOOOoOooOoOooOOoOOoOooOooOOoooOOOoOoOooOOooOoOOOoOOoOOOoOooOoOOOooOOoooOOoOOoOooOOOOoOooOoOoOoOooOoOoO

输出

oOoOoOoOoOoO

说明



备注:

算法知识视频讲解
开通博客
头像 19_hanhan
发表于 2020-05-30 23:42:08
这道题明明很简单的，我却被牛牛难得一见的多组输入卡到自闭，一度怀疑自己是不是sb 题目 题目描述： 小鱼儿吐泡泡，嘟嘟嘟冒出来。小鱼儿会吐出两种泡泡：大泡泡"O"，小泡泡"o"。 两个相邻的小泡泡会融成一个大泡泡,两个相邻的大泡泡会爆掉。 （是的你没看错，小气泡和大气泡 展开全文
去ta的博客 赞 (19) 回复(0) 收起
头像 信仰不悔
发表于 2020-08-14 16:51:42
通过题意,可将输入字符串分成单个字符,每个字符逐个输入,且每次输入对字符串产生的变化只与该字符相邻的元素有关,根据这个特点，我们很容易看出这是一个简单的栈模拟问题。 解题思路：1、栈中无元素或栈顶元素与输入元素不相同时，将输入元素压入栈。2、当栈非空时，判断栈顶元素是否为小泡泡‘o’且输入元素也为小 展开全文
去ta的博客 赞 (7) 回复(1) 收起
头像 虽然吧_但是
发表于 2020-05-23 22:48:56
写过括号匹配这种题就很容易想到用栈来解决此类问题首先要理解栈是什么，它是一种线性表你可以将它理解为一个容器 但他只能从栈顶出，栈顶入，后进先出实际定义（来自百度百科）：栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈 展开全文
去ta的博客 赞 (6) 回复(0) 收起
头像 微澜尛雨
发表于 2021-12-08 19:56:46
题目考点：STL、栈（或队列），另外注意多组输入 题目大意：给出一系列泡泡，两个小泡泡在一起会变成大泡泡，两个大泡泡在一起会爆炸；求这些泡泡的最终状态。 题目分析: 依次从前往后遍历压入栈即可（入栈时将当前泡泡与栈顶泡泡相比较，两小泡泡变成大泡泡，两大泡泡爆炸），唯一注意点就是两个小泡泡变成 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 MedicineCliff
发表于 2024-03-10 17:13:19
今日栈x2 依旧当作笔记来写以防遗忘 #include #include using namespace std; int main() { string s; while(cin>>s) { int n=s.length(),i; stack<char>st 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 包子超好吃
发表于 2021-04-04 20:38:22
核心没什么核心，其实就是括号匹配的板子题，基本上一模一样；注意的地方，例如以下代码 if(!s.empty()&&s.top()=='O')如果把！s.empty()放到&&后面那么编译的时候会出问题，所以栈的非空判断要放在前面；处理完之后呢，栈中保存的结果是正确的， 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 死于算法，生于算法
发表于 2021-11-03 19:27:47
主要是要注意是多组输入，其次就是要小心越界 我这里是手写的栈 #include<iostream> #include<queue> using namespace std; const int N=110; string str; int main() { while 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 夜语声烦-
发表于 2022-06-11 13:19:55
吐泡泡 #include <iostream> #include <algorithm> #include <cstring> #include <stack> using namespace std; char a[110]; stack< 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 矫健的母单花国企上岸了
发表于 2022-02-10 17:59:20
解题思路： 递归（算是吧） 注意：多组数据！！！ ">#include<string.h> #include<stdlib.h> char* f(char* a){ char ss[200]; char sss[200]; for(int i = 0 展开全文
去ta的博客 赞 (1) 回复(0) 收起
头像 ciallobit
发表于 2025-05-31 17:54:29
import sys def main(): lines = sys.stdin.read().splitlines() T = len(lines) ret = [] idx = -1 for _ in range(T): idx += 展开全文
去ta的博客 赞 (1) 回复(0) 收起

问题信息

栈
上传者：牛客303862号
难度：
1条回答 1402浏览

热门推荐

通过挑战的用户

查看代码

相关试题

吐泡泡

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号