NOIP模拟测试8「寿司」 | Hexo

归档于 2019-07-25 21:45

考试时打的类似$n^2$暴力，然后炸了只有10分

后来验证我的算法伪了。

题解

---

显然你有一种解法，假设你要在一个B点断开将R分别移向最左 最右，这样只用分别计算B点右面蓝色数量左面蓝色数量就得到了一个ans

这个题有一个很不显然的结论，假设你要将R移向两边时，序列唯一确定时，设pos=(蓝色数量+1)/2，在pos点将R移向左面，右面花费最小（单调性）

因为这个序列是循环的所以我们只要枚举B点断开的位置就可以$n^2$求出最小的ans值

$n^2$显然过不了1000000

现在我们思考$n^2$问题在哪，首先你每次重新计算一次ans额外花费了时间，然后每次都枚举断点又花费了时间

但实际上我们每次循环到下一个这个序列实际上变化很少，只是前面那个字母删去，后面再加一个字母

实际对ans改变也很少

类似于莫队，对于ans+ - 我们可以得到另一个ans

那么我们可以计算出他的改变

首先我们可以得出每次循环到下一B，假设我们目前断点不变，那么所有左边R对ans造成贡献都会减1，所有右边R对ans造成贡献都会加1

然后我们思考下一个断点，假设当前断点显然就是下一个B

然后我们断点移动过程中我们发现有一些R从右面移动到了左面，那么他要移动贡献也从右面blue数量改成了右面贡献，减去左面贡献加上左面的贡献即可

代码

---

#include<bits/stdc++.h>
#define ll long long
#define A 2100000
using namespace std;
ll t,len,n,ans,pos,zo,p;
ll lb[A],rb[A],lr[A],rr[A];
char c[A];
int main()
{
//    freopen("mkd.txt","r",stdin);
//    freopen("wa.txt","w",stdout);
    scanf("%lld",&t);
    while(t--){
        ans=0;
        zo=ans;
        lb[0]=rb[0]=lr[0]=rr[0]=0;
        scanf("%s",c+1);
        len=strlen(c+1);
        n=len;pos=-1;
        for(ll i=1;i<=len;i++){
            c[n+i]=c[i];
        }
        len*=2;
        rr[len+1]=rb[len+1]=0;
        for(ll i=1;i<=len;i++){
            lb[i]=lb[i-1],lr[i]=lr[i-1];
            if(c[i]=='B')lb[i]++;
            else lr[i]++;
        }
        for(ll i=len;i>=1;i--){
            rr[i]=rr[i+1],rb[i]=rb[i+1];
            if(c[i]=='B') rb[i]++;
            else rr[i]++;
        }
        pos=(lb[n]+1)/2;
//        printf("pos=%lld\n",pos);
        for(ll i=1;i<=n;i++){
            if(lb[i]==pos){
                p=i;
                for(ll j=n;j>i;j--){
                    if(c[j]=='R')
                    ans+=rb[j]-rb[n+1];
//                    printf("rr=%lld rr[n]=%lld\n",rr[j],rr[n+1]);
                }
                break;
            }
            else if(c[i]=='R')ans+=lb[i];
        }
//        printf("ans=%lld\n",ans);
        zo=ans;
        ll head=1,tail=n;
        while(head<=n){
            if(c[head]=='B'){    
                ans-=lr[p]-lr[head-1];//如果当前为B将B向后移动那么左边所有R代价-1
                ans+=rr[p]-rr[tail+1];//如果当前为B将B向后移动那么右边所有R代价+1
                while(c[++p]!='B'){//当前指针应当指向下一个B
                    ans+=lb[p]-lb[head];//如果R由左变为了右，那么代价从左边变成右边
                    ans-=rb[p]-rb[tail+2];
                }
            }
            head++,tail++;
            zo=min(zo,ans);
        }
        cout<<zo<<endl;
    }
}

View Code