P10217 [省选联考 2024] 季风解题报告

鼓豆帝王 · 2024-03-10 11:33:43 · 题解

题目连接：P10217 [省选联考 2024] 季风

解法说明

转化题意

我们先转化题意，整理一下题目里的式子

\sum \limits_{i=0}^{m-1} x_i'=x-\sum \limits_{i=0}^{m-1} x_{i\bmod n}
\sum \limits_{i=0}^{m-1} y_i'=y-\sum \limits_{i=0}^{m-1} y_{i\bmod n}
\left|\sum \limits_{i=0}^{m-1} x_i'\right|+\left|\sum \limits_{i=0}^{m-1} y_i'\right|\le mk

不难看出，本题就是想让我们找到最小的 m，使得

\left|x - \sum _{i=0}^{m-1} x_{i\bmod n}\right|+\left|y - \sum _{i=0}^{m-1} y_{i\bmod n}\right|\le mk

特殊情况

其实 n=1 的情况很有提示作用，根据转化后的题意，可以列出方程

|x-mx_0|+|y-my_0|\le mk

注意到其中 x,y,x_0,y_0,k 都是已知的常数，可以直接分类讨论解方程（其实写出正确的分类讨论才是难点，实在是烦）。

一般情况

我们推广上述情况，可以把原本方程中的 m 看成是周期数，那么我们只需要枚举 n 个周期的起点，解 n 遍这样的方程，再取结果中的最小值即可。

为表述方便，下面令

X_i=\sum \limits_{j=0}^ix_j,i\in[0,n-1]
Y_i=\sum \limits_{j=0}^iy_j,i\in[0,n-1]

则可列出方程

\begin{cases} |x-(X_i+tX_{n-1})|+|y-(Y_i+tY_{n-1})|\le (i+1+nt)k \\ t \ge 0 \end{cases} \\

可以把这个方程整理成我们熟悉的样子

\begin{cases} |(x-X_i)-X_{n-1}t|+|(y-Y_i)-Y_{n-1}t|\le nkt + (i+1)k \\ t \ge 0 \end{cases} \\

然后分类讨论解方程就行啦。

本题只需要开 long long 就够了，~~小心 abs(__int128)~~。

该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。

AC 代码

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

const ll maxN = 1e5 + 10;
const ll INF = 1e18;

struct numstr {
    ll x, y;
} nums[maxN];

ll t, n, k, x, y;
ll sumx, sumy, ans;

ll up(ll x, ll y) {
    ll res = x / y;
    if (res * y < x && y > 0) res++;
    if (res * y > x && y < 0) res++;
    return res;
}

ll down(ll x, ll y) {
    ll res = x / y;
    if (res * y > x && y > 0) res--;
    if (res * y < x && y < 0) res--;
    return res;
}

void solve(ll a, ll b, ll i, ll id) {
    ll l = 0, r = INF;
    if (sumx == 0) {
        if (a < 0) l = INF;
    }
    else if (sumx > 0) r = min(r, down(a, sumx));
    else l = max(l, up(a, sumx));
    if (sumy == 0) {
        if (b < 0) l = max(l, INF);
    }
    else if (sumy > 0) r = min(r, down(b, sumy));
    else l = max(l, up(b, sumy));
    ll q = sumx + sumy + n * k, p = a + b - i * k;
    if (q == 0) {
        if (p > 0) l = INF;
    }
    else if (q > 0) l = max(l, up(p, q));
    else r = min(r, down(p, q));
    if (l <= r && i + n * l >= 0) ans = min(ans, i + n * l);

    l = 0, r = INF;
    if (sumx == 0) {
        if (a > 0) l = INF;
    }
    else if (sumx > 0) l = max(l, up(a, sumx));
    else r = min(r, down(a, sumx));
    if (sumy == 0) {
        if (b < 0) l = max(l, INF);
    }
    else if (sumy > 0) r = min(r, down(b, sumy));
    else l = max(l, up(b, sumy));
    q = -sumx + sumy + n * k, p = -a + b - i * k;
    if (q == 0) {
        if (p > 0) l = INF;
    }
    else if (q > 0) l = max(l, up(p, q));
    else r = min(r, down(p, q));
    if (l <= r && i + n * l >= 0) ans = min(ans, i + n * l);

    l = 0, r = INF;
    if (sumx == 0) {
        if (a < 0) l = INF;
    }
    else if (sumx > 0) r = min(r, down(a, sumx));
    else l = max(l, up(a, sumx));
    if (sumy == 0) {
        if (b > 0) l = max(l, INF);
    }
    else if (sumy > 0) l = max(l, up(b, sumy));
    else r = min(r, down(b, sumy));
    q = sumx - sumy + n * k, p = a - b - i * k;
    if (q == 0) {
        if (p > 0) l = INF;
    }
    else if (q > 0) l = max(l, up(p, q));
    else r = min(r, down(p, q));
    if (l <= r && i + n * l >= 0) ans = min(ans, i + n * l);

    l = 0, r = INF;
    if (sumx == 0) {
        if (a > 0) l = INF;
    }
    else if (sumx > 0) l = max(l, up(a, sumx));
    else r = min(r, down(a, sumx));
    if (sumy == 0) {
        if (b > 0) l = max(l, INF);
    }
    else if (sumy > 0) l = max(l, up(b, sumy));
    else r = min(r, down(b, sumy));
    q = -sumx - sumy + n * k, p = -a - b - i * k;
    if (q == 0) {
        if (p > 0) l = INF;
    }
    else if (q > 0) l = max(l, up(p, q));
    else r = min(r, down(p, q));
    if (l <= r && i + n * l >= 0) ans = min(ans, i + n * l);
}

int main(void) {
    scanf("%lld", &t);
    for (ll j = 1; j <= t; j++) {
        scanf("%lld%lld%lld%lld", &n, &k, &x, &y);
        for (int i = 1; i <= n; i++) {
            scanf("%lld%lld", &nums[i].x, &nums[i].y);
        }
        if (x == 0 && y == 0) {
            printf("0\n");
            continue;
        }

        sumx = 0, sumy = 0;
        for (int i = 1; i <= n; i++) {
            sumx += nums[i].x, sumy += nums[i].y;
        }

        ll nowx = 0, nowy = 0;
        ans = INF;
        for (ll i = 1; i <= n; i++) {
            nowx += nums[i].x, nowy += nums[i].y;
            solve(x - nowx, y - nowy, i, j);
        }
        if (ans == INF) printf("-1\n");
        else printf("%lld\n", ans);
    }
    return 0;
}

P10217 [省选联考 2024] 季风 解题报告