题解：AT_abc380_c [ABC380C] Move Segment

Storm_Lightning · 2024-11-18 15:15:50 · 题解

题解 AT_abc380_c [ABC380C] Move Segment

题目大意

• 统计序列 S 中，连续 1 的部分有多少个。

• 将第 k 个部分整体向前移，直到第 k 个部分和第 k-1 个部分合并成为一个部分是，输出此时的序列 S。

数组定义

思路

从头至尾遍历一遍 S，定义临时变量 number=0，cnt=0，last=0。

第一部分—处理 连续 1 的部分

• 如果 S[i]=1，就让 number+1；

• 如果 S[i]=0，并且 s[i-1]=1。代表这是一个新的部分，进行 cnt+1 ，此时将第 cnt 个部分的 id 值赋为 last，第 cnt 个部分的 shu 值记为 number，并将 number 清 0。

• 如果 S[i]=0，并且 s[i+1]=1。代表即将有一个新的部分，则需要将 last 赋值为下一个部分的起始坐标。

第二部分—移动 第 k 个部分

• 我们既然已将统计了每个部分的起始坐标，不妨将第 k 个部分的起始坐标 直接给瞬移到 第 k-1 个部分的终点坐标的下一位，就可以解决顺义问题啦！

• 但有个问题，如何去算终点坐标呢？我们在知道第 i 个部分的起始坐标和数量后，利用 start+len-1 的计算公式，就可以轻松求解了。

第三部分—输出序列 S

定义临时变量 now=1 （用于当前要使用第几个区间）。

• 我们利用计算终点坐标的公式可以算出第 i 个区间的终点坐标，然后判断当前坐标是否在这个区间里。如果在输出 1，否则输出 0。

• 如果当前坐标的下一个坐标为下一个区间的起始坐标，则更新 last 的值。

代码部分

本人认为前面已经很详细了，就不再多说了。

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,k;
string s;
int id[1000010];
int shu[1000010];
int cnt;
signed main()
{
    cin>>n>>k;
    cin>>s;
    int number=0,last=0;
    for(int i=0;i<n;i++)
    {
        if(s[i]=='1')
        {
            number++;
        }
        else if(s[i-1]=='1'&&s[i]=='0')
        {
            id[++cnt]=last;
            shu[cnt]=number;
            number=0;
        }
        if(s[i]=='0'&&s[i+1]=='1')
        {
            last=i+1;
        }
    }
    if(number!=0)
    {
        id[++cnt]=last;
        shu[cnt]=number;
        number=0;
    }
    id[k]=id[k-1]+shu[k-1];
    int now=1;
    for(int i=0;i<n;i++)
    {
        if(i>=id[now]&&i<=id[now]+shu[now]-1)
        {
            cout<<1;
        }
        else
        {
            cout<<0;
        }
        if(i+1==id[now+1])
        {
            now++;
        }
    }
    return 0;
}

如果大家觉得不错，留个赞再走吧！