题解：CF650B Image Preview

· · 题解

这是青题？？？

注意到照片的方向相当于横着的需要 b+1 秒，竖着的需要 1 秒。

之后不难发现你看的照片一定是一个包含 1 的循环区间，因为你不能跳过没看过的照片。

又会发现，对于任何一个循环区间，包含它的区间看完需要的时间显然大于当前区间。

一个区间最优的走法显然是从 1 开始走到离 1 近的那一端，再折返走到更远的一端。那么按照这个双指针维护即可，复杂度线性。

注意特判答案为 0，以及循环区间长度不能超过 n。 :::success[code]

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ui unsigned int
#define i128 __int128_t
#define u128 __uint128_t
#define i16 short
#define u16 unsigned i16
#define fi first
#define se second
#define pii pair<int,int>
#define lowbit(x) ((x)&(-(x)))
#ifdef int
#define i32 signed
#define u32 unsigned
#define inf (int)(1e18)
#define popc(x) __builtin_popcountll(x)
#define ctz(x) __builtin_ctzll(x)
#define clz(x) __builtin_clzll(x)
#else
#define ll long long
#define ull unsigned ll
#define inf (int)(1e9)
#define infl (int)(1e18)
#define popc(x) __builtin_popcount(x)
#define ctz(x) __builtin_ctz(x)
#define clz(x) __builtin_clz(x)
#define popcl(x) __builtin_popcountll(x)
#define ctzl(x) __builtin_ctzll(x)
#define clzl(x) __builtin_clzll(x)
#define pll pair<ll,ll>
#endif
#define double long double
#define sqrt(x) sqrtl(x)
#define cbrt(x) cbrtl(x)
#define pow(x,y) powl(x,y)
#define sin(x) sinl(x)
#define cos(x) cosl(x)
#define tan(x) tanl(x)
#define push emplace
#define pb emplace_back
#define pf emplace_front
#define ppb pop_back
#define ppf pop_front
const int N=5e5+10,mod=998244353;
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    int n,a,b,t;
    cin>>n>>a>>b>>t;
    string s;
    cin>>s;
    s=' '+s;
    int l=1,r=n+1,tt=(s[1]=='w'?b+1:1),ss=tt;
    while(r>1&&ss<=t) r--,tt+=(s[r]=='w'?b+1:1)+a,ss=tt+min(l-1,n-r+1)*a;
    if(r==n+1)
    {
        cout<<0;
        return 0;
    }
    tt-=(s[r]=='w'?b+1:1)+a,r++,ss=tt+min(l-1,n-r+1)*a;
    int ans=n-r+1+l;
    while(l<n)
    {
        l++,tt+=(s[l]=='w'?b+1:1)+a,ss=tt+min(l-1,n-r+1)*a;
        while(r<=n&&ss>t) tt-=(s[r]=='w'?b+1:1)+a,r++,ss=tt+min(l-1,n-r+1)*a;
        if(ss>t) break;
        ans=max(ans,n-r+1+l);
    }
    cout<<min(ans,n);
    return 0;
}

:::