[CF909D] Colorful Points - 链表,STL

Description

给定一个串，每轮进行如下操作：如果一个字符的相邻字符中存在与它不同的，则这个字符被选中，选好所有字符后将这些字符同时删除，该轮结束。问操作多少次后无法再删除任何点。

Solution

将相同的连续段合并成一个结点，用链表维护

每次遍历所有节点，头尾值 -1，中间值 -2，如果某个节点值 \(\le 0\) 了就删除它

（对 stl::list 还是不熟悉）

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

#define int long long
const int N = 1000005;

struct Node
{
    char c;
    int x;
};

list<Node> l;
string s;
int n;

signed main()
{
    ios::sync_with_stdio(false);

    cin>>s;
    int t_cnt=0;
    n=s.length();
    for(int i=0;i<n;i++)
    {
        ++t_cnt;
        if(i==n-1 || s[i]!=s[i+1])
        {
            l.push_back({s[i],t_cnt});
            t_cnt=0;
        }
    }

    int flag=1,last=0,ans=0;
    while(l.size()>1)
    {
        ++ans;
        for(auto it=l.begin();it!=l.end();it++)
        {
            it->x-=2;
        }
        l.begin()->x++;
        l.rbegin()->x++;
        for(auto it=l.begin();it!=l.end();it++)
        {
            if(it->x<=0) it=l.erase(it), it--;
        }
        for(auto it=l.begin();it!=l.end();it++)
        {
            auto t_it=it;
            t_it++;
            if(t_it==l.end()) break;
            while(t_it->c==it->c)
            {
                it->x+=t_it->x;
                t_it=l.erase(t_it);
                if(t_it==l.end()) break;
            }
        }
        /*for(auto i:l) cout<<i.c<<"*"<<i.x<<" ";
        cout<<endl;*/
    }
    cout<<ans<<endl;
}

[CF909D] Colorful Points - 链表,STL

原文：https://www.cnblogs.com/mollnn/p/13615411.html