3 条题解

  • 1
    @ 2026-10-24 10:59:56

    SOLUTION

    最猎奇的做法,没有之一。

    对于前 3636 分,显然直接二分,只需要想怎么 check。

    先考虑一个判定:令 F=1F = 1,M=−1M = -1,当且仅当一个序列的所有后缀和都大于等于 −1-1 时才可以达到目标。

    对于同一种,可以认为他们的相对位置永远不变。

    当现在的最大 Dark=midDark = mid 时,考虑把每个 FF 向右移动 midmid 位,如果目标位置不存在或被占用就堆在最后面,这样一定是最优的,然后判定即可,容易做到 O(N)O(N),即总复杂度 O(Nlog⁡N)O(N \log N)。

    考虑对所有情况沿用这个做法。

    二分 mid1mid1 代表最大 DarkDark,mid2mid2 代表第一个可以成功移动的位置。通过前缀和容易做到 O(log⁡3N)O(\log ^3 N)。

    对于 mid2mid2 之后的,只要计算出里面有多少个 FF。对于之前的,相对位置不变,只要求出最小后缀和。

    对于 kk 个重复的串,容易发现他的后缀最小值一定出现在头一个或者最后一个串。

    这样就能算了,是 O(∑len)O(\sum len) 的。

    总复杂度 O(log⁡3N+log⁡N∑len)O(\log ^3 N +\log N \sum len)。

    我都不知道我是怎么 1515 分钟写完且一遍调对的....

    CODE

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    #define fi first
    #define se second
    int T,n,m;
    string t[101000];
    int s[101000],len[101000];
    int cf[101000];
    vector<int> ccf[101000];
    int sl[101000];
    int sf[101000];
    int st[101000];
    int get_right_F(int x){
        int L=1,R=m;
        while(L<R){
            int mid=(L+R)>>1;
            if(sl[mid]<x) L=mid+1;
            else R=mid;
        }
        int ix=L,jx=(x-sl[L-1]-1)/len[L],kx=(x-sl[L-1]-1)%len[L]+1;
        // int ix=L,xx=x-sl[L-1];
        int sum=sf[ix-1]+cf[ix]*jx+ccf[ix][kx];
        // cout<<x<<' '<<ix<<' '<<jx<<' '<<kx<<' '<<sf[m]-sum<<" FFFFFFFF\n";
        return sf[m]-sum;
    }
    int check(int x){
        int L=1,R=n*2;
        while(L<R){
            int mid=(L+R+1)>>1;
            if(get_right_F(mid)+mid+x<=n*2) L=mid;
            else R=mid-1;
            // cout<<L<<' '<<R<<' '<<mid<<"\n";
        }
        int l=1,r=L;
        while(l<r){
            int mid=(l+r)>>1;
            if(get_right_F(mid)==get_right_F(L)) r=mid;
            else l=mid+1;
        }
        // cout<<x<<' '<<L<<' '<<l<<' ';
        if(l==0) return 1;
        int ll=1,rr=m;
        while(ll<rr){
            int mid=(ll+rr)>>1;
            if(sl[mid]<l) ll=mid+1;
            else rr=mid;
        }
        int ix=ll,jx=(l-sl[ll-1]-1)/len[ll],kx=(l-sl[ll-1]-1)%len[ll]+1;
        // cout<<ix<<' '<<jx<<' '<<kx<<'\n';
        int rt1=get_right_F(l);
        int dl=rt1-(n*2-l-x-rt1);
        // cout<<rt1<<' '<<dl<<'\n';
        if(dl<-1) return 0;
        for(int i=kx;i>=1;i--){
            dl=dl+(t[ix][i]=='F'?1:-1);
            if(dl<-1) return 0;
        }
        if(jx){
            dl+=st[ix]*(jx-1);
            for(int i=len[ix];i>=1;i--){
                dl=dl+(t[ix][i]=='F'?1:-1);
                if(dl<-1) return 0;
            }
        }
        for(int i=ix-1;i>=1;i--){
            for(int j=len[i];j>=1;j--){
                dl=dl+(t[i][j]=='F'?1:-1);
                if(dl<-1) return 0;
            }
            if(s[i]>1){
                dl+=st[i]*(s[i]-2);
                for(int j=len[i];j>=1;j--){
                    dl=dl+(t[i][j]=='F'?1:-1);
                    if(dl<-1) return 0;
                }
            }
        }
        return 1;
    }
    signed main(){
        ios::sync_with_stdio(0);
        cin.tie(0),cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=m;i++){
            cin>>t[i]>>s[i];
            len[i]=t[i].size(),t[i]=' '+t[i];
            ccf[i].push_back(0);
            for(int j=1;j<=len[i];j++){
                cf[i]+=(t[i][j]=='F');
                st[i]+=(t[i][j]=='F'?1:-1);
                ccf[i].push_back(cf[i]);
                // cout<<ccf[i][j]<<' ';
            }
            // cout<<'\n';
            sf[i]=sf[i-1]+cf[i]*s[i];
            sl[i]=sl[i-1]+len[i]*s[i];
            // cout<<sf[i]<<' '<<sl[i]<<' '<<len[i]<<' '<<cf[i]<<' '<<st[i]<<"----\n";
        }
        if(sf[m]<n){
            cout<<"-1\n";
            return 0;
        }
        int L=0,R=n;
        while(L<R){
            int mid=(L+R)>>1;
            if(check(mid)) R=mid;
            else L=mid+1;
        }
        cout<<L<<'\n';
        return 0;
    }
    

    信息

    ID
    932
    时间
    1000ms
    内存
    256MiB
    难度
    8
    标签
    (无)
    递交数
    37
    已通过
    6
    上传者