题解：P12935 [NERC 2019] Balls of Buma

cyntmeay · 2025-11-18 17:56:37 · 题解

题目大意

题目给定一个字符串，现在可以选择在任意一个位置插入一个字符。如果插入这个字符后某个相同颜色球的连续段因为之前某个操作而变长，且长度达到了 3，那么该连续段的所有球就会被删除。

要求选择新球颜色和插入位置使得所有球最终被消除的方案总数。

思路

理解题意后可以想到将字符串压缩成一块一块的形式，在满足题目条件的消除方案的情况下，其满足的条件一共只有三个。

第一个是左右两个部分的颜色必须对称；第二个是在满足第一个条件后，两个部分的字母数量之和大于等于 2。第三个是中间部分的字母数量至少为 2。

最后答案就是最中间的部分的字母数量加 1。

关键代码

while(1){
        if(l==r){//指针重合结束计算 
            break;
        }
        if(a[l].x!=a[r].x||a[l].s+a[r].s<3){//不合法没有情况，提前返回 
            flag=true;
            break;
        }
        if(abs(r-l)==1){//同上 
            flag=true;
            break; 
        }
        l++;//左指针向右移 
        r--;//右指针向左移 
    }