题解 P10217 【[省选联考 2024] 季风】

Mine_King · 2024-03-09 08:29:20 · 题解

谨以此题解纪念我今年 Day1 T1 因少分讨一个 corner case 而 F 了 10 分。

Problem

省选联考 2024 Day1 T1 季风

题目大意：

给定 n, k, x, y 和 2n 个整数 x _ 0, y _ 0, x _ 1, y _ 1, \ldots, x _ {n - 1}, y _ {n - 1}。

找到最小的非负整数 m，使得存在 2m 个实数 x _ 0', y _ 0', x _ 1', y _ 1', \ldots, x _ {m - 1}', y _ {m - 1}' 满足以下条件，或报告不存在这样的 m：

特别地，m = 0 时，认为 \sum\limits _ {i = 0} ^ {m - 1} (x _ i' + x _ {i \bmod n}) 和 \sum\limits _ {i = 0} ^ {m - 1} (y _ i' + y _ {i \bmod n}) 均为 0。

形象理解就是初始在原点，每次可以选择一个向量 (x', y')，然后将位置加上这个向量，然后时刻 i 季风会使你的位置会加上 (x _ {i \bmod n}, y _ {i \bmod n})，问最少要多少时间才能走到 (x, y)，要求每次选择的 |x'| + |y'| \le k。

Solution

为防止混淆，以下用 ex, ey 代替题目中的 x, y。

显然可以把 x, y 的贡献和 x', y' 的贡献分开来计算。

考虑所有模 n 同余的时间，x, y 的贡献会相差 X = \sum _ {i = 0} ^ {n - 1} x _ i, Y = \sum _ {i = 0} ^ {n - 1} y _ i 的若干倍，因此可以考虑将时间按模 n 的余数划分，分别求解答案然后取最小值。

设当前考虑的时间是 tn + r，则 x, y 产生的贡献分别是 tX + \sum _ {i = 1} ^ {r - 1} x _ i, tY + \sum _ {i = 1} ^ {r - 1} y _ i，考虑合理规划 x', y' 的取值使得可以到达 (ex, ey)。

我们发现只有最后一个限制将横坐标和纵坐标绑在一起了，于是考虑用一些方法分离横纵坐标变成一个一维的问题。
原限制相当于要求 (x _ i', y _ i') 到原点的曼哈顿距离不超过 k，因此只需要将点逆时针旋转 \frac{\pi}{4} 就可以将曼哈顿距离转成切比雪夫距离。
具体地，我们知道 (x, y) 逆时针旋转 \frac{\pi}{4} 后会变成 (\frac{x - y}{\sqrt{2}}, \frac{x + y}{\sqrt{2}})，为了方便，我们再令每个点的横纵坐标都乘上 \sqrt{2}，显然这样不会出现问题，然后只需要将 x, y, ex, ey 都这样旋转一下就行了，然后原本的限制就变成了 \max\{x', y'\} \le k，即 x' \le k, y' \le k。

接下来我们只考虑横坐标，纵坐标的求解是一样的。
显然 -k(tn + r) \le \sum _ {i = 1} ^ {m - 1} x _ i' \le k(tn + r)，并且不难发现对于任意 -k(tn + r) \le v \le k(tn + r)，都一定可以构造一组 x' 使得 \sum _ {i = 1} ^ {m - 1} x _ i' = v。
因此我们只需要满足：

方便起见我们令 ex \gets ex - \sum _ {i = 1} ^ {r - 1} x _ i。

现在问题转化为给定 l, r, l', r'，求 t 的取值范围，使得 [tl, tr] \cap [l', r'] \ne \varnothing，显然合法的 t 是一个区间，我们只需要求出这个区间然后将横纵坐标的区间取个交即可得到答案。

然后考虑这个东西怎么求，只需要一些小小的分讨：

首先可以钦定 r' \ge 0，若 r' < 0 则将两个区间都关于原点对称即可。

首先考虑区间下界：

• 若 tl \le 0，则 t 的下界为 0。
• 否则若 r \le 0，则无解。
• 否则答案为 \left\lceil\frac{tl}{r}\right\rceil。

然后考虑区间上界：

• 若 l \le 0：
  • 若 r < 0, tl \le 0，则 t 的上界为 \left\lfloor\frac{tl}{r}\right\rfloor。
  • 否则，抛开上面提到的无解情况，答案为 +\infty。
• 否则答案为 \left\lfloor\frac{tr}{l}\right\rfloor。

至此这题就做完了。

Code

// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int T, n;
long long k, tx, ty;
long long x[100005], y[100005];

void rotate(long long &x, long long &y) {
    long long ax = x - y, ay = x + y;
    x = ax, y = ay;
    return ;
}
pair<long long, long long> calc(long long l, long long r, long long tl, long long tr) {
    if (tr < 0) {
        l = -l, r = -r, swap(l, r);
        tl = -tl, tr = -tr, swap(tl, tr);
    }
    pair<long long, long long> res;
    if (tl <= 0) res.first = 0;
    else {
        if (r > 0) res.first = (tl + r - 1) / r;
        else return {0, -1};
    }
    if (l <= 0) {
        if (r < 0 && tl <= 0) res.second = -tl / -r;
        else res.second = 0x3f3f3f3f3f3f3f3f;
    } else res.second = tr / l;
    return res;
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> T;
    while (T--) {
        cin >> n >> k >> tx >> ty, rotate(tx, ty);
        for (int i = 0; i < n; i++) cin >> x[i] >> y[i], rotate(x[i], y[i]);
        for (int i = 1; i < n; i++) x[i] += x[i - 1], y[i] += y[i - 1];
        long long X = x[n - 1], Y = y[n - 1];
        long long ans = -1;
        for (int i = 0; i < n; i++) {
            long long xp = tx, yp = ty;
            if (i) xp -= x[i - 1], yp -= y[i - 1];
            pair<long long, long long> ix = calc(X - n * k, X + n * k, xp - i * k, xp + i * k);
            pair<long long, long long> iy = calc(Y - n * k, Y + n * k, yp - i * k, yp + i * k);
            pair<long long, long long> interval(max(ix.first, iy.first), min(ix.second, iy.second));
            if (interval.first > interval.second) continue;
            long long res = interval.first * n + i;
            if (ans == -1 || res < ans) ans = res;
        }
        cout << ans << '\n';
    }
    return 0;
}