戴夫准备在后院种植植物来抵御僵尸的进攻。 他有 n n 种植物可以选择，每种植物有两个属性：攻击力 s s 和类型 t t。其中 t = 1 t=1 表示这是一种特殊植物（如坚果墙）， t = 0 t=0 表示普通攻击植物。 为了形成有效的防御体系，戴夫需要选择最大数量的植物，使得对于每个选中的植物 i i，要么它是特殊植物（ t = 1 t=1），要么存在一个选中的植物 j j （注意可以是自己），使得当前植物的攻击力能整除那个植物的攻击力加1（即 s i ∣ ( s j + 1 ) s i ​ ∣(s j ​ +1)，表示植物间有配合效果）。 输入格式 第一行一个整数 T T 表示多组数据。 对于每组数据： 第一行一个整数 n n。 接下来一行 n n 个数，第 i i 个表示 s i s i ​ 。 接下来一行 n n 个数，第 i i 个表示 t i t i ​ 。 输出格式 对于每组数据： 输出一行一个整数，表示最多能选择的植物数量。 使用c++语言

```cpp #include <iostream> #include <vector> #include <algorithm> #include <unordered_map> using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int T; cin >> T; while (T--) { int n; cin >> n; vector<int> s(n); for (int i = 0; i < n; i++) { cin >> s[i]; } vector<int> t(n); for (int i = 0; i < n; i++) { cin >> t[i]; } // 分离普通植物和特殊植物 vector<int> normal, special; for (int i = 0; i < n; i++) { if (t[i] == 0) { normal.push_back(s[i]); } else { special.push_back(s[i]); } } // 对普通植物排序 sort(normal.begin(), normal.end()); // 统计特殊植物的数量 int specialCount = special.size(); // 使用哈希表记录每个攻击力值 unordered_map<int, bool> exists; for (int val : normal) exists[val] = true; for (int val : special) exists[val] = true; // 贪心选择普通植物 int selectedNormal = 0; for (int val : normal) { bool canSelect = false; // 检查是否存在特殊植物 if (specialCount > 0) { canSelect = true; } // 检查是否存在其他植物满足整除条件 if (!canSelect) { // 检查是否存在已选的普通植物满足条件 for (int other : normal) { if (other == val) continue; if (exists[other] && (val % (other + 1) == 0)) { canSelect = true; break; } } } // 检查是否存在特殊植物满足条件 if (!canSelect) { for (int sp : special) { if (val % (sp + 1) == 0) { canSelect = true; break; } } } if (canSelect) { selectedNormal++; // 标记当前植物已被选择 exists[val] = true; } } // 特殊植物总是可以被选择 int result = specialCount + selectedNormal; cout << result << "\n"; } return 0; } ``` 代码说明： 1. 数据结构： - 使用`vector<int>`存储普通植物和特殊植物的攻击力 - 使用`unordered_map`记录存在的植物攻击力值 2. 算法逻辑： - 特殊植物（t=1）总是可以被选择 - 普通植物需要满足条件：存在已选植物j使得`s[i] % (s[j] + 1) == 0` - 采用贪心策略选择普通植物 3. 优化： - 对普通植物排序便于处理 - 使用哈希表快速检查植物是否存在 - 优先检查特殊植物是否满足条件 4. 时间复杂度： - 每组数据O(n²)最坏情况，适合n≤1000的数据规模 注意： 这是一个贪心解法，对于某些特殊测试用例可能不是最优解。如果数据规模更大或需要精确最优解，可能需要使用图论或动态规划方法。 [2026-01-19 19:20:57 | AI问答 | 773点数解答]