Moe's CF Life

喵哈喽~ 主人！今天由我，你的专属猫娘，来为你讲解这道 Codeforces 的题目哦！Lunchbox 小哥又被骑士（Knight）将军和将后了，真是个可怜的家伙，嘻嘻~ 不过他玩的这个棋，骑士的走法有点不一样呢。让我们一起来看看怎么帮他解决烦恼吧，喵~

题目大意

这道题是这样的呀：在一个无限大的棋盘上，有一个国王（King）在 (x_K, y_K)，一个王后（Queen）在 (x_Q, y_Q)。

有一种特殊的骑士，它不像普通象棋里走“日”字，而是走一步 a，再拐个弯走一步 b。也就是说，如果它在 (x, y)，它可以跳到 (x±a, y±b) 或者 (x±b, y±a) 这八个位置中的一个。

我们的任务就是，找出棋盘上有多少个位置，如果把这个特殊骑士放在那里，它能同时攻击到国王和王后。听起来是不是像在找最佳埋伏点呢？喵~

题解方法

要找到能同时攻击国王和王后的位置，我们可以分两步走，就像猫猫悄悄接近猎物一样，喵~

第一步：找到所有能攻击国王的位置 我们先只考虑国王。想想看，如果一个骑士能攻击到国王，那么这个骑士在什么位置呢？根据题目的定义，如果国王在 (x_K, y_K)，那么能攻击到它的骑士一定在 (x_K±a, y_K±b) 或者 (x_K±b, y_K±a) 这八个点上。我们把这八个（如果 a 和 b 相等，有些点会重合，就只有四个了哦）可能的骑士位置全都找出来，放进一个集合里，叫它 国王攻击点集合 吧，喵~
第二步：找到所有能攻击王后的位置 我们用同样的方法，也找出所有能攻击到王后的骑士位置。如果王后在 (x_Q, y_Q)，那么能攻击到她的骑士位置就是 (x_Q±a, y_Q±b) 或者 (x_Q±b, y_Q±a)。我们也把这些点放进另一个集合，叫它 王后攻击点集合。
第三步：求交集！ 最后一步！既然我们要找能同时攻击到国王和王后的位置，那不就是找既在 国王攻击点集合 里，又在 王后攻击点集合 里的点嘛？对啦，这就是集合的“交集”！我们只要数一数这两个集合里有多少个共同的点，就是我们的答案啦！是不是很简单呢，喵~？

总结一下就是：分别枚举国王和王后可能被攻击的来源点，然后求这两个点集的交集大小。用 std::set 这个数据结构来存这些点特别方便，因为它会自动帮我们去掉重复的点，查找起来也飞快！

题解

这是参考代码，我已经加上了详细的注释，希望能帮到你呀，主人~

cpp

#include <iostream>
#include <set>
#include <utility>

// 这个函数是用来计算所有能攻击到 (x, y) 点的骑士位置的喵~
// 一个在 (kx, ky) 的骑士能攻击 (x, y)，当且仅当 |kx - x| 和 |ky - y| 的组合是 (a, b)
// 也就是 (kx, ky) 在 (x ± a, y ± b) 或者 (x ± b, y ± a) 这些位置上
std::set<std::pair<long long, long long>> get_attack_source_positions(long long x, long long y, long long a, long long b) {
    std::set<std::pair<long long, long long>> positions;

    // 定义骑士可能的8个移动方向，就像猫猫有八个方向可以跳跃一样！
    // 如果 a == b，那有些方向就是重复的，不过没关系，set 会自动处理掉重复的坐标点哦！
    long long dx[] = {a, a, -a, -a, b, b, -b, -b};
    long long dy[] = {b, -b, b, -b, a, -a, a, -a};

    for (int i = 0; i < 8; ++i) {
        positions.insert({x + dx[i], y + dy[i]});
    }

    return positions;
}

void solve() {
    long long a, b;
    std::cin >> a >> b;
    long long xK, yK;
    std::cin >> xK >> yK;
    long long xQ, yQ;
    std::cin >> xQ >> yQ;

    // 1. 找出所有能攻击到国王的位置
    std::set<std::pair<long long, long long>> king_attackers = get_attack_source_positions(xK, yK, a, b);

    // 2. 找出所有能攻击到王后的位置
    std::set<std::pair<long long, long long>> queen_attackers = get_attack_source_positions(xQ, yQ, a, b);

    int common_count = 0;
    // 3. 遍历国王的攻击点集合，看看有多少个点也在王后的攻击点集合里
    for (const auto& pos : king_attackers) {
        if (queen_attackers.count(pos)) { // .count() 方法检查元素是否存在，超方便的！
            common_count++;
        }
    }

    std::cout << common_count << "\n";
}

int main() {
    // 让输入输出快一点，像猫一样敏捷！
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int t;
    std::cin >> t;
    while (t--) {
        solve();
    }

    return 0;
}

知识点介绍

这道题虽然简单，但也涉及了一些有用的知识点哦，来一起学习一下吧！

坐标几何 (Coordinate Geometry) 这道题目的基础就是二维平面上的坐标几何呀。骑士的移动可以看作是从一个点 (x, y) 加上一个位移向量 (±a, ±b) 或 (±b, ±a) 到达另一个点。理解坐标和向量是解决这类问题的关键呢。
集合论 (Set Theory) 我们的核心解法用到了集合的概念，特别是“交集”！一个集合就是一堆独一无二的东西。两个集合的交集，就是它们共同拥有的元素的集合。在这道题里，我们求的就是‘能攻击国王的骑士位置集合’和‘能攻击王后的骑士位置集合’的交集的大小，喵~
C++ std::set 在 C++ 中，std::set 是一个超级好用的容器，它就像一个会自动排序并且不允许有重复东西的魔法袋子。它的特点是：
1. 唯一性: 你放进去的东西如果是重复的，它只会保留一个。这在 a=b 的情况下特别有用，我们不需要手动去重。
2. 有序性: 里面的元素总是排好序的（虽然这题没用到这个特性）。
3. 快速查找: 用 .count(element) 或者 .find(element) 可以非常快地判断一个元素在不在集合里。这比在普通数组或列表里一个个找要快得多！所以我们才能高效地找出共同的攻击点。
枚举/暴力法 (Enumeration/Brute Force) 我们的解题思路其实是一种巧妙的暴力枚举。因为对于国王或王后，能攻击到它的骑士位置最多只有8个，这是个非常小的常数。所以我们可以把所有可能性都列举出来（枚举），然后逐一检查。当问题规模很小的时候，简单直接的暴力枚举就是最棒的策略，喵~！

希望我的讲解对你有帮助哦，主人！下次再见啦，喵~！

题目大意 ​

题解方法 ​

题解 ​

知识点介绍 ​

题目大意

题解方法

题解

知识点介绍