本章节参考:2020,2021 年 CF 简单题精选 - 题单 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
首先，很容易观察到点的一些特征:
- 都在第一象限；
- 点的分布越来越稀疏。
以样例为例：
还有无限个点没有画出来。
根据点的分布越来越稀疏的特性，能不能发现收集点的规律呢？
比如我们可以先枚举一个点 \(i\)，直接从 \((x_s, y_s)\) 出发去收集 \(\text P_i\)。
然后呢？如果往 \(\text P_0\) 的方向收集，点会非常密集；如果往 \(\text P_\infty\) 的方向收集，点就会非常稀疏。
当然，我们往 \(\text P_0\) 的方向收集！
但是，这边的点是有限的，如果全部收集完了时间还绰绰有余呢？
那就原路返回，再往 \(\text P_\infty\) 的方向收集！
有人可能会疑惑，为什么这里都原路返回了，答案还是最优呢？
首先，因为随着 \(j\) 的增大，\(x_j, y_j\) 都在增大，所以 \(\sum_{j = 1}^{i}\operatorname{dist}(\text P_{j-1}, \text P_j)\)（也就是从 \(\text P_i\) 收集到 \(\text P_0\) 的总距离）就等于 \(\operatorname{dist}(\text P_0 ,\text P_i)\)（\(\operatorname{dist}\) 表示曼哈顿距离）。
下面为了分析方便只看 \(x\) 坐标（\(\operatorname{Xdist}\) 表示 \(x\) 坐标之差）。
点最密集的时候应该是什么时候？很显然，\(a_x\) 和 \(b_x\) 都最小的时候，也就是 \(a_x = 2, b_x = 0\)。
\[ \operatorname{Xdist}(\text P_{i+1}, \text P_{i}) = (a_x \cdot x_{i} + b_x) - x_{i} = (a_x - 1)\cdot x_{i} + b_x = x_i \]
\[ \operatorname{Xdist}(\text P_{0}, \text P_{i}) = x_i - x_0 \]
\(\because x_0 \ge 1 \quad \therefore \operatorname{Xdist}(\text P_{i+1}, \text P_{i}) > \operatorname{Xdist}(\text P_{0}, \text P_{i})\)
现在 \(y\) 坐标也加进来，就可以得到 \(\operatorname{dist}(\text P_{i+1}, \text P_{i}) > \operatorname{dist}(\text P_{0}, \text P_{i})\)。
这说明什么？收集 \(\text P_0 \sim \text P_{i - 1}\) 的时间比只收集一个 \(\text P_{i + 1}\) 的时间还要少！
如果当初选择向右走，那再去收集 \(\text P_{i + 2}\) 的时候，显然 \(\operatorname{dist}(\text P_{i+1}, \text P_{i +2}) > \operatorname{dist}(\text P_{i}, \text P_{i+1})\)，那么 \(\operatorname{dist}(\text P_{i+1}, \text P_{i +2}) + \operatorname{dist}(\text P_{i}, \text P_{i+1}) > 2 \operatorname{dist}(\text P_{0}, \text P_{i})\)。说明向 \(\text P_{\infty}\) 方向收集 \(2\) 个点的时候，\(\text P_0\) 方向已经回来了，并收集了 \(i\) 个点，如果 \(i \ge 2\) 那么直接可以知道答案更优了，还剩两种情况：
- \(i=0\)，这时没什么左右之分，那不影响答案；
- \(i=1\)，直接带入算一算，\(x_1 = 2 x_0\)，\(x_2 = 4 x_0\)，那么左边加上返回的时间是 \(2 x_0\)，直接去 \(\text P_2\) 的时间也是 \(2 x_0\)，因为越往后点越稀疏，而两种方案当前耗时相同，起点不同，所以 \(\text P_0\) 方向还是更优。
还有一个小问题，就是数组开多大，因为 \(2^{64} > 10^{18}\)，所以数组开到 \(70\) 就绰绰有余了。
时间复杂度 \(\mathcal O(n^2)\)，\(n\) 是要用到的点数，算到 \(x_n > x_s, y_n > y_s, \operatorname{dist}(\text P_n, \text S) > t\) 即可。
//https://codeforces.com/contest/1292/problem/B /* 38 70 2 2 67 88 6838924170055088 456766390500883 9176106261147424 调了半天,最终还是A了 由数据范围可知道,由于数据点是以指数级增长的,所以最多有2^64>=10^16,也就是顶多64个 然后 由于数据点一共就64个,不难想到暴力枚举,我认为比较难的地方就在于如何去枚举,如果 我们真的是纯暴力的话,每个点有选或不选,那么就是2^64,肯定不行 由于数据点是指数级爆炸增长,所以说可以这样想,假设原点在某两点之间,那么我们要先把左边的遍历完再遍历右边 可以想 2^0+2^1+....2^n-1相加,他们的和 是不如 2^n大的,所以说我们走2^n这个点不如走n-1所有点 */ //3,144,565,100,727,795 //5,102,364,399,534,485 #include<bits/stdc++.h> #define int long long using namespace std; const int N=2e5+10; int res; //bool cmp(pair<int,int>a,pair<int,int>b) //{ // return a.first<b.first; //} signed main() { int x0,y0,ax,ay,bx,by,xs,ys,t,f=0,pos; cin>>x0>>y0>>ax>>ay>>bx>>by>>xs>>ys>>t; vector<pair<int,int>>point; point.push_back({x0,y0}); for(int i=1;i<=61;i++){ int x=x0*ax+bx,y=y0*ay+by; if(x<0||y<0) break; if(x0*ax+bx>=1e17||y0*ay+by>=1e17) break; point.push_back({x,y}),x0=x,y0=y; } // sort(point.begin(),point.end(),cmp); // int vis=0; // for(int i=0;i<point.size();i++) // if(point[i]==make_pair(xs,ys)) pos=i,vis++; // // cout<<pos<<endl; // for(auto i:point) cout<<i.first<<' '<<i.second<<endl; // // for(int i=pos;i<point.size();i++){ // int ans=0,nowx=xs,nowy=ys,t_=t; //// cout<<"右: "<<endl; // for(int j=pos+1;j<=i;j++){ //// cout<<t_<<endl; //// cout<<j<<' '<<point[j].first<<' '<<point[j].second<<endl; // if(point[j]==make_pair(xs,ys)) continue; // int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy)); // if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second; // else break; // } //// cout<<"左: "<<endl; // for(int j=pos;j>=0;j--){ //// cout<<t_<<endl; //// cout<<j<<' '<<point[j].first<<' '<<point[j].second<<' '<<endl; // if(point[j]==make_pair(xs,ys)) continue; // int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy)); // if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second; // } //// cout<<ans<<endl; // res=max(res,ans); // } for(int i=0;i<point.size();i++){ int t_=t,nowx=xs,nowy=ys,ans=0; for(int j=i;j>=0;j--){ int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy)); if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second; } for(int j=i+1;j<point.size();j++){ int x=(abs(point[j].first-nowx)+abs(point[j].second-nowy)); if(t_>=x) t_-=x,ans++,nowx=point[j].first,nowy=point[j].second; else break; } res=max(res,ans); } // if(vis>=2) res++; cout<<res; return 0; }