Aroma's Seatch
题意简述
题目链接。
一个二维平面内有无限个点，从 \(0\) 开始编号，编号为 \(0\) 的点的坐标为 \((x_{0} , y_{0})\)。对于一个编号为 \(i(i>0)\) 的点，它的坐标为 \((a_{x} \cdot x_{i-1}+b_{x},a_y \cdot y_{i-1}+b_{y})\)。Aroma 最开始在点 \((x_s,y_s)\) 处，她每秒钟可以向上、下、左、右移动一个单位长度，求 \(t\) 秒内她最多能经过几个点（重复经过只算一次）。
题目分析
观察题目，我们能发现几个性质：
-
点与点之间的距离随着编号的增加而增加，即点会变得越来越稀疏。
-
对于一个编号为 \(i(i>0)\) 的点，从第 \(0\) 个点出发走到第 \(i\) 个点所用的时间一定小于从第 \(i\) 个点出发走到第 \(i+1\) 个点的时间。
性质 \(1\) 比较显然，下面我们来证明性质 \(2\)：
观察点与点之间的关系以及数据范围我们可以发现，当 \(a_{x}=2,b_{x}=0\) 时，点的分布是最密集的。这里我们以 \(x\) 坐标举例（以下，\(Xdist(A,B)\) 表示点 \(A\) 与点 \(B\) 之间在 \(x\) 坐标上的距离）。
\[Xdist(P_{i},P{i+1})=(a_{x} \cdot x_{i}+b_{x})-x_i=2 \cdot x_{i}-x_{i}=x_{i} \]而
\[Xdist(P_0,P_i)=x_i-x_0 \]因为 \(x_0 \geq 1\)，所以 \(Xdist(P_i，P_{i+1}) > Xdist(p_i,0)\)，在 \(y\) 坐标上也是一样。
于是我们可以想出一个贪心策略，枚举点 \(P_i\) 从起始点开始走到 \(P_i\)，然后向靠近第 \(0\) 个点的方向走，如果已经走到了第 \(0\) 个点但是时间仍有剩余就原路返回向远离的 \(0\) 个点的方向走。
下面我们来证明贪心策略是正确的：
当我们从 \(p_i\) 开始向远离第 \(0\) 个点的方向走时，有
\[dist(P_i,P_{i+1})+dist(P_{i+1},p_{i+2})>2\cdot dist(0,p_i) \]这意味着，如果向远离第 \(0\) 个点的方向走，经过了两个点时，如果向靠近第 \(0\) 个点的方向走就可以走一个来回，并经过了 \(i\) 个点。
Code
#include<bits/stdc++.h>
#define int long long
#define y1 yy
using namespace std;
int ax,ay,bx,by,xs,ys,t,tot,ans;
struct node{
int x,y;
}point[100005];
inline int dis(int x1,int y1,int x2,int y2){
return llabs(x1-x2)+llabs(y1-y2);
}
signed main(){
cin>>point[0].x>>point[0].y>>ax>>ay>>bx>>by>>xs>>ys>>t;
while(!(point[tot].x>xs && point[tot].y>ys && dis(xs,ys,point[tot].x,point[tot].y)>t)){
point[++tot].x=point[tot-1].x*ax+bx;
point[tot].y=point[tot-1].y*ay+by;
}
for(int i=0;i<=tot;i++){
int sum=0,temp=t;
if(dis(point[i].x,point[i].y,xs,ys)>temp) continue;
else{
temp-=dis(point[i].x,point[i].y,xs,ys);
sum++;
}
for(int j=i;j>0;j--){
if(dis(point[j].x,point[j].y,point[j-1].x,point[j-1].y)<=temp){
temp-=dis(point[j].x,point[j].y,point[j-1].x,point[j-1].y);
sum++;
}
else{
break;
}
}
for(int j=1;j<=tot;j++){
if(dis(point[j].x,point[j].y,point[j-1].x,point[j-1].y)<=temp){
temp-=dis(point[j].x,point[j].y,point[j-1].x,point[j-1].y);
if(j>i) sum++;
}
else break;
}
ans=max(ans,sum);
}
cout<<ans;
return 0;
}