CF382B

_edge_ · 2022-07-01 06:31:04 · 题解

没人发题解？

感觉我的做法好麻烦，用官方题解来推推柿子就很快能解决了。

先来说一下我的做法吧。

首先，对于 c\le a-3000 的情况，我们可以直接进行暴力处理，复杂度大概也是可以接受的。

然后就是比较大的情况，其实我们可以发现这个东西肯定是有一个循环节的，并且这个循环节是在 1000 的范围之内，因为总共就 1000 个数。

我一开始以为这个 b 就是这个循环节的头结果越写越不对，总的来说，就是 b 会先到一段不循环的，然后再到循环节，类似于基环树一样。

为了避免在没到循环的时候就结束，我加了上面的特判。

对于有循环节的，我们可以记录循环节内 c 减少的次数以及经过的秒数。

然后这个东西我们可以直接对他二分，形式化就是 c-ans \times sum >a 其中 ans 要最大，sum 为循环节内 c 减少的次数。

然后对于零散开的，即循环节只有一段的，范围不超过 1000 可以直接暴力找。

#include <iostream>
#include <cstdio>
#include <cstring>
#define int long long 
using namespace std;
const int INF=1e3+5;
int a,b,w,x,c,f[INF],sum,sum1,ans,f1[INF],iu;
void DFS(int y) {
//  cout<<y<<" endl\n";
    if (f[y]) {ans+=f[y];c-=f1[y];sum-=f[y];sum1-=f1[y];iu=y;return ;}
    f[y]=sum;f1[y]=sum1;
    if (y>=x) {sum1++;sum++;DFS(y-x);}
    else sum++,DFS(w-(x-y));
    return ;
}
void DFS1(int y) {
//  cout<<y<<" "<<c<<" "<<a<<" endl\n";
    if (c<=a) return ;
    ans++;
    if (y>=x) {c--;DFS1(y-x);}
    else DFS1(w-(x-y));
    return ;
}
signed main()
{
    ios::sync_with_stdio(false);
    cin>>a>>b>>w>>x>>c;
    if (c-a<=3000) {DFS1(b);cout<<ans<<"\n";return 0;}
    DFS(b);
//  cout<<sum1<<" "<<sum<<" endl\n";
//  while (c-sum1>a) c-=11111sum1,ans+=sum;
    int l=0,r=1e15,ans1=0;
    while (l<=r) {
        int Mid=(l+r)>>1;
        if (c-Mid*sum1>a) l=(ans1=Mid)+1;
        else r=Mid-1;
//      cout<<l<<" "<<r<<" "<<c-Mid*sum1<<" "<<ans1<<" "<<" pp\n";
    }
//  cout<<ans1<<" "<<sum1<<" "<<ans1*sum<<" "<<" oo\n";
    c-=sum1*ans1;ans+=ans1*sum;
//  cout<<c<<" "<<a<<" kkk\n";
    memset(f,0,sizeof f);
    DFS1(iu);cout<<ans<<"\n";
    return 0;
}