首页 > 其他分享 >Educational Codeforces Round 110 (Rated for Div. 2) C. Unstable String(状态机)

Educational Codeforces Round 110 (Rated for Div. 2) C. Unstable String(状态机)

时间:2023-04-14 20:22:59浏览次数:57  
标签:Educational Rated LL cin 状态机 字符串

https://codeforces.com/contest/1535/problem/C

题目大意:

给定一个字符串s,由 1 0 ?组成:?每次都可以任意替换成0或者1

问我们这个子字符串中,能够组成010101这样两两互不相等的字符串的数量最大是多少?
input 
3
0?10
???
?10??1100
output 
8
6
25

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=2e5+7;
LL f[N][2];
int main()
{
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        memset(f,0,sizeof f);
        string s;
        cin>>s;
        s="?"+s;
        LL ans=0;
        for(LL i=1;i<s.size();i++)
        {
            if(s[i]=='0') f[i][1]=f[i-1][0]+1;
            else if(s[i]=='1') f[i][0]=f[i-1][1]+1;
            else
            {
                f[i][1]=f[i-1][0]+1;
                f[i][0]=f[i-1][1]+1;
            }
            ans+=max(f[i][1],f[i][0]);
        }
        cout<<ans<<endl;
    }
    return 0;
}

标签:Educational,Rated,LL,cin,状态机,字符串
From: https://www.cnblogs.com/Vivian-0918/p/17319833.html

相关文章

  • Educational Codeforces Round 120 (Rated for Div. 2)
    题目链接C核心思路这是一个很好的二分的题目,首先我们判断题目可不可二分,很显然是可以的把。因为假设我们x是可以的话,x+1...肯定也是可以的,但是x-1,x-2....这些又是不可以的。好,接下来思考二分刚开始的左右边界,左边届很好想,关键是右边界。这个其实也不难。因为我们最坏肯定是全......
  • CodeTON Round 2 (Div. 1 + Div. 2, Rated, Prizes!)
    CodeTONRound2(Div.1+Div.2,Rated,Prizes!)A.Two0-1Sequencesvoidsolve(){intn=read(),m=read(),ans=1;strings,t;cin>>s>>t;//cout<<s<<t<<endl;for(inti=t.size()-1,j=s.size()-1;i>=1&......
  • Enemy状态机设计思路
    前言:为了更清晰的认识状态机并且理清Enemy设计思路,所以整理了一下Enemy的代码设计逻辑做了一张简单的思维图先进行一个简单的认识干货:FMS有限状态机状态机类似于动画器(animator),动画器可以简单清晰地管理游戏角色的动画:待机、跳跃、下落、跑步……,状态机的目的也是如......
  • Educational Codeforces Round 146 (Rated for Div. 2)
    Preface补题ing值得一提的时补这场的时候先是遇上了CF的12小时大维护,后面又遇到了评测机崩了测不了也是有点有意思的说A.Coins傻逼题,首先考虑\(2|n\)时一定有解\(x=\frac{n}{2},y=0\),否则若\(2\nmidn\and2|k\)则由裴蜀定理知此时一定无解否则\(y\)必为奇数,我们令\(x=\fra......
  • 马尔科夫链文本生成(散列表,状态机,马尔科夫链)
    Codingame散列表为主题的练习题中,马尔科夫链文本生成吸引到了我的注意力。它集合了马尔科夫链,状态机和散列表三个方面的学习内容。其中,n-gram马尔科夫链运用到了文本聊天机器人的设计中,还是蛮有启发性的,应该是chatgpt之前的一项经典技术。下面简单讲讲这个编程练习题。目标制作......
  • Do you know the bitwise sum sample demonstrated in "Neural Networks and Deep Lea
    Doyouknowthebitwisesumsampledemonstratedin"NeuralNetworksandDeepLearning"byautor MichaelNielsen?Yes,Iamfamiliarwiththebitwisesumexampledemonstratedin"NeuralNetworksandDeepLearning"byMichaelNielsen......
  • Edu Round 板刷计划 4. Educational Codeforces Round 4 题解
    ChangeLog:2023.04.06开坑.A-TheTextSplitting弱智题.枚举分出来多少个长度为\(p\)的串,则能计算出长度为\(q\)的串有多少个,若合法则直接输出即可.无解输出-1.Samplesubmission.B-HDDisOutdatedTechnology比A还弱智.直接记录每个数的位置,然后模拟一......
  • 状态机图
    笔记软件在2023/4/614:26:40推送该笔记状态机图用于模拟各个类对象,用例和整个系统的动态行为。换句话说,当一个状态机创建它所附着的对象,该对象成为状态机的所有者时,例如,状态机附加的对象可以是类,用例甚至整个系统。​​什么是UML中的状态机图?参考状态机图是一种行为,它指定对......
  • Educational Codeforces Round 146 (Rated for Div. 2)
    A.Coins#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongintread(){intx=0,f=1,ch=getchar();while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();if(ch......
  • Educational Codeforces Round 124 (Rated for Div. 2)
    题目链接C核心思路其实还是得根据样例,首先我们先自己分析出来。现根据边地数目来分析。我们其实不难发现四个端点必须得连上边。边数为2.那么只有两条竖线。方案数是一种边数为3,那么就一条竖线还有就是一把叉这里交换位置就是两条了。还有就是平行四边形和一条斜线,也是可以......