P4763 [CERC2014]Bricks 题解

XL4453 · 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;
}