首页 > 其他分享 >Codeforces Round #661 (Div. 3) D. Binary String To Subsequences(贪心/思维)

Codeforces Round #661 (Div. 3) D. Binary String To Subsequences(贪心/思维)

时间:2023-01-25 23:33:47浏览次数:78  
标签:Binary typedef String LL cin 661 Codeforces 序列

https://codeforces.com/contest/1399/problem/D

题目大意:

长度为n的字符串s只由0和1组成。 

我们要把s分成最小数量的子序列,使得每一个子序列看起来像“010101 ...”或者“101010……”(即子序列不应包含两个相邻的0或1)。

先输出总共划分成了多少个子序列,再分别输出所属的子序列的编号。
input 
4
4
0011
6
111111
5
10101
8
01010000
output 
2
1 2 2 1 
6
1 2 3 4 5 6 
1
1 1 1 1 1 
4
1 1 1 1 1 2 3 4 

参考了这位佬的写法,强推:
https://www.cnblogs.com/pixel-Teee/p/13444081.html

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<LL,LL> PII;
const LL MAXN=1e18,INF=1e9;
const LL N=5e5+10,M=4002;
#define endl '\n'
LL ans[N];
int main()
{
    //cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    LL T=1;
    cin>>T;
    while(T--)
    {
        LL n;
        cin>>n;
        string s;
        cin>>s;
        s=" "+s;
        queue<LL> q0,q1;
        LL idx=0;
        for(int i=1;i<=n;i++)
        {
            if(s[i]=='0')
            {
                if(q1.size()!=0)
                {
                    LL t=q1.front();
                    //队列是先进先出,用了立即改变0 1状态
                    q1.pop();
                    ans[i]=ans[t];
                    q0.push(i);
                }
                else
                {
                    ans[i]=++idx;
                    q0.push(i);
                }
            }
            else
            {
                if(q0.size()!=0)
                {
                    LL t=q0.front();
                    q0.pop();
                    ans[i]=ans[t];
                    q1.push(i);
                }
                else
                {
                    ans[i]=++idx;
                    q1.push(i);
                }
            }
        }
        cout<<idx<<endl;
        for(int i=1;i<=n;i++)
            cout<<ans[i]<<" ";
        cout<<endl;
    }
    return 0;
}

标签:Binary,typedef,String,LL,cin,661,Codeforces,序列
From: https://www.cnblogs.com/Vivian-0918/p/17067446.html

相关文章

  • Educational Codeforces Round 142 (Rated for Div. 2) A-D
    比赛链接A题解知识点:贪心。代码#include<bits/stdc++.h>usingnamespacestd;usingll=longlong;boolsolve(){intn;cin>>n;intcnt=0;......
  • Codeforces Round #845----C
    题目:Problem-C-Codeforces题解:使用双指针。枚举l,寻找最小的r使条件成立。代码:#include<bits/stdc++.h>usingnamespacestd;voidsolve(){ intn,m; cin>......
  • CF1792 D. Fixed Prefix Permutations : Educational Codeforces Round 142 (Rated fo
    给出n个长度为m的排列(a1,a2,a3,...,an)定义一个操作 r=ai•aj:r[k]=a[j][a[i][k]]定义一个排列(p1,p2,...,pn)的beauty为最大的k,使得p[1]=1,p[2]=2,..,p[k......
  • 学习笔记——NoSQL数据库;Redis概述;redis中常用的数据类型(key、string)
    2023-01-24一、NoSQL数据库1、NoSQL数据库的简介NoSQL(NoSQL=NotOnlySQL),即“不仅仅是SQL”,泛指非关系型的数据库。NosQL不依赖业务逻辑方式存储,而以简单的key-value模......
  • Codeforces Round #822 (Div. 2) D
    链接:https://codeforces.com/problemset/problem/1734/E题意,给定n,b[1~n],求一个nn矩阵,满足a[i][i]=b[i],且对于r1<r2,c1<c2,a[r1][c1]+a[r2][c2]!=a[r1][c2]+a[r2][c1](m......
  • CodeForces-907#B 题解
    正文设数组\(c_{x,y,i,j}\)代表\((x,y)\)位置的大格子中\((i,j)\)位置的小格子。很显然,输入中字符的输入顺序是要调整的,实际的顺序是\(x,i,y,j\)。对于输入的\(......
  • Codeforces Round #845 (Div. 2) and ByteRace 2023 A-D
    CodeforcesRound#845(Div.2)andByteRace2023A-DA.EverybodyLikesGoodArrays!题意:对给定数组进行操作:删除相邻两项,替换为两项的乘积,使得该数组奇偶相间。......
  • CString如何转COleDateTime
    可以用类COleDateTime  .ParseDateTime或者是用ColeVariant例子如下所示CString aa="1978-01-0108:08:08";  COleVariant v(aa);  v.ChangeType(VT_D......
  • abc214 F - Substrings
    题意:求给定字符串\(s\)的不同非空子序列个数要求被选入的位置两两不相邻\(n\le2e5\)思路:如果没有不相邻的要求怎么做?\(f_i\)表示考虑\(s[1..i]\),并且选\(i\)......
  • Codeforces Round #845 (Div. 2) and ByteRace 2023
    《B.Emordnilap》数学,思维   题意:给定一个由1~n组成序列,然后将这序列复制,反转,再放到原序列的末尾,得到新的序列(设为s)问s的逆序对个数 当时我写......