3 条题解
-
1
做法。
首先可以看出,无解的情况为正常男生的数量大于 ,并且这是个充要条件。
分析什么样的字符串是合法的。直接考虑需要分析奇偶性还有一大堆东西,无法下手,所以我们从最后的排队情况入手。
对于每个正常男生,他一定会领取男装。并且当他领取男装的时候一定会有女装大佬在领取女装。我们可以先把这一部分放好。
还有一些情况是两个女装大佬出现在同一时刻。我们考虑把这样的时刻插入到已经放好的部分中。我们记第 个正常男生前面插入了 个这样的时刻。
对于每个正常男生,他必须要等到他前面的所有女装大佬都拿完队服之后才能拿。因此记第 个正常按男生前面排有 个女装大佬,那么 。
因为只有 是未知的,所以我们移个项。。
对于女装大佬,我们要求当前被钦定位置的人数小于等于队伍中女装大佬的总人数。记正常男生个数为 ,有 。
根据刚才的结论,,因此得出字符串合法的条件是 。
接下来考虑如何计算答案。
显然让正常男生尽可能靠前更优。因为 ,所以可以推出答案为 需要减少的最大值,也就是 。
这样就有 36 pts 了。
考虑如何快速计算 。
对于每一种字符串, 最大的 一定在它的最后一段或第一段。所以我们只需要计算一段的答案即可。
复杂度 。
#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
- 上传者