7 条题解

  • 22
    @ 2023-6-2 15:23:33
    题目大意
            给出一串只由O和o组成字符串，相邻的oo会组成O，相邻的OO会消失，求字符串最终的效果。

    完整思路
            通过题意,可知第i个字符s[i]对字符串产生的变化只与该字符相邻的元素有关,根据这个特点，我们可以看出这是一个栈模拟问题。

    1、遍历字符串，栈中无元素或栈顶元素与s[i]不相同时，将s[i]压入栈。

    2、当栈非空时，判断栈顶元素是否为小泡泡‘o’且s[i]也为小泡泡,这时将栈顶元素出栈,此时并不能将合成的大泡泡'O'直接压入栈中,因为可能栈顶的小泡泡出栈后,栈顶变成了大泡泡,这时需要将大泡泡消去,若栈顶不为大泡泡时,将大泡泡压入栈中。

    3、若s[i]和栈顶元素同为大泡泡时，将栈顶元素出栈。

    4、将栈顶剩余元素逐个出栈，逆序输出结果。



    题解 
    
#include <bits/stdc++.h>
using namespace std;
string s;
stack<char> st;
string str;
int main()
{
    cin >> s;
    st.push(s[0]);
    for (int i = 1; i < s.length(); i++)
    {
        if (st.empty() || st.top() != s[i])
        {
            st.push(s[i]);
            continue;
        }
        if (!st.empty() && st.top() == s[i] && s[i] == 'o')
        {
            st.pop();
            if (!st.empty() && st.top() == 'O')
                st.pop();
            else
                st.push('O');
        }
        else if (!st.empty() && st.top() == s[i] && s[i] == 'O')
        {
            st.pop();
        }
    }
    while (!st.empty()) 
    {
        str += st.top();
        st.pop();
    }
    if(str.length() == 0)
        cout << -1;
    for (int i = (int)str.length() - 1; i >= 0; i--) 
        cout << str[i];
}
    • 16
      @ 2023-6-3 17:28:55 
      #include<bits/stdc++.h>
using namespace std;

int main(){
    string s;
    while(cin >> s){
        stack<char> st;
        string str;
        st.push(s[0]);
        for(int i = 1; i < s.length(); i++){
            if(st.empty() || st.top() != s[i]){
                st.push(s[i]);
                continue;
            }
            if(!st.empty()&&st.top()==s[i]&&s[i]=='o'){
                st.pop();
                if(!st.empty()&&st.top()=='O') st.pop();
                else st.push('O');
            }
            else if(!st.empty()&&st.top()==s[i]&&s[i]=='O'){
                st.pop();
            }
        }
        while(!st.empty())
        {
            str+=st.top();
            st.pop();
        }
        for(int i=(int)str.length()-1;i>=0;i--)
            cout<<str[i];
        cout<<endl;
        if(str.length() == 0)
        cout << -1;
    }   
}
      • 12
        @ 2023-6-2 21:11:20

        栈思想 模拟：

        ooOOoooO t=o o 空栈，入栈

        t=o oo->O 非空，融合，弹出o，压入O

        t=O OO-> 非空，融合，弹出O

        t=O O 空栈，入栈

        t=o Oo 非空，融合，压入o

        t=o Ooo->OO-> 非空，融合,弹出o,压入O，栈首与栈首后一位可融合，将栈首作为新的临时元素，再来一次play（写一个判断函数,判断栈首与栈首后一位是否可融合，若不可融合则过，否则循环）

        t=o o 空栈，入栈

        t=O oO 非空，融合，压入O

        此时栈从上到下排列如下 Oo

        算法结束后应该倒序输出

        倒序输出方法如下：先一个一个输出至string容器中，再反转string即可

        算法抽象如下： i 若空栈，压入 ii 若非空，融合，操作，判断栈首与后一位是否可融合，是则继续融合，否则过 如果可以继续融合，那么函数参数a变为栈首元素，弹出栈首，继续操作 考虑到只有Ooo可以继续，所以可以简化算法

        Ooo->OO ooo->oO

        注意：oo会空栈

        获取知识点：

        对于stack,pop是弹出，top是获取！ 把STL传入参数用&引用

        #include<cstdio>
#include<iostream>
#include<stack>
#include<string>
using namespace std;
int fuse(char a,char b) { //融合函数,无效操作返回0，两个小的返回1，两个大的返回2
	if(a=='o' && b=='O')	return 0;
	if(a=='O' && b=='o')	return 0;
	if(a=='o' && b=='o')	return 1;
	if(a=='O' && b=='O')	return 2;
}
bool judge(stack<char> a) { //判断栈首与后一位是否可融合
	char temp;
	temp=a.top();
	a.pop();
	if(fuse(a.top(),temp))	return true;
	else return false;
}
void play(stack<char> &old,char a) { //从字符串逐次获取元素，进行如下操作
	if (old.empty()) { //i:若栈为空，压入栈
		old.push(a);
		return;
	} else { //ii:若非空，融合，操作，判断栈首与后一位是否可融合，是则继续融合，否则过
		int ans;//存放fuse的结果
		char temp=old.top();
		ans=fuse(a,temp);
		if(ans==0) {
			old.push(a);
			return;
		} else if(ans==1) {	//oo融合为O
			old.pop();
			old.push('O');
			char temp=old.top();
			old.pop();
			if(!old.empty()	&& old.top()=='O')	old.pop();
			else	old.push(temp);
		} else if(ans==2) {	//OO破碎
			old.pop();
		}
	}
	
}
string copy(stack<char> &sta) {
	string a;
	while(!sta.empty()) {
		a+=sta.top();
		sta.pop();
	}
	return a;
}
void reverseStr(string& str) //字符串反转 
{ 
	int n = str.length(); 
	for (int i = 0; i < n / 2; i++) 
		swap(str[i], str[n - i - 1]); 
} 
int main() {
	string str1;
	while(cin>>str1) {
		stack<char> old;
		for(int i=0; i<str1.length(); i++) {
			char now=str1[i];
			play(old,now);
		}
		string ans;
		ans=copy(old);
		reverseStr(ans);
		cout<<ans<<endl;
	}
	return 0;
}

        注意下,只有80分

        所以我又改了一下

        #include <stdio.h>
#include <cstring>
#include <stack>
#include <iostream>
#include <algorithm>
using namespace std;
int main(){
	char str[101];
	while(scanf("%s",str)!=EOF){
		stack<char> s;
	//	s.push(str[0]);
		for(int i=0;i<strlen(str);i++){
			s.push(str[i]);
			while(s.size()>1){//更新 
				char c=s.top();
				s.pop();
				char c1=s.top();
				s.pop();
				if(c==c1&&c=='o'){
					s.push('O');
				}else if(c==c1&&c=='O'){
					continue;
				}else if(c!=c1){
					s.push(c1);//注意入栈的顺序 
					s.push(c);
					break;
				}
			}
		}
		int num=0;
		char str1[101];
		while(!s.empty()){
			str1[num++]=s.top();
			s.pop();
		}
		for(int i=num-1;i>=0;i--){
			printf("%c",str1[i]);
		}
		printf("\n");
	}
	return 0;
}

        结果还是80分……

        然后我就发现,我没看到要输出-1

      • 3
        @ 2023-10-22 16:46:25

        本题结果得置换一下，不然输出的是反的

        #include <bits/stdc++.h>
using namespace std;
stack<char> sta,answer;
string a;
int main(){
    cin>>a;
    for (int i=0;i<a.length();i++){
        if (sta.empty())sta.push(a[i]);
        else if (sta.top()==a[i]){
            sta.pop();
            if (a[i]=='o'){
                if (sta.empty())sta.push('O');
                else if (sta.top()=='O')sta.pop();
                else sta.push('O');
            }
        }
        else sta.push(a[i]);
    }
    if (sta.empty()){
        cout<<-1;
        return 0;
    }
    //颠倒sta->answer
    while (sta.empty()!=1){
        answer.push(sta.top());
        sta.pop();
    }
    //输出
    while (answer.empty()!=1){
        cout<<answer.top();
        answer.pop();
    }
}

        另外请教一下，怎么写带颜色的题解（就是代码）

        • @ 2024-1-22 18:06:13

          在for循环那里, "a.length()"外要有“int( )” 如下：

          for(int i=1;i<int(a.length());i++)
        • @ 2024-1-30 14:09:44

          @ 没有只会提示，不耽误AC

      • 2
        @ 2024-3-10 19:53:05 
        #include <bits/stdc++.h>
using namespace std;
string s;//定义字符串
int main(){
    cin>>s;
    while (true){
    	int now=s.find("oo"),now1=s.find("OO");
    	if (now==-1&&now1==-1)break;
    	if (now==-1)s.erase(now1,2);
    	else if (now1==-1)s.replace(now,2,"O");
    	else if (now<now1)s.replace(now,2,"O");
    	else if (now1<now)s.erase(now1,2);
	}
	if (s.size())cout<<s;
	else cout<<-1;
    return 0;
}
      • 2
        @ 2024-1-30 14:48:09

        万恶的return value 3221225477 害我检查一个点，终于弄对了，累死 😵‍💫😵😭 以下是AC代码，请不要走我的老路

        #include <bits/stdc++.h>
using namespace std;
string s;
stack<char> a,ans;
int main()
{
	cin >> s;
	a.push(s[0]);
	for (int i = 1;i < (int)s.length();i++)
	{
		if (a.empty())
		{
			a.push(s[i]);
		}
		else if (s[i] == 'o' && a.top() == 'o')
		{
			a.pop();
			if (a.empty())
			{
				a.push('O');
				continue;
			}
			else if (a.top() == 'O')
			{
				a.pop();
			}
			else
			{
				a.push('O');
			}
		}
		else if (s[i] == 'O' && a.top() == 'O')
		{
			a.pop();
		}
		else if (s[i] == 'O' && a.top() == 'o')
		{
			a.push('O');
		}
		else
		{
			a.push('o');
		}
	}
	if (a.empty() == 1)
	{
		cout << -1;
		return 0;
	}
	while (!a.empty())
	{
		ans.push(a.top());
		a.pop();
	}
	while (!ans.empty())
	{
		cout << ans.top();
		ans.pop();
	}
	return 0;
}//请谨慎使用
        • -2
          @ 2023-10-23 19:53:06

          AC 代码

          //-----pp.cpp----- By JakeHao
#include <iostream>
#include <cstring>
#include <stack>
using namespace std;
stack<char> sta,ans;
int main()
{
    string a;
    char x;
    cin >> a;
    sta.push(a[0]);
    for(int i=1;i<int(a.length());i++)
    {
        x=' ';
        if(!sta.empty())
        {
            x=sta.top();        
        }
        sta.push(a[i]);
        if(sta.size()>=2)
        {
            if(x=='o'&&sta.top()=='o')
            {
                sta.pop();
                sta.pop();
                sta.push('O');
                if(sta.size()>=2)
                {
                    x=sta.top();    
                    sta.pop();
                    if(sta.top()=='O'&&x=='O')
                    {
                        sta.pop();
                    }
                }
            }
            else if(x=='O'&&sta.top()=='O')
            {
                sta.pop();
                sta.pop();
            }
        }
    }
    if(sta.empty())
    {
        cout << -1;
    }
    else
    {
        while(!sta.empty())
        {
            ans.push(sta.top());
            sta.pop();
        }
        while(!ans.empty())
		{
			cout << ans.top();
			ans.pop();
		}
    }
    return 0;
}
          • @ 2024-1-30 14:10:27

            pp.cpp??????????????????????????????????????????????????????????????????????????????????

        • 1

        吐泡泡

        信息

        ID
        128
        时间
        1000ms
        内存
        256MiB
        难度
        4
        标签
        递交数
        1474
        已通过
        646
        上传者
        1. 关于
        2. 联系我们
        3. 隐私
        4. 服务条款
        5. 版权申诉
        6. Language
        7. 兼容模式
        8. 主题
        3. Worker 0, 16ms
        4. Powered by Hydro v4.9.24 Community, Modified by hetao