题解：P12677 Brooklyn Round 1 & NNOI Round 1 A - Flying Flower
时间限制这么别样的题，还真是第一次见……
题意简述
本题是一个博弈论问题，模拟飞花令游戏的数学版本。游戏规则如下：
- 给定质数
k （若k 非质数则直接判定小Z获胜）。 - 小 X 和小 Z 分别拥有序列
a （长度n ）和b （长度m ）。 - 小 X 先手，从
a 中选择一个能被k 整除的数。 - 随后双方轮流选择，每次选择的数必须大于对方上一轮选择的数，且必须能被
k 整除。 - 无法选择数的一方失败。
对于
解题思路
我们可以使用线性筛法预处理
为每个质数
对于每次询问：
- 若
k 不是质数，输出Z。 - 若
k 是质数，但对应的列表为空（即序列a 和b 中均无能被k 整除的数），则小 X 无法开局，输出Z。 - 否则，对列表中的数按值降序排序，并按数值分组处理。
博弈状态计算：
-
从大到小处理每个数值的组：
- 记录当前组内是否存在
a 类数（hasA）和b 类数（hasB）。 - 根据大于当前数值的组中是否存在必败态，计算当前组的必败态。
- 更新全局状态（
has_fail_A和has_fail_B），表示当前及更大的数中是否存在a 类或b 类必败节点。
- 记录当前组内是否存在
-
若最终
has_fail_A为真，则小 X 存在必胜策略（输出X），否则小 Z 获胜（输出Z）。
Code
不用vector代码就爆了，不知道为什么。
#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。
-
筛法求质数：
O(MAXV) ，其中MAXV = 8 \times 10^6 。 -
构建质数对应的列表：对于每个数
x ，分解其质因子的时间复杂度为O(\log x) ，总时间复杂度为O((n + m) \log \max(a_i, b_i)) ，其中n 和m 分别为序列a 和b 的长度，\max(a_i, b_i) \leq 8 \times 10^6 。 -
处理每个询问：
- 质数判断
O(1) （因为已经筛好了，直接查表）。 - 排序列表
O(s_k \log s_k) ，其中s_k 为质数k 对应的列表大小。 - 扫描列表
O(s_k) 。 - 处理询问的总时间复杂度：
\sum_{k \text{为质数}} O(s_k \log s_k) （对所有质数k ，处理其对应的列表s_k 的时间复杂度的总和。）
- 质数判断
-
得出结论：总时间复杂度为：
O(MAXV + (n + m) \log \max(a_i, b_i) + \sum_{k \text{为质数}} s_k \log s_k) 其中
MAXV = 8 \times 10^6 ，s_k 为质数k 对应的列表大小。但实际中s_k 不会总是n + m ，因此均摊复杂度会更优。