3 条题解
-
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; }
信息
- ID
- 932
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 8
- 标签
- (无)
- 递交数
- 37
- 已通过
- 6
- 上传者