A16813. Blackslex and Girls
编程题
普及+/提高
知识点
题目描述
在尝试用定长比特串的 De Bruijn 序列搭讪女生失败后，Blackslex 转而投身于政治。
凭借其极高的个人魅力，他现在负责为国家的 $n$ 个选区划定边界。在 Blackslex 所在的国家中，党派 A 有 $x$ 名选民，党派 B 有 $y$ 名选民。凭借其高超的区划技艺，他可以随意将任意党派的选民分配到任意选区。
由于他对比特串的执着，他想知道是否能够将选民分配，使得每个选区的获胜者符合某个比特串的模式。为了避免被怀疑，他还必须确保每个选区至少分配 $p_i$ 个选民。请你告诉他，是否可以做到！
形式化地，给定一个长度为 $n$ 的二进制字符串 $s$，一个长度为 $n$ 的数组 $p$，以及两个整数 $x$ 和 $y$。
你需要判断是否存在长度为 $n$ 的两个非负整数数组 $a$ 和 $b$，使得满足以下所有条件：
- $a_1 + a_2 + \dots + a_n = x$
- $b_1 + b_2 + \dots + b_n = y$
- 对于每个 $1 \leq i \leq n$，$a_i + b_i \geq p_i$
- 对于每个 $1 \leq i \leq n$：
- 如果 $s_i = 0$，则 $a_i > b_i$
- 如果 $s_i = 1$，则 $b_i > a_i$
凭借其极高的个人魅力，他现在负责为国家的 $n$ 个选区划定边界。在 Blackslex 所在的国家中，党派 A 有 $x$ 名选民，党派 B 有 $y$ 名选民。凭借其高超的区划技艺，他可以随意将任意党派的选民分配到任意选区。
由于他对比特串的执着，他想知道是否能够将选民分配，使得每个选区的获胜者符合某个比特串的模式。为了避免被怀疑，他还必须确保每个选区至少分配 $p_i$ 个选民。请你告诉他，是否可以做到！
形式化地，给定一个长度为 $n$ 的二进制字符串 $s$，一个长度为 $n$ 的数组 $p$，以及两个整数 $x$ 和 $y$。
你需要判断是否存在长度为 $n$ 的两个非负整数数组 $a$ 和 $b$，使得满足以下所有条件：
- $a_1 + a_2 + \dots + a_n = x$
- $b_1 + b_2 + \dots + b_n = y$
- 对于每个 $1 \leq i \leq n$，$a_i + b_i \geq p_i$
- 对于每个 $1 \leq i \leq n$：
- 如果 $s_i = 0$，则 $a_i > b_i$
- 如果 $s_i = 1$，则 $b_i > a_i$
输入格式
第一行包含一个整数 $t$（$1 \leq t \leq 10^4$）——表示测试用例的数量。
每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$1 \leq n \leq 2 \times 10^5$，$1 \leq x, y \leq 10^9$）。
第二行包含一个长度为 $n$ 的二进制字符串 $s$。
第三行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq 10^9$）。
所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。
每个测试用例的第一行包含三个整数 $n$、$x$ 和 $y$（$1 \leq n \leq 2 \times 10^5$，$1 \leq x, y \leq 10^9$）。
第二行包含一个长度为 $n$ 的二进制字符串 $s$。
第三行包含 $n$ 个整数 $p_1, p_2, \dots, p_n$（$1 \leq p_i \leq 10^9$）。
所有测试用例中 $n$ 的总和不超过 $2 \times 10^5$。
输出格式
对于每个测试用例，如果存在满足所有条件的数组 $a, b$，则输出（不区分大小写）YES，否则输出 NO。
输入输出样例
输入 #1
6 3 5 5 010 2 4 3 4 2 3 0001 1 1 1 1 2 4 2 00 3 3 4 23 20 1111 2 2 2 2 1 25 26 0 51 2 4 2 00 3 4
输出 #1
YES NO YES NO NO NO
说明/提示
在第一个测试用例中，一种可行的选民分布为：$a = [2, 0, 3]$，$b = [0, 4, 1]$。
在第三个测试用例中，一种可行的分配为：$a = [2, 2]$，$b = [1, 1]$。
对于其他测试用例，可以证明不存在满足要求的分配方案。
在第三个测试用例中，一种可行的分配为：$a = [2, 2]$，$b = [1, 1]$。
对于其他测试用例，可以证明不存在满足要求的分配方案。