Codeforces Round #614 (Div. 2) D

变色失败只加8分距离变色只差5分 B题没想到那么简单，结论秒猜，不敢交，傻傻验证5分钟。

C题也想了码了好一会儿，我动态维护set做的。

1小时3题，整体难度好像没以前那么大了？(虽然也不强，但比以前好不少了......

难道是我变强了？(逃

补了个D，真是傻逼题(指我sb

D.Aroma's Search

倍数至少是2，所以至多60几次肯定到上限了。

然后这里处理有个细节，之前我一直是乘的来计算这些坐标的，当他>2e16结束，实际上我总感觉有可能存在溢出这样的bug。虽然这里似乎没有？

看了标程和rk1的代码，学到了这里处理用除法反过来判断有无达到上限，就不会有溢出的问题了。值得学一下。

主要是对于曼哈顿距离的理解还是太浅了，亏我还一个一个的走，思维真是抱歉。

从一个点连续经过一系列点再到另一个点的距离其实就是两端点的曼哈顿距离，直接通过平移就可以看出来。

手稿上图都画了都没看出来，zdsb。实际上我想的假算法还在一个点一个点的走 (ε=ε=ε=┏(゜ロ゜;)┛

然后随便怎么做了。这里n很小，所以复杂度很宽，怎么做都行。

三重循环枚举最先到的点，左端点，右端点。很容易理解。

然后因为最先到的点以后，实际上也要继续往左端点或者右端点走，所以标程直接二重循环枚举左右端点，取起点到二者中更小的加上必经之路的左右之间的全部距离。

#include <bits/stdc++.h>

#ifndef ONLINE_JUDGE

#define debug(x) cout << #x << ": " << x << endl

#else

#define debug(x)

#endif

using namespace std;

typedef long long ll;

const int MAXN=2e5+7;

const int INF=0x3f3f3f3f;

const int MOD=1e9+7;

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    ll x0,y0,ax,ay,bx,by;

    cin>>x0>>y0>>ax>>ay>>bx>>by;

    ll xs,ys,t;

    cin>>xs>>ys>>t;

    vector<ll>x(1,x0),y(1,y0);

    ll lim=(1ll<<62)-1;

    while( (lim-bx)/ax>=x.back() && (lim-by)/ay>=y.back())

    {

        x.push_back(x.back()*ax+bx);

        y.push_back(y.back()*ay+by);

    }

    int cnt=x.size();

    int ans=0;

    for(int i=0;i<cnt;++i)

    {

        for(int j=i;j<cnt;++j)

        {

            ll len=x[j]-x[i]+y[j]-y[i];

            ll distl=abs(xs-x[i])+abs(ys-y[i]);

            ll distr=abs(xs-x[j])+abs(ys-y[j]);

            if(len<=t-distl || len<=t-distr) ans=max(ans,j-i+1);

        }

    }

    cout<<ans<<endl;

    return 0;

}

变色？

下次一定？

巴特西

Codeforces Round #614 (Div. 2) D

最新文章

热门文章