联合省选 2024 Day1 T1 题解

cancan123456 · 2024-03-02 15:35:41 · 个人记录

形式化题面：给出 2n 个整数 x_0,y_0,x_1,y_1,\dots,x_{n-1},y_{n-1}，与整数 x,y，求最小的非负整数 m 满足存在 2n 个实数 x_0',y_0',x_1',y_1',\dots,x_{m-1}',y_{m-1}' 使得 \sum_{i=0}^{m-1}x_i'+x_{i\bmod n}=x,\sum_{i=0}^{m-1}y_i'+y_{i\bmod n}=y 且对于任意 0\le i<m 有 |x_i'|+|y_i'|\le k 或报告不存在这样的非负整数 m。

首先将条件变形：

我们断言该不定方程组有解的充要条件为：

上推下：由 |a+b|^2=(a+b)^2=a^2+2ab+b^2\le|a|^2+2|a||b|+|b|^2\le(|a|+|b|)^2 可知 |a+b|\le|a|+|b|，所以

下推上：

取 x_i'=\dfrac{C_x}m,y_i'=\dfrac{C_y}m 即可，容易验证其符合条件。

回到原题，考虑枚举 Q=m\bmod n，设 P=\dfrac{m-i}n，则：

记 k_1=\sum_{i=0}^{n-1}x_i,b_1=\sum_{i=0}^{Q-1}x_i,k_2=\sum_{i=0}^{n-1}y_i,b_2=\sum_{i=0}^{Q-1}y_i，则我们需要找到最小的 P 使得 |k_1P+b_1|+|k_2P+b_2|P\le(Pn+Q)k=nkP+Qk，只需要对 k_1P+b_1 和 k_2P+b_2 的符号进行分类讨论然后拆绝对值即可。

时间复杂度为 O(n)，可以通过此题。

写法好可以写得很快，下面是我考场上写了 70 分钟的代码：

#include <cstdio>
using namespace std;
typedef long long ll;
const int N = 100005;
ll x[N], y[N], xsum[N], ysum[N];
ll abs(ll x) {
    return x < 0 ? -x : x;
}
ll min(ll a, ll b) {
    return a < b ? a : b;
}
ll max(ll a, ll b) {
    return a > b ? a : b;
}
void swap(ll a, ll b) {
    a ^= b ^= a ^= b;
}
ll ceil_div(ll a, ll b);
ll floor_div(ll a, ll b) {
    if (a >= 0) {
        return a / b;
    } else {
        return -ceil_div(-a, b);
    }
}
ll ceil_div(ll a, ll b) {
    if (a >= 0) {
        return (a + b - 1) / b;
    } else {
        return -floor_div(-a, b);
    }
}
struct Solution {
    ll l, r;
    bool okl, okr;
    Solution() {
        okl = okr = false;
    }
    bool empty() {
        return okl && okr && l > r;
    }
    ll get_min() {
        if (empty()) {
            return -1;
        } else if (!okl) {
            return 0;
        } else if (okr && r < 0) {
            return -1;
        } else {
            return max(l, 0);
        }
    }
};
Solution empty_sol() {
    Solution E;
    E.okl = E.okr = true;
    E.l = +1;
    E.r = -1;
    return E;
}
Solution operator + (const Solution & a, const Solution & b) {
    Solution c;
    if (a.okl && b.okl) {
        c.okl = true;
        c.l = max(a.l, b.l);
    } else if (a.okl && !b.okl) {
        c.okl = true;
        c.l = a.l;
    } else if (!a.okl && b.okl) {
        c.okl = true;
        c.l = b.l;
    } else {
        c.okl = false;
    }
    if (a.okr && b.okr) {
        c.okr = true;
        c.r = min(a.r, b.r);
    } else if (a.okr && !b.okr) {
        c.okr = true;
        c.r = a.r;
    } else if (!a.okr && b.okr) {
        c.okr = true;
        c.r = b.r;
    } else {
        c.okr = false;
    }
    return c;
}
Solution solve_kx_ge_b(ll k, ll b);
Solution solve_kx_le_b(ll k, ll b) {
    // solution of kx <= b
    if (k == 0) {
        return 0 <= b ? Solution() : empty_sol();
    } else if (k > 0) {
        Solution res;
        res.okr = true;
        res.r = floor_div(b, k);
        return res;
    } else {
        return solve_kx_ge_b(-k, -b);
    }
}
Solution solve_kx_ge_b(ll k, ll b) {
    // solution of kx >= b
    if (k == 0) {
        return 0 >= b ? Solution() : empty_sol();
    } else if (k > 0) {
        Solution res;
        res.okl = true;
        res.l = ceil_div(b, k);
        return res;
    } else {
        return solve_kx_le_b(-k, -b);
    }
}
ll my_min(ll a, ll b) {
    if (a == -1 || b == -1) {
        return a + b + 1;
    } else {
        return min(a, b);
    }
}
ll my_kP_plus_b(ll P, ll k, ll b) {
    if (P == -1) {
        return -1;
    } else {
        return k * P + b;
    }
}
int main() {
    freopen("wind.in", "r", stdin);
    freopen("wind.out", "w", stdout);
    int T;
    scanf("%d", &T);
    ll k, X, Y;
    for (int n; T != 0; T--) {
        scanf("%d %lld %lld %lld", &n, &k, &X, &Y);
        for (int i = 0; i < n; i++) {
            scanf("%lld %lld", &x[i], &y[i]);
        }
        for (int i = 1; i <= n; i++) {
            xsum[i] = xsum[i - 1] + x[i - 1];
            ysum[i] = ysum[i - 1] + y[i - 1];
        }
        ll ans = -1;
        for (int i = 0; i < n; i++) {
            // k mod n = i.
            ll k1 = xsum[n], k2 = ysum[n];
            ll b1 = xsum[i] - X, b2 = ysum[i] - Y;
            // solve abs(k1 * P + b1) + abs(k2 * P + b2) <= n * k * P + i * k
            ans = my_min(ans, my_kP_plus_b((solve_kx_ge_b(k1, -b1) + solve_kx_ge_b(k2, -b2) + solve_kx_le_b(+k1 + k2 - n * k, i * k - b1 - b2)).get_min(), n, i));
            ans = my_min(ans, my_kP_plus_b((solve_kx_ge_b(k1, -b1) + solve_kx_le_b(k2, -b2) + solve_kx_le_b(+k1 - k2 - n * k, i * k - b1 + b2)).get_min(), n, i));
            ans = my_min(ans, my_kP_plus_b((solve_kx_le_b(k1, -b1) + solve_kx_ge_b(k2, -b2) + solve_kx_le_b(-k1 + k2 - n * k, i * k + b1 - b2)).get_min(), n, i));
            ans = my_min(ans, my_kP_plus_b((solve_kx_le_b(k1, -b1) + solve_kx_le_b(k2, -b2) + solve_kx_le_b(-k1 - k2 - n * k, i * k + b1 + b2)).get_min(), n, i));
        }
        printf("%lld\n", ans);
    }
    return 0;
}

代码第 45 行和第 47 行的 if 顺序写反了，对 k_1,k_2 符号进行分类讨论可以证明这不影响正确性。