自动搬运

查看原文

来自洛谷，原作者为

	XL4453 没有水平捏

搬运于2025-08-24 22:03:21，当前版本为作者最后更新于2022-11-25 15:22:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

解题思路：

首先特殊处理比值恒为 $0$ 和不存在比值的情况，也就是全是 $\text{W}$ 或者 $\text{B}$，明显这两种情况下每一个字符分一组就是最优解。

对于其它情况，发现所有段的比值都等于整个串里面的比值，也就是比值固定。在这个前提下，发现如果对于某一个满足比值区间，其子区间同样满足这个比值，将这个大区间拆成这个子区间和其补集同样满足条件，而且划分出的区间还多了一个。由此得出结论，每一次从边缘贪心地选取出最短可以满足条件的区间一定是最优的。

具体判断时可以计算出当前情况下满足条件需要的数量，检验这个数量是否可以被取到即可。总复杂度 $O(n)$。

代码：

#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int MAXN=100005;
int T,n,cnt1,cnt2,num[MAXN],col[MAXN],ans,c1,c2,t;
char c;
int gcd(int a,int b){
	if(b==0)return a;
	return gcd(b,a%b);
}
void init(){
	cnt1=cnt2=ans=c1=c2=t=0;
}
signed main(){
	scanf("%lld",&T);
	while(T--){
		init();
		scanf("%lld",&n);
		for(int i=1;i<=n;i++){
			scanf("%lld",&num[i]);
			for(c=getchar();c!='B'&&c!='W';c=getchar());
			if(c=='B')col[i]=1,cnt1+=num[i];
			else col[i]=2,cnt2+=num[i];
		}
		if(cnt1==0||cnt2==0){
			printf("%lld\n",cnt1+cnt2);
			continue;
		}
		int GCD=gcd(cnt1,cnt2);
		cnt1=cnt1/GCD;cnt2=cnt2/GCD;
		for(int i=1;i<=n;i++){
			if(col[i]==1){//当前为黑 
				//(c1+k)/c2==cnt1/cnt2
				//k==cnt1*c2/cnt2-c1
				if(c2%cnt2!=0){
					c1+=num[i];
					continue;
				}
				t=(cnt1*(c2/cnt2))-c1;
				if(c2&&t>=0&&t<=num[i])ans++,c1=num[i]-t,c2=0;
				else c1+=num[i];
			}
			else{
				if(c1%cnt1!=0){
					c2+=num[i];
					continue;
				}
				t=(cnt2*(c1/cnt1))-c2;
				if(c1&&t>=0&&t<=num[i])ans++,c2=num[i]-t,c1=0;
				else c2+=num[i];				
			}
		}
		printf("%lld\n",ans);
	}
	return 0;
}