题解：CF2179E Blackslex and Girls

znzryb · 2025-12-28 15:27:27 · 题解

题目

本题包含 t 组数据。

每组数据给定 N，两类票的总数 X, Y，一个长度为 N 的二进制串 s，以及数组 A。

我们需要把所有票分到 N 个选区里。设第 i 个选区分到两类票分别为 x_i, y_i，要求满足以下条件：

对每个 i，有 x_i + y_i \ge A_i。
若 s_i = 0，则 x_i > y_i；若 s_i = 1，则 y_i > x_i。

若存在一种分配方案，输出 YES；否则输出 NO。

思路讲解

本题的关键在于“每个选区至少 A_i 张票”。即使我们满足了所有下界，剩余的票也必须分配到某些选区，且不能改变原有的胜负关系。

第一步：每个选区的最小合法分配

首先，我们考虑每个选区的最小合法分配。

::::warning{open} 注意，这里做每个选区的最小合法分配时有一个陷阱，如果说选区要求人数是 2，且要求 X 赢，那么，那么我们会给这个选区分配 2 个这个 X 的人，分配 0 个 Y 的人（根据我们的算法）。但，这样分配，实际上 Y 这里还可以在分配一个人也不会出事，因此最后在调配的时候还要注意一下这个地方，最小合法分配并不代表一定无法给弱势方再加人了。 ::::

对于第 i 个选区，若想让胜者严格多一票且总票数尽量少，我们应使总票数接近 A_i，并让胜者获得 \lfloor A_i/2 \rfloor + 1 票。

若 s_i = 0，最小分配为：

x_i^{\min} = \left\lfloor \frac{A_i}{2} \right\rfloor + 1,\quad y_i^{\min} = A_i - x_i^{\min}

若 s_i = 1，最小分配为：

y_i^{\min} = \left\lfloor \frac{A_i}{2} \right\rfloor + 1,\quad x_i^{\min} = A_i - y_i^{\min}

我们将所有选区的最小分配累加，并从总票数中扣除，得到剩余票数：

opX = X - \sum x_i^{\min},\quad opY = Y - \sum y_i^{\min}

若 opX < 0 且 opY < 0，说明两类票都不足以满足下界，直接输出 NO。

第二步：处理 opX, opY 都非负的情况

当 opX \ge 0 且 opY \ge 0 时，基本要求已满足。接下来的问题是如何将剩余的 opX 张 X 类票和 opY 张 Y 类票分配到选区中，且不改变胜负结果。

如果 s 中既有 0 又有 1：我们可以把所有额外的 X 类票加到某个 s_i = 0 的选区（胜者加票不影响胜负），把所有额外的 Y 类票加到某个 s_i = 1 的选区。这样胜负关系一定不会改变，故输出 YES。
如果 s 全是 1：所有选区都要求 y_i > x_i。我们计算每个选区在最小分配下的差值 \Delta_i = y_i^{\min} - x_i^{\min}，显然 \Delta_i \ge 1。在不额外投 Y 类票的前提下，第 i 个选区最多还能“白塞”一些 X 类票而不翻盘，数量为：

\max\left(0,\ \Delta_i - 1\right)

我们将所有选区的这些“白塞容量”累加，从 opX 中扣除。如果 opX 仍有剩余，说明我们需要用 Y 类票去“对冲”这些多余的 X 类票。此时，若 opY 足够大（即 opY 不小于剩余的 opX），则可以维持胜负关系，输出 YES；否则输出 NO。

如果 s 全是 0：同理，完全对称地处理即可。

这一步对应代码中的 check_when_opx_opy_big_0 函数。

第三步：利用“少数票”替换“多数票”修正负数缺口

若最小分配后出现一正一负的情况，例如 opX < 0 但 opY \ge 0，这意味着按最小分配所需的 X 类票超过了现有数量，但 Y 类票有剩余。

这时我们可以利用 s_i = 1 的选区。因为在这些选区里 Y 类票是多数，我们可以在不改变胜负的前提下，将其中一部分原本分配给 X 的票替换成 Y 类票。每替换一张，状态更新为：

opX \leftarrow opX + 1,\quad opY \leftarrow opY - 1

单个选区最多能替换的数量不超过它在最小分配里拿到的少数票数，即 x_i^{\min}。我们可以遍历所有 s_i = 1 的选区，贪心地进行替换，直到 opX 不再为负，或者 opY 耗尽。

对称地，如果 opY < 0 但 opX \ge 0，我们就去遍历 s_i = 0 的选区，把一部分 Y 类票替换成 X 类票，单个选区的替换上限是 y_i^{\min}。

替换结束后，若能让 opX, opY 同时非负，则回到第二步继续判定；否则输出 NO。

AC代码

https://codeforces.com/contest/2179/submission/355016537 ::::info[代码]

/**
 * Problem: E. Blackslex and Girls
 * Contest: Codeforces Round 1071 (Div. 3)
 * Judge: Codeforces
 * URL: https://codeforces.com/contest/2179/problem/E
 * Created: 2025-12-23 23:17:50
 * Author: Gospel_rock
 */

#include <bits/stdc++.h>
#include <ranges>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<":"<<var<<"\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using LD = long double;
// using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7; 
static constexpr double eps = 1e-8;
const double pi = acos(-1.0);

ll lT;

/*
 *
 */

void Solve() {
    ll N, X, Y;
    cin >> N >> X >> Y;
    string s;
    cin >> s;
    vector<ll> cnt01(2);
    for (int i=0;i<s.size();++i) {
        cnt01[s[i]-'0']++;
    }

    vector<ll> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    ll opX=X,opY=Y;
    vector<array<ll,2>> suf_cnt_01(N);
    // for (int i=N-2;i>=0;--i) {
    //     suf_cnt_01[i]=suf_cnt_01[i+1];
    //     suf_cnt_01[i][s[i+1]-'0']++;
    // }

    for (int i=0;i < N;++i) {
        if (s[i]=='0') {
            ll consume_x=A[i]/2+1,consume_y=A[i]-consume_x;
            if (consume_y<0) consume_y=0;
            opX-=consume_x;
            opY-=consume_y;
        }else if (s[i]=='1'){
            ll consume_y=A[i]/2+1,consume_x=A[i]-consume_y;
            if (consume_x<0) consume_x=0;
            opX-=consume_x;
            opY-=consume_y;
        }
    }
    // debug(opX);
    // debug(opY);
    if (opX<0 && opY<0) {
        cout<<"NO\n";
        return;
    }

    auto check_when_opx_opy_big_0=[&]() {
        if (opX>=0 && opY>=0) {
            if (cnt01[0] && cnt01[1]) {
                cout<<"YES\n";
                return true;
            }
            if (cnt01[1]/* && opY>=opX*/) {
                ll oopx=opX;
                for (int i=0;i<s.size();++i) {
                    if (s[i]=='1') {
                        ll consume_y=A[i]/2+1,consume_x=A[i]-consume_y;
                        if (consume_x<0) consume_x=0;
                        oopx-=max(0ll,consume_y-consume_x-1);
                    }
                }
                if (opY>=oopx) {
                    cout<<"YES\n";
                    return true;
                }
            }
            if (cnt01[0] /*&& opX>=opY*/) {
                ll oopy=opY;
                for (int i=0;i<s.size();++i) {
                    if (s[i]=='0') {
                        ll consume_x=A[i]/2+1,consume_y=A[i]-consume_x;
                        if (consume_y<0) consume_y=0;
                        oopy-=max(0ll,consume_x-consume_y-1);
                    }
                }
                if (opX>=oopy) {
                    cout<<"YES\n";
                    return true;
                }
            }
            cout<<"NO\n";
            return true;
        }
        return false;
    };
    if (check_when_opx_opy_big_0()) {
        return;
    }
    if (opY>=abs(opX)) {
        for (int i=0;i<N;++i) {
            if (s[i]=='1') {
                ll consume_y=A[i]/2+1,consume_x=A[i]-consume_y;
                if (consume_x<0) consume_x=0;
                ll can_be_replace_with_y=min({consume_x, opY,abs(opX)});
                opY-=can_be_replace_with_y;
                opX+=can_be_replace_with_y;
            }
        }
        if (check_when_opx_opy_big_0()) {
            return;
        }
    }
    if (opX>=abs(opY)) {
        for (int i=0;i<N;++i) {
            if (s[i]=='0') {
                ll consume_x=A[i]/2+1,consume_y=A[i]-consume_x;
                if (consume_y<0) consume_y=0;
                ll can_be_replace_with_x=min({consume_y, opX, abs(opY)});
                opX-=can_be_replace_with_x;
                opY+=can_be_replace_with_x;
            }
        }
        if (check_when_opx_opy_big_0()) {
            return;
        }
    }
    cout<<"NO\n";

}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    cin >> lT;
    while (lT--)
        Solve();
    return 0;
}

/*

1
4 4 5
1101
3 2 1 2

1
4 2 3
0001
1 1 1 1

1
7 11 3
0000000
1 3 1 2 2 1 3

1
3 4 7
111
3 1 2

*/

::::