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;
    } 
    /*
    */
    

    信息

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