专栏文章

题解：P12677 Brooklyn Round 1 & NNOI Round 1 A - Flying Flower

CCleverSea
P12677题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mioycbt1
此快照首次捕获于
2025/12/03 03:09
3 个月前
此快照最后确认于
2025/12/03 03:09
3 个月前
查看原文
时间限制这么别样的题，还真是第一次见……

题意简述

本题是一个博弈论问题，模拟飞花令游戏的数学版本。游戏规则如下：
  • 给定质数 kk（若 kk 非质数则直接判定小Z获胜）。
  • 小 X 和小 Z 分别拥有序列 aa（长度 nn）和 bb（长度 mm）。
  • 小 X 先手，从 aa 中选择一个能被 kk 整除的数。
  • 随后双方轮流选择，每次选择的数必须大于对方上一轮选择的数，且必须能被 kk 整除。
  • 无法选择数的一方失败。
对于 qq 次询问，每个询问给出一个 kk，判断在双方均采用最优策略时，小 X（先手）是否能获胜。

解题思路

我们可以使用线性筛法预处理 11 到 8×1068\times 10^6 的所有质数，并记录每个数的最小质因子。
为每个质数 pp 构建一个列表，存储序列 aa 和 bb 中能被 pp 整除的数及其类别（aa 中的数标记为 00，bb 中的数标记为 11）。

对于每次询问：

  • 若 kk 不是质数，输出 Z。
  • 若 kk 是质数，但对应的列表为空（即序列 aa 和 bb 中均无能被 kk 整除的数），则小 X 无法开局，输出 Z。
  • 否则，对列表中的数按值降序排序，并按数值分组处理。

博弈状态计算：

  • 从大到小处理每个数值的组：
    • 记录当前组内是否存在 aa 类数（hasA）和 bb 类数（hasB）。
    • 根据大于当前数值的组中是否存在必败态，计算当前组的必败态。
    • 更新全局状态（has_fail_A 和 has_fail_B），表示当前及更大的数中是否存在 aa 类或 bb 类必败节点。
  • 若最终 has_fail_A 为真，则小 X 存在必胜策略（输出 X），否则小 Z 获胜（输出 Z）。

CodeCode

不用vector代码就爆了，不知道为什么。
CPP
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 8e6 + 10;

vector<int> primes;
int minn[N + 1];
bool is_prime[N + 1];

// 线性筛法预处理质数及最小质因子
void sieve() {
    for (int i = 0; i <= N; i++) {
        is_prime[i] = true;
        minn[i] = 0;
    }
    is_prime[0] = is_prime[1] = false;
    for (int i = 2; i <= N; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            minn[i] = i;
        }
        for (int j = 0; j < primes.size(); j++) {
            int p = primes[j];
            if (i * p > N) break;
            is_prime[i * p] = false;
            minn[i * p] = p;
            if (i % p == 0) break;
        }
    }
}

// 存储每个质数对应的列表：存储序列中能被该质数整除的数及其类别（0：来自a，1：来自b）
vector<pair<int, int>> lists[N + 1];
// 缓存结果：'X' 或 'Z'，初始化为 -1 表示未计算
char res[N + 1];

int main() {
    sieve(); // 筛法预处理
    int n, m, q;
    scanf("%d %d %d", &n, &m, &q);
    vector<int> a(n);
    vector<int> b(m);
    // 读入序列 a
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
    }
    // 读入序列 b
    for (int i = 0; i < m; i++) {
        scanf("%d", &b[i]);
    }
    // 初始化缓存
    memset(res, -1, sizeof(res));
    // 预处理序列 a：分解每个数的质因子，并加入对应质数的列表
    for (int i = 0; i < n; i++) {
        int x = a[i];
        if (x == 1) continue; // 1 没有质因子
        vector<int> fac;
        int temp = x;
        // 分解质因子（去重）
        while (temp > 1) {
            int p = minn[temp];
            fac.push_back(p);
            while (temp % p == 0)
                temp /= p;
        }
        // 将数加入其每个质因子的列表，标记为 0（来自 a）
        for (int p : fac) {
            lists[p].push_back({x, 0});
        }
    }
    // 预处理序列 b：同理
    for (int i = 0; i < m; i++) {
        int x = b[i];
        if (x == 1) continue;
        vector<int> fac;
        int temp = x;
        while (temp > 1) {
            int p = minn[temp];
            fac.push_back(p);
            while (temp % p == 0)
                temp /= p;
        }
        for (int p : fac) {
            lists[p].push_back({x, 1});
        }
    }
    // 处理每个询问
    while (q--) {
        int k;
        scanf("%d", &k);
        // 若 k 超出范围或非质数，输出 'Z'
        if (k > N || !is_prime[k]) {
            printf("Z\n");
        } else {
            // 若结果已缓存，直接输出
            if (res[k] != -1) {
                printf("%c\n", res[k]);
            } else {
                // 若该质数对应的列表为空，则小X无法开局，小Z获胜
                if (lists[k].empty()) {
                    res[k] = 'Z';
                    printf("Z\n");
                } else {
                    // 获取列表并按数值降序排序
                    auto& vec = lists[k];
                    sort(vec.begin(), vec.end(), [](const pair<int, int>& x, const pair<int, int>& y) {
                        return x.first > y.first;
                    });
                    bool hfA = false; // 是否存在 A 类必败节点
                    bool hfB = false; // 是否存在 B 类必败节点
                    int i = 0;
                    int totsize = vec.size();
                    // 按数值分组处理
                    while (i < totsize) {
                        int j = i;
                        // 找到相同数值的组
                        while (j < totsize && vec[j].first == vec[i].first)
                            j++;
                        // 保存当前状态（大于当前数值的节点状态）
                        bool csfA = hfA;
                        bool csfB = hfB;
                        bool hasA = false, hasB = false;
                        // 统计组内是否有 A 类或 B 类节点
                        for (int idx = i; idx < j; idx++) {
                            if (vec[idx].second == 0)
                                hasA = true;
                            else
                                hasB = true;
                        }
                        bool gfA = false;
                        bool gfB = false;
                        // 计算 A 类节点的必败态：若存在 A 类节点且大于当前数的 B 类节点无必败态，则当前 A 类节点为必败
                        if (hasA && !csfB)
                            gfA = true;
                        // 计算 B 类节点的必败态：若存在 B 类节点且大于当前数的 A 类节点无必败态，则当前 B 类节点为必败
                        if (hasB && !csfA)
                            gfB = true;
                        // 更新全局状态
                        if (gfA)
                            hfA = true;
                        if (gfB)
                            hfB = true;
                        i = j; // 移动到下一组
                    }
                    // 若存在 A 类必败节点，小X可选择该节点使小Z面临必败，故小X获胜
                    if (hfA) {
                        res[k] = 'X';
                        printf("X\n");
                    } else {
                        res[k] = 'Z';
                        printf("Z\n");
                    }
                }
            }
        }
    }
    return 0;
}

现在，分析一下时间复杂度

这应该是我做的最复杂的时间复杂度分析了qwq。
  1. 筛法求质数：O(MAXV)O(MAXV)，其中 MAXV=8×106MAXV = 8 \times 10^6。
  2. 构建质数对应的列表：对于每个数 xx，分解其质因子的时间复杂度为 O(log⁡x)O(\log x)，总时间复杂度为 O((n+m)log⁡max⁡(ai,bi))O((n + m) \log \max(a_i, b_i))，其中 nn 和 mm 分别为序列 aa 和 bb 的长度，max⁡(ai,bi)≤8×106\max(a_i, b_i) \leq 8 \times 10^6。
  3. 处理每个询问：
    • 质数判断 O(1)O(1)（因为已经筛好了，直接查表）。
    • 排序列表 O(sklog⁡sk)O(s_k \log s_k)，其中 sks_k 为质数 kk 对应的列表大小。
    • 扫描列表 O(sk)O(s_k)。
    • 处理询问的总时间复杂度：∑k为质数O(sklog⁡sk)\sum_{k \text{为质数}} O(s_k \log s_k)（对所有质数 kk，处理其对应的列表 sks_k 的时间复杂度的总和。）
  4. 得出结论：总时间复杂度为：
    O(MAXV+(n+m)log⁡max⁡(ai,bi)+∑k为质数sklog⁡sk)O(MAXV + (n + m) \log \max(a_i, b_i) + \sum_{k \text{为质数}} s_k \log s_k)
    其中 MAXV=8×106MAXV = 8 \times 10^6，sks_k 为质数 kk 对应的列表大小。但实际中 sks_k 不会总是 n+mn + m，因此均摊复杂度会更优。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...