题解：P12935 [NERC 2019] Balls of Buma

__VN · 2025-06-29 19:13:37 · 题解

P12935 [NERC 2019] Balls of Buma

题目传送门 题解代码通过记录

题目大意

规则大意

如果某个颜色相同的球段由于之前的操作变长，并且其长度达到至少 3 ，那么该球段的所有球都会被消除。

目的

插入一个新球使该球段的所有球都被消除，求方案总数。

思路

先压缩字符串。

for(int i=0;i<s.size();i++){        //压缩字符串
    if((s[i]!=s[i-1]&&i)||!num){    //没有上一区块或与上一区块不同色 
        num++;
        if(!m[s[i]]){               //没有出现过此颜色              
            m[s[i]]=++cnt;          //颜色总数++ 
            a[num][1]=cnt;
        }else a[num][1]=m[s[i]];    //否则对应 
        t[m[s[i]]]++;
    }
    a[num][0]++;                    //区块长度++ 
}

由题易得，如果要使所有球都被消除，则有且仅有一个颜色出现过奇数次，且中心区块为这个颜色，此区块即为小球插入的位置。

因为球段必须由于之前的操作变长，所以左右两边颜色对称分布，故有且仅有一个颜色出现过奇数次。

详解见代码。

完整代码

#include<bits/stdc++.h>
using namespace std;
map<char,int> m;            //字符对应颜色 
string s;
int cnt=0;                  //颜色总数 
int num=0;                  //共有区块总数 
int a[300001][2]={};        //区块信息 
int t[300001]={};           //桶,各颜色区块数目 eg:AABAA  A:2,B:1 
bool se(int l,int r){                               //是否能全部消除 
    while(l!=0&&r!=num+1){                          //如果没有到边界 
        if(a[l][1]!=a[r][1]||a[l][0]+a[r][0]<=2){   //不同色(包含不变长),或小于3 
            return 0;
        }
        l--; 
        r++;
    }
    return 1; 
}
int main(){
    cin>>s;
    for(int i=0;i<s.size();i++){        //压缩字符串
        if((s[i]!=s[i-1]&&i)||!num){    //没有上一区块或与上一区块不同色 
            num++;
            if(!m[s[i]]){               //没有出现过此颜色              
                m[s[i]]=++cnt;          //颜色总数++ 
                a[num][1]=cnt;
            }else a[num][1]=m[s[i]];    //否则对应 
            t[m[s[i]]]++;
        }
        a[num][0]++;                    //区块长度++ 
    }
    int f=0;                //出现奇数次的颜色 
    for(int i=1;i<=cnt;i++){
        if(t[i]%2==1){
            if(f){          //如果有两种颜色 
                cout<<0;
                return 0;
            }   
            f=i;            //记录 
        }
    }
    int mid;
    if(num%2==0){
        cout<<0;
        return 0;
    }else mid=num/2+1;
    if(f&&a[mid][1]==f&&a[mid][0]>=2&&se(mid-1,mid+1)) cout<<a[mid][0]+1;   //颜色出现奇数次且能全消 
    else cout<<0;
    return 0;
}