3 条题解

  • 1
    @ 2026-10-26 15:26:33

    O(∑∣S∣)O( \sum |S| ) 做法。

    首先可以看出,无解的情况为正常男生的数量大于 NN,并且这是个充要条件。

    分析什么样的字符串是合法的。直接考虑需要分析奇偶性还有一大堆东西,无法下手,所以我们从最后的排队情况入手。

    对于每个正常男生,他一定会领取男装。并且当他领取男装的时候一定会有女装大佬在领取女装。我们可以先把这一部分放好。

    还有一些情况是两个女装大佬出现在同一时刻。我们考虑把这样的时刻插入到已经放好的部分中。我们记第 ii 个正常男生前面插入了 fif_i 个这样的时刻。

    对于每个正常男生,他必须要等到他前面的所有女装大佬都拿完队服之后才能拿。因此记第 ii 个正常按男生前面排有 cnticnt_i 个女装大佬,那么 ∀i,cnti≤i+2×fi\forall i , cnt_i \le i + 2 \times f_i 。

    因为只有 fif_i 是未知的,所以我们移个项。∀i,2×fi≥cnti−i\forall i , 2 \times f_i \geq cnt_i - i。

    对于女装大佬,我们要求当前被钦定位置的人数小于等于队伍中女装大佬的总人数。记正常男生个数为 MM,有 M+max(2×fi)≤2×N−MM + max( 2 \times f_i ) \le 2 \times N - M。

    根据刚才的结论,max(2×fi)≥max(cnti−i)max( 2 \times f_i ) \geq max( cnt_i - i ),因此得出字符串合法的条件是 max(cnti−i)≤2×N−2×Mmax(cnt_i - i) \le 2 \times N - 2 \times M。

    接下来考虑如何计算答案。

    显然让正常男生尽可能靠前更优。因为 cnti+1−(i+1)≥cnti−i−1cnt_{i+1}-(i+1) \geq cnt_i -i -1,所以可以推出答案为 cnticnt_i 需要减少的最大值,也就是 max(cnti−i)+2×M−2×Nmax(cnt_i -i) + 2 \times M - 2 \times N。

    这样就有 36 pts 了。

    考虑如何快速计算 max(cnti−i)max(cnt_i - i)。

    对于每一种字符串, max(cnti−i)max(cnt_i - i) 最大的 ii 一定在它的最后一段或第一段。所以我们只需要计算一段的答案即可。

    复杂度 O(∑∣S∣)O( \sum |S| )。

    #include<bits/stdc++.h>
    using namespace std;
    #define int long long
    const int inf=1e18;
    int n,m;
    string s;
    signed main(){
    	ios::sync_with_stdio(0);
    	cin.tie(0);
    	cin>>n>>m;
    	int ans=-inf,cnt=0,M=0;
    	while(m--){
    		int k;
    		cin>>s>>k;
    		s=" "+s;
    		int len=s.size()-1;
    		int ncnt=0,nM=0,nans=-inf;
    		for(int i=1;i<=len;i++){
    			if(s[i]=='M'){
    				nM++;
    				nans=max(nans,ncnt-nM);
    			}else{
    				ncnt++;
    			}
    		}
    		if(nM==0){
    			cnt=cnt+ncnt*k;continue;
    		}else{
    			if(ncnt>nM){
    				cnt=cnt+(k-1)*ncnt;
    				M=M+(k-1)*nM;
    				ans=max(ans,cnt-M+nans);
    				cnt+=ncnt;M+=nM;
    			}else{
    				ans=max(ans,cnt-M+nans);
    				cnt=cnt+k*ncnt;
    				M=M+k*nM;
    			}
    		}
    	}
    	if(M>n){
    		cout<<"-1";return 0;
    	}
    	cout<<max(0ll,ans+2*M-2*n)<<"\n";
    	return 0;
    } 
    /*
    */
    
    • 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;
      }
      
      • 0
        @ 2026-10-21 15:55:02

        洛谷 P3615 [JOISC 2016] 如厕计划 / Toilets

        • 1

        信息

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