题目链接: 核心考点: [[计算几何]]

B. Expansion Plan 2

时间限制：每个测试 1 秒 内存限制：每个测试 256 MB

问题描述

你正在分析一个坐标为 $(X,Y)$ 的无限网格（具体来说，$(0,0)$ 正上方的格子是 $(0,1)$，$(0,0)$ 正右方的格子是 $(1,0)$）。初始时，只有 $(0,0)$ 这个格子是黑色的。

给你一个长度为 $n$ 的字符串 $a_1a_2\dots a_n$，由字符 "4" 和 "8" 组成，它描述了 $n$ 次扩张操作。对于每个 $i$ 从 $1$ 到 $n$，所有格子同时发生以下变化：

• 如果 $s_i =$ "4"：对于每个格子，如果它与某个黑色格子正交相邻（即共享一条边），则它变为黑色；否则保持原状态不变。
• 如果 $s_i =$ "8"：对于每个格子，如果它与某个黑色格子正交或对角相邻（即共享一条边或一个角），则它变为黑色；否则保持原状态不变。

请问在过程结束后，格子 $(x,y)$ 是否为黑色？

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ ($1 \le t \le 10^4$)。

接下来是每个测试用例的描述： - 第一行包含三个整数 $n$, $x$, $y$ ($1 \le n \le 2 \cdot 10^5$, $-10^9 \le x,y \le 10^9$) — 分别表示扩张操作的数量，以及你关心的格子的坐标 - 第二行包含一个长度为 $n$ 的字符串 $s$，由字符 "4" 和 "8" 组成 — 表示扩张操作的类型

保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果格子 $(x,y)$ 在字符串 $s$ 描述的扩张操作后是黑色的，输出 YES，否则输出 NO。

判题系统对大小写不敏感（例如 YES, Yes, yes, yEs 都会被识别为肯定答案）。

样例输入

6
3 3 3
888
4 5 1
4884
4 3 -3
4884
7 -7 -5
4884884
10 0 0
4884884888
1 1 1
4

样例输出

YES
NO
YES
NO
YES
NO

Note

The first three test cases are illustrated below:

In the first test case, after the expansion operations in the string $\texttt{"888"}$, cell $(3, 3)$ is black, so the answer is $\texttt{YES}$.

In the second test case, cell $(5, 1)$ is white after the expansion operations in the string $\texttt{"4884"}$.

💡 核心直觉 (一句话总结)

我做这个题目的时候是直接找到规律

✅ 正解思路

• 首先对于在x=0 || y=0 的点，只要另一个坐标不超过n，那肯定行
• 然后就是直接将坐标压缩到第一象限，因为都是对称的
• 在第一象限中，我发现以列的视角来看，总共有k列高度均是n ,刚好和有多少的8的个数相等，我就直接猜了，然后后面的依次减一楼梯递减判断

🧠 举一反三 (Pattern)

• 下次看到 "..." -> 想到 ...

---

💻 代码

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair<int,int> PII;
const int N=1e6+7;
const int mod=1e9+7;

void solve(){
    int n,x,y;
    cin>>n>>x>>y;
    x=abs(x),y=abs(y);

    string s;
    cin>>s;
    int cnt4=0,cnt8=0;
    for(int i=0;i<n;i++){
        if(s[i]=='4') cnt4++;
        else cnt8++;
    }
    if(x==0){
        if(y<=n){
            printf("YES\n");
            return ;
        }
    }
    if(y==0){
        if(x<=n){
            printf("YES\n");
            return ;
        }
    }

    if(x<=cnt8){
        if(y<=n){
            printf("YES\n");
            return ;
        }
    }else if(x<=n){
        int i=x-cnt8;
        if(y<=n-i){
            printf("YES\n");
            return ;
        }
    }
    printf("NO\n");


    return ;
}


int main(){
    int t;
    cin>>t;
    while(t--){
        solve();
    }
    return 0;
}
````





# CF 题解思路
- 操作顺序并不重要。只有子字符串中的 $\texttt{4}s$ 和 $\texttt{8}s$ 的数量才重要。
- 如果我们可以正交移动（使用 $\texttt{4}$ ）和对角移动（使用 $\texttt{8}$ ），则黑色单元是我们可以从 $(0, 0)$ 开始到达的位置。
- 带有 $\texttt{8}$ 的移动等价于带有 $\texttt{4}$ 的两个不同方向的移动。
- 操作顺序无关紧要。所以计算 $\texttt{4}s$ 和 $\texttt{8}s$ 的数量，并假设有 $a$ $\texttt{4}$ 和 $b$ $\texttt{8}s$ 。-网格对称。我们可以假设 $x, y \geq 0$ （通过使 $x := |x|$ ， $y := |y|$ ）。

- 黑色单元格是我们可以从 $(0, 0)$ 开始到达的位置，如果我们可以正交移动（使用 $\texttt{4}$ ）

和对角线（使用 $\texttt{8}$ ）。-特别是，由于 $x, y \geq 0$ ， $\texttt{4}$ 是向上或向右的步骤，而 $\texttt{8}$ 由两个步骤组成，一个向上，一个向右。

- 因此您总共有 $a+2b$ 个步骤，其中只有 $a+b$ 个步骤可以在同一方向上。

- 必要和充分条件是

-- $a+2b \geq x+y$ （您需要能够执行 $x+y$ 步骤，向上或向右，

联系 $(x, y)$ ）-- $a+b \geq \max(x, y)$ （您需要能够执行 $y$ 向上步进和 $x$ 向右步进）



# CF 题解代码
```cpp
#include <bits/stdc++.h>
using namespace std;

#define nl "\n"
#define nf endl
#define ll long long
#define pb push_back
#define _ << ' ' <<

#define INF (ll)1e18
#define mod 998244353
#define maxn 110

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    #if !ONLINE_JUDGE && !EVAL
        ifstream cin("input.txt");
        ofstream cout("output.txt");
    #endif

    ll t; cin >> t;
    while (t--) {
        ll n, x, y; cin >> n >> x >> y;
        string s; cin >> s; s = '#' + s;
        ll a = 0, b = 0;
        for (ll i = 1; i <= n; i++) {
            a += (s[i] == '4');
            b += (s[i] == '8');
        }

        x = abs(x); y = abs(y);
        if (a + 2 * b < x + y) cout << "NO" << nl;
        else if (a + b < max(x, y)) cout << "NO" << nl;
        else cout << "YES" << nl;
    }

    return 0;
}

CF 题解代码的解释

这份 CF 官方题解的思路其实非常巧妙，它是从“资源消耗”和“步数限制”两个数学角度来建模的，比找规律（几何形状）更具普适性。

我们可以把这个问题看作是：你要从 $(0,0)$ 走到 $(x,y)$（假设 $x,y \ge 0$），你手里有两种卡片：

• 卡片 '4' ($a$ 张)：可以让你的 $x+y$ 增加 1（向右走一步 或 向上走一步）。

• 卡片 '8' ($b$ 张)：可以让你的 $x+y$ 增加 2（向右上走一步，相当于同时向右和向上，即 $(+1, +1)$），或者也可以当做卡片 '4' 用（只增加 1）。

核心逻辑拆解

官方题解的判断逻辑由两个不等式组成，这两个条件必须同时满足：

1. 能量（Manhattan 距离）限制：

$$a + 2b \ge x + y$$

• 含义：你所有的卡片加起来，能提供的最大“位移总和”是否足够？

• 解释：

  • 目标点的曼哈顿距离是 $x + y$。

  • 一张 '4' 最多提供 1 个单位的距离贡献。

  • 一张 '8' 最多提供 2 个单位的距离贡献（因为它能斜着走，一步顶两步， $x+1, y+1$ 意味着 $x+y$ 增加了 2）。

  • 所以，你手里所有牌能走出的最大距离是 $1 \cdot a + 2 \cdot b$。如果这个值都小于 $x+y$，那你无论如何都走不到。

2. 物理（最大坐标）限制：

$$a + b \ge \max(x, y)$$

• 含义：你所有的操作次数（步数），是否足够支撑走到最远的那个坐标？

• 解释：

  • 无论你出 '4' 还是出 '8'，在一个回合内，你在 X 轴方向最多只能走 1 格，在 Y 轴方向最多也只能走 1 格。

  • 也就是说，经过 $n$ 次操作（$n = a+b$），你的 X 坐标绝对不可能超过 $n$，Y 坐标也绝对不可能超过 $n$。

  • 举个反例：假设你要去 $(10, 0)$，也就是 $x=10, y=0$。即使你有 5 张 '8'（$a=0, b=5$），虽然 $a+2b = 10$ 满足了第一个条件，但是你只有 5 个回合，你在 X 轴方向撑死只能走到 5，根本到不了 10。

  • 所以，总步数 $a+b$ 必须大于等于 $x$ 和 $y$ 中较大的那个。

---

举例说明

让我们用你的样例数据来验证一下这个逻辑：

样例 2：

4 5 1

4884

• 目标：$(5, 1)$，即 $x=5, y=1$。

• 资源：'4' 有 2 个 ($a=2$)，'8' 有 2 个 ($b=2$)。

• 判断：

  1. 能量判定：$a + 2b = 2 + 2(2) = 6$。目标距离 $x+y = 5+1=6$。$6 \ge 6$，满足（说明如果全用最高效率，距离是够的）。

  2. 步数判定：$a + b = 4$。最大坐标 $\max(5, 1) = 5$。$4 \ge 5$ 吗？不满足。

• 结果：NO。

• 直观理解：你只有 4 步机会，怎么可能走到坐标为 5 的地方呢？

样例 4：

7 -7 -5

4884884

• 目标：取绝对值 $(7, 5)$。

• 资源：'4' 有 3 个 ($a=3$)，'8' 有 4 个 ($b=4$)。

• 判断：

  1. 能量判定：$a + 2b = 3 + 8 = 11$。目标 $7+5=12$。$11 \ge 12$？不满足。

• 结果：NO。

• 直观理解：就算 '8' 全部当做斜着走（一步顶两步），拼了老命也只能凑出 11 的距离，到不了 12。

你的思路 vs 题解思路

• 你的思路（楼梯形状）：是几何视角。你观察到了 '8' 能够填充出一个矩形区域，然后 '4' 在边缘进行扩展。这非常直观，适合找规律做题，但在高维或者更复杂的操作下可能难以推广。

• 题解思路（不等式）：是代数/度量视角。它剥离了形状，只看“贡献值”和“上限”。

  • $x+y$ 是曼哈顿距离（L1 范数）。

  • $\max(x, y)$ 是切比雪夫距离（L∞ 范数）的一种变体。

  • 这种思路在计算几何和图论中最短路问题中非常常用：先看总量够不够，再看单项上限够不够。

总结

CF 题解的那两行代码核心就是在问：

1. 油够不够？ ( $a+2b \ge x+y$ )

2. 时间够不够？ ( $a+b \ge \max(x,y)$ )

只要这两个都够了，你就一定能通过合理分配 '4' 和 '8' 的走法到达目的地。