原题链接
考察:贪心
这题不难,但是本蒟蒻是fw.主要是没分析出点的性质,发现了点的个数很少后没啥反应(.)
思路:
注意到点的坐标是倍增增长的,根据起始坐标的范围,最大能运动到(2*1016,2*1016)处.a最小是2,因此最多是60个点.
接下来就没想到了,因为点坐标是倍增增大的,因此1~i的耗费时间<i到i+1的时间.所以我们枚举起点,尽可能往下走.如果时间没走完就再往回走.
关于怎么取点,WA了很多次,结论是x||y>2e16即可break
Code
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 110;
LL cnt,nx[N],ny[N],ax,ay,bx,by,sx,sy,t;
LL get(LL x,LL y,LL dx,LL dy)
{
return abs(dx-x)+abs(dy-y);
}
int solve(int idx)
{
LL cost = get(sx,sy,nx[idx],ny[idx]);
LL now = t;
if(cost>now) return 0;
now-=cost;
int res = 1;
LL x = nx[idx],y=ny[idx];
for(int i=idx-1;i>=0;i--)
{
cost = get(x,y,nx[i],ny[i]);
if(now<cost) break;
res++;
now-=cost;
x = nx[i],y = ny[i];
}
cost = get(x,y,nx[idx],ny[idx]);
if(cost>now) return res;
now-=cost;
x = nx[idx],y = ny[idx];
for(int i=idx+1;i<=cnt;i++)
{
cost = get(x,y,nx[i],ny[i]);
if(now<cost) break;
res++;
now-=cost;
x = nx[i],y = ny[i];
}
return res;
}
int main()
{
scanf("%lld%lld%lld%lld%lld%lld%lld%lld%lld",&nx[0],&ny[0],&ax,&ay,&bx,&by,&sx,&sy,&t);
while(1)
{
LL dx = nx[cnt]*ax+bx;
LL dy = ny[cnt]*ay+by;
if(dx>2e16||dy>2e16) break;
nx[++cnt] = dx;
ny[cnt] = dy;
}
int res =0;
for(int i=0;i<=cnt;i++)
res = max(solve(i),res);
printf("%d\n",res);
return 0;
}