专栏文章

题解：P12935 [NERC 2019] Balls of Buma

ccyntmeay
P12935题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5mf6k
此快照首次捕获于
2025/12/01 20:57
3 个月前
此快照最后确认于
2025/12/01 20:57
3 个月前
查看原文

题目大意

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

思路

理解题意后可以想到将字符串压缩成一块一块的形式，在满足题目条件的消除方案的情况下，其满足的条件一共只有三个。 第一个是左右两个部分的颜色必须对称；第二个是在满足第一个条件后，两个部分的字母数量之和大于等于 22。第三个是中间部分的字母数量至少为 22。
最后答案就是最中间的部分的字母数量加 11。

关键代码

CPP
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--;//右指针向左移 
	}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...