CF1292B Aroma’s Search

发布于 2020-10-24  40 次阅读


CF1292B

Description

平面上有无穷多个物品,坐标满足递推关系 x_i = a_i x_{i-1} + b_x, y_i=a_iy_{i-1}+b_y 起始位置在 (x s , y s ),每时刻可以向前后左

右移动 1 单位长度。当你移动到一个物品所在坐标时可以立即获得这个物品。求 t 时间内最多能获得多少物品。

Solution

透过现象看本质

注意到b_x,b_y的范围都很大,再观察物品的坐标是满足一个一次函数关系的。a_x,a_y是斜率,而截距很大。注意到自变量其实是你上一个坐标,所以这些物品的坐标会当x_{i-1},y_{i-1}达到一定范围的时候,增长极大。

由此我们可以知道,在我们有限的时间t内,是不可能走到很多点的(最多大概是100)左右,所以可以走到的这些物品的位置我们都可以算出来。

有了这些,我们只需要考虑如何选点即可。当x_{i-1},y_{i-1}还处于一个比较小的范围的时候,相对于全局他们的分布是密集的。当x_{i-1},y_{i-1}上升到一定大小时,两个点会间隔较远。t内有可能走不到。

于是我们贪心地走,因为点不多,所以我们可以枚举一个起始的物品,从它开始往下选物品,选到不能选到时候,走回来,看看还能不能往上选物品(因为实际上你的选物品的路径一定是一个从下网上选物品的)。

复杂度O(n^2)

写法还有很多种,效果是一样的。范围又小,这一种还比较好写,因为这道题细节有点多。

Code

又到了我最喜欢的代码环节

#include <bits/stdc++.h>
using namespace std;

#define int long long

int x0, Y0, ax, ay, bx, by, xs, ys, t;

std::vector < pair < int, int > > a;

inline int read()
{
    char ch = getchar();
    int f = 1, x = 0;
    while (ch < '0' || ch > '9') { if (ch == '-') f = -1; ch = getchar(); }
    while (ch >= '0' && ch <= '9') { x = (x << 1) + (x << 3) + ch - '0'; ch = getchar(); }
    return x * f;
}

inline void init()
{
    int xi = x0, yi = Y0, nx = 0, ny = 0;
    a.push_back(make_pair(x0, Y0));
    while (1) {
        nx = ax * xi + bx, ny = ay * yi + by;
        if (abs(nx - x0) > (1e17) || abs(ny - Y0) > (1e17)) break;
        a.push_back(make_pair(nx, ny));
        xi = nx, yi = ny;
    }
}

signed main()
{
    x0 = read(), Y0 = read(), ax = read(), ay = read(), bx = read(), by = read();
    xs = read(), ys = read(), t = read();
    init();
    int ans = 0;
    for (register int i = 0; i < a.size(); ++ i) {
        int tim = llabs(xs - a[i].first) + llabs(ys - a[i].second), cnt = 0;
        if (tim > t) continue;
        ++ cnt;
        int xi = a[i].first, yi = a[i].second;
        if (i > 0) {
            for (register int j = i - 1; j >= 0; -- j) {
                int dis = (llabs(xi - a[j].first) + llabs(yi - a[j].second));
                tim += dis;
                if (tim > t) break;
                ++ cnt;
                xi = a[j].first, yi = a[j].second;
            }
        }
        if (tim >= t) { ans = std::max(ans, cnt); continue; }
        for (register int j = i + 1; j < a.size(); ++ j) {
            int dis = llabs(xi - a[j].first) + llabs(yi - a[j].second);
            tim += dis;
            if (tim > t) break;
            ++ cnt;
            xi = a[j].first, yi = a[j].second;
        }
        ans = std::max(ans, cnt);
    }
    printf("%lld\n", ans);
    return 0;
}

朴实沉毅