题目链接:https://codeforces.com/problemset/problem/1292/B
洛谷链接:https://www.luogu.com.cn/problem/CF1292B
主要还是没能多想想吧。
还是看了题解。其实并没有那么难。突破口是在上面。
我们可以发现假设bx = by = 0, pn的坐标就是(ax^n * px, ay^n * p)这是一个指数。所以在2e16范围内非常的小。大概是五六十个差不多。
之后还需要发现pn到pn+1的距离肯定是 > p0到p1 + p1到p2 + p2到 p3 ... pn-1到pn(具体可以结合2的幂次来理解 1 + 2 + 4 + ... 2^(n-1) = 2^n - 1 < 2^n
所以我们的最优策略肯定是先选一个起点往左走,之后走到p0之后开始走pi+1(你选定的起点右边的一个点)一直到体力不够为止。
由于点不多我们大可以枚举这个起点。
所以复杂度应该是log2e16 * log2e16
以下是AC代码:
#include <bits/stdc++.h> using namespace std; typedef long long ll; const int maxn = 2e6 + 10; #define x first #define y second int main() { ll x0, y0, ax, ay, bx, by; cin >> x0>> y0>> ax>> ay>> bx>> by; ll xs, ys, t; cin >> xs >> ys >> t; vector<pair<ll, ll> > point; while (x0 < 2e16 && y0 < 2e16) { ///注意这里不能开到1e17会wa132,如果比1e16小的话会WA更早 point.push_back({x0, y0}); x0 = x0 * ax + bx; y0 = y0 * ay + by; } //cout << point.size() << endl; int n = point.size(); int ans = 0; for (int i = 0; i < n; ++ i) { ll cost = 0; int cnt = 0; ll curx = xs, cury = ys; for (int j = i; j >= 0 && cost <= t; j --) { cost += abs(point[j].x-curx) + abs(point[j].y-cury); if (cost <= t) cnt ++; curx = point[j].x; cury = point[j].y; } for (int j = i+1; j < n && cost <= t; j ++) { cost += abs(point[j].x-curx) + abs(point[j].y-cury); if (cost <= t) cnt ++; curx = point[j].x; cury = point[j].y; } ans = max(cnt, ans); } cout << ans << endl; return 0; }