題目鏈接：點擊查看

題目大意：給出一個無限大小的二維平面坐標系，現在給出一系列數據點，給出的形式是給出(x[0],y[0])，再規定可以使用遞推式x[i]=ax*x[i-1]+bx，y[i]=ay*y[i-1]+by，現在問，若給出起點為(sx,sy)，可以進行上下左右的移動，每次移動消耗一次步數，問在步數不超過 k 次的情況下，最多能經過多少個數據點，注意一個數據點經過多次也只算一次

題目分析：這個題目有一個很關鍵的細節，就是ax和ay大于等于2，再加上步數小于等于1e16，在這兩個條件的約束下，可以做出貢獻的點數最多是小于64個的，因為2^64>1e18，這樣一來我們就可以預處理出這60多個點，然后暴力，兩層for循環確定起點和終點，每次走相鄰兩個點時的距離為其曼哈頓距離時可以保證最優，這樣實時更新最大值就好了

有個比較麻煩的細節就是題目中的數據范圍控制不好就會爆longlong，上面提到的，有貢獻的點必須滿足x和y小于等于一個limit，這個limit開大了開小了都會Wa，差不多2e16是可以AC的

代碼：

#include<iostream> #include<cstdio> #include<string> #include<ctime> #include<cstring> #include<algorithm> #include<stack> #include<queue> #include<map> #include<set> #include<cmath> #include<sstream> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e5+100;const LL limit=2e16;struct Node {LL x,y;Node(LL X,LL Y){x=X;y=Y;} };LL dis(Node a,Node b) {return llabs(a.x-b.x)+llabs(a.y-b.y); }int main() { // freopen("input.txt","r",stdin); // ios::sync_with_stdio(false);LL x0,y0,ax,ay,bx,by,xs,ys,t;cin>>x0>>y0>>ax>>ay>>bx>>by>>xs>>ys>>t;LL x=x0,y=y0;Node start=Node(xs,ys);vector<Node>node;while(x<=limit&&y<=limit){node.push_back(Node(x,y));x=x*ax+bx,y=y*ay+by;}int ans=0;for(int st=0;st<node.size();st++)for(int ed=0;ed<node.size();ed++)if(dis(node[st],node[ed])+dis(start,node[st])<=t)ans=max(ans,abs(st-ed)+1);printf("%d\n",ans);return 0; }

?

總結

以上是生活随笔為你收集整理的CodeForces - 1293D Aroma's Search(暴力)的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。