CF1292B Aroma’s Search 题解

题意：

获得了新身体后，我们的偶像 Aroma White（或者应该被称为 Kaori Minamiya？）开始在 OS 空间中寻找她尘封的过去。

这个空间可以看作是一个二维平面，在其内部有着无限多的数据点，从 $0$ 开始标号，它们的坐标定义如下：

第 $0$ 个点的坐标为 $(x_0, y_0)$。

对于 $i > 0$，第 $i$ 个点的坐标为 $(x_i, y_i) = (a_x \cdot x_{i-1} + b_x, a_y \cdot y_{i-1} + b_y)$。

初始时 Aroma 的位置为 $(x_s, y_s)$。她只能留在 OS 空间中最多 $t$ 秒，因为她还需要传送回真实世界。她不需要返回初始位置 $(x_s, y_s)$ 也能传送回家。

在 OS 空间中，Aroma 可以做如下操作：

在点 $(x, y)$ 上时，Aroma 可以移动到这四个点之一：$(x-1, y), (x+1, y), (x, y-1), (x, y+1)$。这个操作需要耗费 $1$ 秒。

如果 Aroma 当前的位置上有数据点，她可以收集它。我们可以假定这个操作耗费 $0$ 秒。当然，每个数据点只能被收集一次。

Aroma 想要在传送回去之前，收集尽可能多的数据点。你能帮助她计算在 $t$ 秒内最多能收集的数据点的个数吗？

输入格式：

第一行输入六个整数 $x_0, y_0, a_x, a_y, b_x, b_y$，通过它们可以确定数据点的坐标。

第二行输入三个整数 $x_s, y_s, t$，表示 Aroma 的初始位置和可用的时间。

输出格式：

输出一个整数，表示 Aroma 最多能收集的数据点个数。

数据范围：

$1 \le x_0, y_0, x_s, x_y, t \le {10}^{16}$，$2 \le a_x, a_y \le 100$，$0 \le b_x, b_y \le {10}^{16}$。

可以发现这个点的增长速度是非常快的，这意味着点会越来越稀疏。

因此考虑贪心地从起始点出发向 $0$ 的方向走，如果还有时间就从距离 $0$ 最近的那个点向 $+\infty$ 方向走。

接着我们来证明，这样的做法是最优的。

考虑点最密集的情况（因为这种情况似乎更有可能出现反例），此时 $a_x = 2, b_x = 0$ 。

设离当前点最近的那个点是 $i$ ，我们考虑 $x$ 上的大小关系。

$\begin{aligned} d_x(i,~i + 1) = a_xx_i + b_x - x_i = x_i \\[6pt] \sum_{0 \le j < i}d_x(j,~j + 1) = d_x(0,i) = x_i - x_0 \end{aligned}$

而 $x_0 \ge 1$ 使得向 $+\infty$ 方向走一个点甚至不如向 $0$ 方向走到底，况且这还是最密集的情况。

可以预见的是，如果向 $+\infty$ 方向走了两个点，还不如向 $0$ 走到底再回来到 $i+1$ 。证毕。

时间复杂度 $\mathcal{O}(n^2)$

代码：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
void up(int &x,int y) { x < y ? x = y : 0; }
void down(int &x,int y) { x > y ? x = y : 0; }
#define N ((int)(60))

int ax,ay,bx,by,sx,sy,T,x[N],y[N];
int dis(int x1, int y1, int x2, int y2) { return abs(x1 - x2) + abs(y1 - y2); }
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> x[0] >> y[0] >> ax >> ay >> bx >> by;
    cin >> sx >> sy >> T;
    int n = 0, res = 0; 
    while(true)
    {
        ++n; x[n] = ax * x[n - 1] + bx; y[n] = ay * y[n - 1] + by;
        if(x[n] > sx && y[n] > sy && dis(sx, sy, x[n], y[n]) > T) break;
    }
    for(int i = 0; i <= n; i++)
        if(dis(sx, sy, x[i], y[i]) <= T)
        { 
            int r = 1, t = T - dis(sx, sy, x[i], y[i]);
            for(int j = i; j; j--) {
                if(dis(x[j], y[j], x[j - 1], y[j - 1]) <= t)
                    { t -= dis(x[j], y[j], x[j - 1], y[j - 1]), ++r; }
                else break;
            }
            for(int j = 1; j <= n; j++) {
                if(dis(x[j], y[j], x[j - 1], y[j - 1]) <= t)
                    { t -= dis(x[j], y[j], x[j - 1], y[j - 1]), r += (j > i); }
                else break;
            }
            up(res, r);
        }
    cout << res << '\n';
    return 0;
}