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; } /* */ -
1
SOLUTION
最猎奇的做法,没有之一。
对于前 分,显然直接二分,只需要想怎么
check。先考虑一个判定:令 ,,当且仅当一个序列的所有后缀和都大于等于 时才可以达到目标。
对于同一种,可以认为他们的相对位置永远不变。
当现在的最大 时,考虑把每个 向右移动 位,如果目标位置不存在或被占用就堆在最后面,这样一定是最优的,然后判定即可,容易做到 ,即总复杂度 。
考虑对所有情况沿用这个做法。
二分 代表最大 , 代表第一个可以成功移动的位置。通过前缀和容易做到 。
对于 之后的,只要计算出里面有多少个 。对于之前的,相对位置不变,只要求出最小后缀和。
对于 个重复的串,容易发现他的后缀最小值一定出现在头一个或者最后一个串。
这样就能算了,是 的。
总复杂度 。
我都不知道我是怎么 分钟写完且一遍调对的....
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; }
- 1
信息
- ID
- 932
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 37
- 已通过
- 6
- 上传者