首页 > 其他分享 >C. Qingshan Loves Strings 2

C. Qingshan Loves Strings 2

时间:2024-07-03 23:42:00浏览次数:19  
标签:01 int Qingshan back pop ++ Loves push Strings

原题链接

题解

1.当10个数不一致时,无论怎样都不成立
2.当01个数一致时,是否一定存在某种方法使得成立呢?
3.对于长度为 \(k\) 的字符串 \(s\),若不合法,那我在旁边添加一个01,则我们可以连续删除两边的配对数字,且至少能删除一对,且经过若干轮的删除一定能使字符串长度减小

总的来说,我们把插入若干个01串使得对称的过程,看成插入若干个01串,使得两端对称的部分消除

code

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int t;
    cin>>t;

    while(t--)
    {
        int n;
        cin>>n;

        string s;
        cin>>s;

        deque<int> q,id;
        int cnt=0;
        for(int i=0;s[i];i++)
        {
            q.push_back(s[i]-'0');
            cnt+=q.back();
            id.push_back(i);
        }
        id.push_back(n);
        if(cnt*2!=n)
        {
            puts("-1");
            continue;
        }

        queue<int> ans;
        int l=0,r=n;//代表当前插入的位置

        while(q.size()>1)
        {
            if(q.front()==q.back())
            {
                if(q.back()==0)
                {
                    q.pop_front();
                    l++;
                    ans.push(r);

                    q.push_back(0);
                    r++;
                }
                else
                {
                    q.pop_back();
                    r++;
                    ans.push(l);

                    q.push_front(1);
                    l++;
                }
            }
            else
            {
                q.pop_back();
                q.pop_front();
                l++;
                r--;
            }
        }

        cout<<ans.size()<<endl;
        while(ans.size())
        {
            cout<<ans.front()<<" ";
            ans.pop();
        }

        puts("");
    }
    return 0;
}


标签:01,int,Qingshan,back,pop,++,Loves,push,Strings
From: https://www.cnblogs.com/pure4knowledge/p/18282765

相关文章

  • [题解]AT_abc343_g [ABC343G] Compress Strings
    思路首先假设有两个串\(a,b\),如果\(b\)是\(a\)的子串,且\(a\neqb\)则不需要考虑\(b\);如果\(a=b\),则如需要保留一个\(a\)。做完上述操作后,显然最终的答案是由这些串按照一定顺序拼接起来,再删掉重叠部分。例如:abbcc与ccdde拼接为abbccccdde,发现cc是重复的,所以......
  • fasterxml ToStringSerializerBase报错
    ToStringSerializerBase报错报错内容整合dubbo时报错Causedby:java.lang.NoClassDefFoundError:com/fasterxml/jackson/databind/ser/std/ToStringSerializerBase atcom.fasterxml.jackson.datatype.jsr310.JavaTimeModule.<init>(JavaTimeModule.java:158)~[jackson-dataty......
  • c++ stringstream
    转载:https://blog.csdn.net/jllongbell/article/details/79092891v前言:  以前没有接触过stringstream这个类的时候,常用的字符串和数字转换函数就是sscanf和sprintf函数。开始的时候就觉得这两个函数应经很叼了,但是毕竟是属于c的。c++中引入了流的概念,通过流来实现字......
  • CF Everyone Loves to Sleep 每个人都喜欢睡觉
    我这个蒟蒻又来做CF了我做的是“EveryoneLovestoSleep”“每个人都喜欢睡觉”Vlad,likeeveryoneelse,lovestosleepverymuch.EverydayVladhastodo n things,eachatacertaintime.Foreachofthesethings,hehasanalarmclockset,the i -......
  • LeetCode Greatest Common Divisor of Strings All In One
    LeetCodeGreatestCommonDivisorofStringsAllInOneLeetCode1071errorsfunctiongcdOfStrings(str1:string,str2:string):string{letresult=``;lettemp=[];if(str1.length>str2.length){letreg=newRegExp(str2,'g'......
  • 题解:CF1954F Unique Strings
    link计数类*3100首次独立过纪念版题解。首先我们考虑一个去重的问题。貌似针对循环同构去重的问题,只能从循环节上入手。那么我们考虑设\(dp(d)\)为最小循环节长度恰好为\(d\)不同方案数个数,则答案为:\[\sum_{d=1}^ndp(d)=\sum_{d|n}\frac{dp(d)}{d}\]这似乎是一条可行......
  • LeetCode 1915. Number of Wonderful Substrings
    原题链接在这里:https://leetcode.com/problems/number-of-wonderful-substrings/description/题目:A wonderful stringisastringwhere atmostone letterappearsan odd numberoftimes.Forexample, "ccjjc" and "abab" arewonderful,but "ab&......
  • 蓝桥杯-错误票据(两种写法stringstream和扣字符)
    某涉密单位下发了某种票据,并要在年终全部收回。每张票据有唯一的ID号。全年所有票据的ID号是连续的,但ID的开始数码是随机选定的。因为工作人员疏忽,在录入ID号的时候发生了一处错误,造成了某个ID断号,另外一个ID重号。你的任务是通过编程,找出断号的ID和重号的ID。假设断号不可能......
  • LeetCode 2060. Check if an Original String Exists Given Two Encoded Strings
    原题链接在这里:https://leetcode.com/problems/check-if-an-original-string-exists-given-two-encoded-strings/description/题目:Anoriginalstring,consistingoflowercaseEnglishletters,canbeencodedbythefollowingsteps:Arbitrarily split itintoa sequ......
  • ABC240Ex Sequence of Substrings
    ABC240ExSequenceofSubstringsLIS的好题改编。约定\(S(l,r)\)为字符串\(s\)中第\(l\)位到底\(r\)​位。\(S(l,r)<S(x,y)\)为字符串中\([l,r]\)的子串字典序比\([x,y]\)的子串小。前置LIS的\(n\logn\)求法。题解我们考虑按照类似于朴素LIS的方式设状......