作为DIV2的D题来讲,这个题目不算难。 题目大意:再规定的时间内寻找宝藏,第i个宝藏的位置为a*x(i-1)+b,a*y(i-1)+b。然后给出初始位置xs,ys和时间t让求再时间t内能够寻找到多少宝藏。
题解:
两相邻的宝藏的坐标差一定是最小的。所以答案一定是连续的一组坐标。注意数据范围x的范围是2e16,a最小是2,所以最多也就60多个宝藏,直接暴力起点终点就行。
#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll N=1E3+7; ll limit=2e16; struct stu{ ll x,y; }arr[N]; ll dis(ll x,ll y){ return (ll)abs(arr[x].x-arr[y].x)+(ll)abs(arr[x].y-arr[y].y); } int main() { ll x0,y0,a1,a2,b1,b2; cin>>x0>>y0>>a1>>a2>>b1>>b2; ll xs,ys,t; cin>>xs>>ys>>t; arr[0].x=x0; arr[0].y=y0; int pos=1; ll x=x0,y=y0; for(ll i=1;i<=100;i++){ x=x*a1+b1; y=y*a2+b2; if(x>=limit||y>=limit) break; arr[pos].x=x; arr[pos++].y=y; } ll ans=0; for(ll i=0;i<pos;i++){ for(ll j=0;j<pos;j++){ if(dis(i,j)+(ll)abs(xs-arr[i].x)+(ll)abs(ys-arr[i].y)<=t){ if(j>i) ans=max(ans,j-i+1); else ans=max(ans,i-j+1); } } } cout<<ans<<endl; return 0; }