首页 > 代码库 > 汕头市队赛 C KMP codeforces B. Image Preview
汕头市队赛 C KMP codeforces B. Image Preview
汕头市队赛题目传送门
codeforces题目传送门
这道题我的做法是 尝试先往左走然后往右走 或者先往右走然后往左走 然后注意一下枚举顺序就okay啦
#include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; const int M=1e6+7; LL read(){ LL ans=0,f=1,c=getchar(); while(c<‘0‘||c>‘9‘){if(c==‘-‘) f=-1; c=getchar();} while(c>=‘0‘&&c<=‘9‘){ans=ans*10+(c-‘0‘); c=getchar();} return ans*f; } int n,a,b,T; LL w[M],ans; char s[M]; LL pd1(int l,int r){ LL sum=w[r]-w[l-1]; int now=(r-l)+(n+1-l); return sum+(LL)now*a; } LL pd2(int l,int r){ LL sum=w[r]-w[l-1]; int now=(r-l)+(r-n-1); return sum+(LL)now*a; } int main() { n=read(); a=read(); b=read(); T=read(); scanf("%s",s+1); for(int i=n+1;i<=2*n;i++) s[i]=s[i-n]; for(int i=1;i<=2*n;i++) w[i]=(s[i]==‘w‘?(b+1):1)+w[i-1]; // for(int i=1;i<=2*n;i++) printf("%lld ",w[i]); printf("\n"); int l=n+1; for(int r=2*n;r>=n+1;r--){ while(l>r-n+1&&pd1(l-1,r)<=T) l--; if(pd1(l,r)<=T) ans=max(ans,(LL)(r-l+1)); } //printf("%lld\n",ans); int r=n+1; for(int l=2;l<=n+1;l++){ while(r<l+n-1&&pd2(l,r+1)<=T) r++; if(pd2(l,r)<=T) ans=max(ans,(LL)(r-l+1)); } // ans=min(ans,(LL)n); printf("%lld\n",ans); return 0; }
汕头市队赛 C KMP codeforces B. Image Preview
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。