CSP-S 33 算法题目解析与实现分析
本文旨在对 CSP-S 33 模拟赛中的几道典型算法问题进行详细分析与解法探讨，涵盖数论、动态规划以及树上路径操作等专题。我们将深入解析每道题目的核心思路，并提供相应的C++代码实现。
问题一：因数计数与统计
本题要求统计在给定范围内，每个数作为多少个输入数字的因数。具体来说，给定一个整数 N 和 M 个整数 a1, a2, ..., aM。对于每个非负整数 k 从 0 到 M，我们需要找出有多少个整数 x（其中 1 ≤ x ≤ N）满足以下条件：在给定的 M 个数中，恰好有 k 个数以 x 为因数。
解题思路
解决此问题的主要步骤是：
- 对于每个输入数字
ai，找出其所有因数。 - 维护一个哈希表（例如
std::map），记录每个因数x在a1, ..., aM中出现的频率。也就是说，map[x]存储有多少个aj能被x整除。 - 最后，遍历哈希表，根据每个因数
x的频率map[x]，将其归类到最终结果数组result_counts中。
寻找因数最有效的方法是先对数字进行质因数分解，然后通过深度优先搜索（DFS）组合这些质因数及其幂次来生成所有因数。例如，如果一个数 P = p1e1 * p2e2 * ... * pkek，其任何因数都可以表示为 p1x1 * p2x2 * ... * pkxk，其中 0 ≤ xi ≤ ei。
对于在 1 到 N 之间但不是任何 ai 的因数的数字 x，它们的频率为 0。这部分需要单独统计，即从 N 中减去所有在哈希表中出现过的不同因数的数量。
代码实现
#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
#include <cmath>
// 使用 long long 以避免溢出
using namespace std;
// 存储质因数及其指数
struct PrimeFactor {
long long prime;
int exponent;
};
// 计算 a 的 b 次幂
long long power(long long base, int exp) {
long long res = 1;
while (exp > 0) {
if (exp & 1) res *= base;
base *= base;
exp >>= 1;
}
return res;
}
// DFS 生成所有因数
void generate_divisors(long long current_divisor_product, int prime_idx,
const vector<PrimeFactor>& factors,
long long max_N, map<long long, int>& divisor_frequency_map) {
if (current_divisor_product > max_N) {
return;
}
if (prime_idx == factors.size()) {
divisor_frequency_map[current_divisor_product]++;
return;
}
// 考虑当前质因数 p_i 的 0 到 e_i 次幂
long long p = factors[prime_idx].prime;
int e = factors[prime_idx].exponent;
for (int i = 0; i <= e; ++i) {
long long next_divisor_part = power(p, i);
if (next_divisor_part > max_N / current_divisor_product && current_divisor_product != 0) { // 防止溢出
// 如果 current_divisor_product * next_divisor_part 会超过 max_N, 停止此分支
break;
}
generate_divisors(current_divisor_product * next_divisor_part,
prime_idx + 1, factors, max_N, divisor_frequency_map);
}
}
// 处理单个数字：质因数分解并生成所有因数
void process_number_for_divisors(long long val, long long max_N, map<long long, int>& divisor_frequency_map) {
long long temp_val = val;
vector<PrimeFactor> factors;
for (long long i = 2; i * i <= temp_val; ++i) {
if (temp_val % i == 0) {
int count = 0;
while (temp_val % i == 0) {
temp_val /= i;
count++;
}
factors.push_back({i, count});
}
}
if (temp_val > 1) { // 剩余的 temp_val 是一个大质数
factors.push_back({temp_val, 1});
}
generate_divisors(1, 0, factors, max_N, divisor_frequency_map);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
long long N_limit;
int M_count;
cin >> N_limit >> M_count;
vector<long long> input_numbers(M_count);
for (int i = 0; i < M_count; ++i) {
cin >> input_numbers[i];
}
map<long long, int> global_divisor_frequencies; // key: divisor, value: count of input_numbers it divides
for (long long num_val : input_numbers) {
process_number_for_divisors(num_val, N_limit, global_divisor_frequencies);
}
vector<long long> result_counts(M_count + 1, 0); // result_counts[k] = how many x (1..N) divide k numbers
long long numbers_with_zero_divisors = N_limit;
for (auto const& [divisor, freq] : global_divisor_frequencies) {
if (divisor > N_limit) continue; // Only care about divisors up to N_limit
if (freq <= M_count) {
result_counts[freq]++;
numbers_with_zero_divisors--;
}
}
result_counts[0] += numbers_with_zero_divisors;
for (int k = 0; k <= M_count; ++k) {
cout << result_counts[k] << "\n";
}
return 0;
}
问题二：带时间限制的背包问题
给定 N 种商品，每种商品有其成本 cost、价值 value 和可购买时间 available_time。有 M 次查询，每次查询给定一个查询时间 query_T 和最大预算 max_budget，要求在 query_T 时刻及之前，以不超过 max_budget 的总成本所能获得的最大总价值是多少。
解题思路
这是一个经典的背包问题变种，引入了时间维度。由于商品价值和时间的范围相对较小，而成本可能较大，我们可以使用动态规划，并对 DP 状态进行转换。
我们定义 min_cost_dp_table[t][v] 为在时间 t 之前，获得至少 v 总价值所需的最小成本。初始时，所有 min_cost_dp_table[t][v] 设为无穷大，min_cost_dp_table[0][0] = 0。
具体步骤如下：
- 将所有商品按其
available_time升序排序。 - 按时间
t顺序迭代（从1到最大时间，本题为300）。- 对于每个时间
t，首先继承前一时刻t-1的所有 DP 状态：min_cost_dp_table[t][v] = min_cost_dp_table[t-1][v]。这意味着在时间t时，所有在t-1之前可以获得的状态仍然有效。 - 然后，处理所有
available_time等于t的新商品。对于每个新商品，更新 DP 状态：min_cost_dp_table[t][v] = min(min_cost_dp_table[t][v], min_cost_dp_table[t][v - current_item_value] + current_item_cost)。这里需要注意，为了确保每个商品只使用一次（0/1 背包），对于价值v的迭代应从大到小。
- 对于每个时间
- 在所有时间迭代完成后，对每个
t，进行一次"前缀最小值"处理：min_cost_dp_table[t][v] = min(min_cost_dp_table[t][v], min_cost_dp_table[t][v+1])。这样，min_cost_dp_table[t][v]就能表示获得至少v价值的最小成本。 - 对于每个查询
(query_T, max_budget)，在min_cost_dp_table[query_T]这一行中，使用二分查找（upper_bound）找出在不超过max_budget成本下能达到的最大价值。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <cstring> // For memset
using namespace std;
const int MAX_TIME = 300;
const int MAX_VALUE_SUM = 90000;
const int INF = 0x3f3f3f3f; // 表示无穷大成本
struct Item {
int cost, value, available_time;
};
// 比较函数，用于按时间对商品排序
bool compareItemsByTime(const Item& a, const Item& b) {
return a.available_time < b.available_time;
}
// dp[t][v] 表示在时间 t 及之前，获得价值 v 所需的最小成本
int min_cost_dp_table[MAX_TIME + 1][MAX_VALUE_SUM + 1];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int num_items, num_queries;
cin >> num_items >> num_queries;
vector<Item> items(num_items);
for (int i = 0; i < num_items; ++i) {
cin >> items[i].cost >> items[i].value >> items[i].available_time;
}
sort(items.begin(), items.end(), compareItemsByTime);
// 初始化DP表
memset(min_cost_dp_table, INF, sizeof(min_cost_dp_table));
min_cost_dp_table[0][0] = 0; // 0成本获得0价值
int item_idx = 0; // 当前待处理的商品索引
for (int t = 1; t <= MAX_TIME; ++t) {
// 继承前一时刻的状态
for (int v = 0; v <= MAX_VALUE_SUM; ++v) {
min_cost_dp_table[t][v] = min_cost_dp_table[t-1][v];
}
// 处理所有在当前时间 t 可用的新商品
while (item_idx < num_items && items[item_idx].available_time == t) {
int current_cost = items[item_idx].cost;
int current_value = items[item_idx].value;
// 0/1 背包更新，价值从高到低遍历
for (int v = MAX_VALUE_SUM; v >= current_value; --v) {
if (min_cost_dp_table[t][v - current_value] != INF) {
min_cost_dp_table[t][v] = min(min_cost_dp_table[t][v],
min_cost_dp_table[t][v - current_value] + current_cost);
}
}
item_idx++;
}
}
// 后处理：dp[t][v] 变为获得"至少" v 价值的最小成本
for (int t = 0; t <= MAX_TIME; ++t) {
for (int v = MAX_VALUE_SUM - 1; v >= 0; --v) {
min_cost_dp_table[t][v] = min(min_cost_dp_table[t][v], min_cost_dp_table[t][v+1]);
}
}
for (int q = 0; q < num_queries; ++q) {
int query_T, max_budget;
cin >> query_T >> max_budget;
// 在dp[query_T]行中二分查找第一个成本大于max_budget的价值
// 这样它的前一个元素就是不超过max_budget的最大价值
auto it = upper_bound(min_cost_dp_table[query_T],
min_cost_dp_table[query_T] + MAX_VALUE_SUM + 1,
max_budget);
// it 指向第一个 > max_budget 的位置，所以 (it - 1) 指向 <= max_budget 的最大价值对应的位置
// 如果 it 是 dp[query_T] 的开始，说明没有价值能达到，或者说0价值是唯一选择。
cout << (it - min_cost_dp_table[query_T]) - 1 << "\n";
}
return 0;
}
问题三：树上边定向与计数
给定一棵包含 N 个节点和 N-1 条边的树。我们需要为每条边指定一个方向，使得满足 M 个特定的方向限制。每个限制形如 (u, v)，表示从节点 u 到节点 v 的路径上的所有边都必须指向同一方向，或者说，这条路径上的所有节点相对于 u 或 v 呈现出单向序列关系。最终，求出满足所有限制的边定向方案数。如果不存在合法方案，输出 0。
解题思路
此问题可以建模为带方向的2-SAT问题，并在树上结合重链剖分（Heavy-Light Decomposition, HLD）和并查集（Disjoint Set Union, DSU）来解决。
-
建模为2-SAT问题：
每个节点
i可以有两种状态：'向上'或'向下'（相对于其父节点）。我们将节点i表示为变量i，其相反状态表示为i+N。- 如果边
(u, v)被定向为同向，则表示u和v状态相同。在 DSU 中合并(u, v)和(u+N, v+N)。 - 如果边
(u, v)被定向为异向，则表示u和v状态相反。在 DSU 中合并(u, v+N)和(u+N, v)。 - 如果任何时候发现
find(i) == find(i+N)，则说明存在矛盾，无解。
- 如果边
-
重链剖分：
用于高效处理树上路径查询。通过两次深度优先搜索（DFS），我们可以：
- 计算每个节点的深度
dep、子树大小siz、父节点fa和重子节点son。 - 将树分解为多条重链，记录每个节点所属的重链头
top，以及它在 HLD 序中的位置id。
- 计算每个节点的深度
-
LCA与路径处理：
对于每个查询
(u, v)：- 找出
u和v的最近公共祖先lca。 - 如果
u, v分别位于lca的不同子树中，则u到v的路径必须经过lca。此时，路径上的边方向必须是u走向lca，然后lca走向v，或者u远离lca，lca远离v。这要求u和v相对于lca的方向必须相反。因此，合并(u, v+N)和(u+N, v)。 - 然后，遍历从
u到lca的路径（不包含lca）和从v到lca的路径（不包含lca）。对于路径上的每一条边(x, fa[x])，由于路径上的所有边必须同向，我们合并(x, fa[x])和(x+N, fa[x]+N)。这可以通过线段树在 HLD 序上进行区间更新来完成。线段树节点存储一个标志位，指示该区间内的边是否已被处理。
- 找出
-
计数方案：
所有限制处理完毕后，遍历 DSU 结构。如果任何节点
i出现find(i) == find(i+N)，则输出0。否则，计算 DSU 中独立成分的数量。在2N个节点（i和i+N）的 DSU 结构中，如果有C个连通分量，且每个i和i+N都在不同的分量中，则方案数为2^(C/2)。 本题中，C = 2N - (tot)，其中 `tot` 是所有非根节点的数量 (即 `2N` 减去连通分量数)。因此，答案是 `2^(N - tot/2)`。结合题意中的n-1初始自由边，可以理解为(n-1)减去 `tot/2` (被固定方向的边数)。
代码实现
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric> // For iota
using namespace std;
const int MOD = 1e9 + 7;
const int MAX_NODES = 3e5 + 10; // N 和 N+N 可能达到 2*N
// DSU (Disjoint Set Union)
vector<int> parent_dsu;
int find_set(int v) {
if (v == parent_dsu[v])
return v;
return parent_dsu[v] = find_set(parent_dsu[v]);
}
void unite_sets(int a, int b) {
a = find_set(a);
b = find_set(b);
if (a != b) {
parent_dsu[b] = a;
}
}
// HLD (Heavy-Light Decomposition)
vector<vector<int>> adj_list;
vector<int> depth, subtree_size, tree_parent, heavy_child;
vector<int> chain_head, hld_pos, hld_node_map; // chain_head: 重链头, hld_pos: HLD序中的位置, hld_node_map: HLD序位置到节点
int hld_time;
void dfs1(int u, int p, int d) {
depth[u] = d;
tree_parent[u] = p;
subtree_size[u] = 1;
heavy_child[u] = 0; // Initialize heavy_child to 0
int max_child_size = 0;
for (int v : adj_list[u]) {
if (v == p) continue;
dfs1(v, u, d + 1);
subtree_size[u] += subtree_size[v];
if (subtree_size[v] > max_child_size) {
max_child_size = subtree_size[v];
heavy_child[u] = v;
}
}
}
void dfs2(int u, int head) {
chain_head[u] = head;
hld_pos[u] = ++hld_time;
hld_node_map[hld_time] = u;
if (heavy_child[u]) { // 先处理重子节点
dfs2(heavy_child[u], head);
}
for (int v : adj_list[u]) { // 再处理轻子节点
if (v == tree_parent[u] || v == heavy_child[u]) continue;
dfs2(v, v); // 轻子节点开启一条新重链
}
}
// 线段树用于标记路径上的边
struct SegmentTreeNode {
int left_bound, right_bound;
bool marked; // 表示该区间内的边是否已处理 (即被固定为同向)
};
vector<SegmentTreeNode> seg_tree_nodes;
int N_nodes_for_tree; // N for tree building
void build_segment_tree(int node_idx, int l, int r) {
seg_tree_nodes[node_idx].left_bound = l;
seg_tree_nodes[node_idx].right_bound = r;
seg_tree_nodes[node_idx].marked = false; // Initially no edges are marked
if (l == r) return;
int mid = (l + r) / 2;
build_segment_tree(node_idx * 2, l, mid);
build_segment_tree(node_idx * 2 + 1, mid + 1, r);
}
// 将路径上的边标记为同向
// update_segment_tree(1, hld_pos[top[u]] + (tree_parent[top[u]] == lca_node), hld_pos[u], N)
void update_segment_tree(int node_idx, int query_l, int query_r, int N_val) {
if (query_l > query_r) return;
if (seg_tree_nodes[node_idx].marked) return; // 区间已标记，无需重复处理
int current_l = seg_tree_nodes[node_idx].left_bound;
int current_r = seg_tree_nodes[node_idx].right_bound;
if (query_l <= current_l && current_r <= query_r) {
// 当前节点区间完全被查询区间覆盖，将其中所有边标记为同向
// 每条 HLD 序上的节点 i 对应的边是 (hld_node_map[i], tree_parent[hld_node_map[i]])
for (int i = current_l; i <= current_r; ++i) {
int current_node = hld_node_map[i];
int parent_node = tree_parent[current_node];
if (parent_node != 0) { // 根节点没有父边
unite_sets(current_node, parent_node);
unite_sets(current_node + N_val, parent_node + N_val);
}
}
seg_tree_nodes[node_idx].marked = true;
return;
}
// 部分覆盖或不覆盖，递归处理子节点
int mid = (current_l + current_r) / 2;
if (query_l <= mid) update_segment_tree(node_idx * 2, query_l, query_r, N_val);
if (query_r > mid) update_segment_tree(node_idx * 2 + 1, query_l, query_r, N_val);
seg_tree_nodes[node_idx].marked = seg_tree_nodes[node_idx * 2].marked && seg_tree_nodes[node_idx * 2 + 1].marked;
}
// 计算 a 的 b 次幂对 MOD 取模
long long power_mod(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp & 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp >>= 1;
}
return res;
}
int get_lca(int u, int v) {
while (chain_head[u] != chain_head[v]) {
if (depth[chain_head[u]] < depth[chain_head[v]]) {
swap(u, v);
}
u = tree_parent[chain_head[u]];
}
return depth[u] < depth[v] ? u : v;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N_nodes, M_queries;
cin >> N_nodes >> M_queries;
N_nodes_for_tree = N_nodes;
// DSU 初始化 2*N 个节点 (N for actual nodes, N for their complement/opposite state)
parent_dsu.resize(2 * N_nodes + 1);
iota(parent_dsu.begin(), parent_dsu.end(), 0); // parent_dsu[i] = i
// HLD 结构初始化
adj_list.resize(N_nodes + 1);
depth.resize(N_nodes + 1);
subtree_size.resize(N_nodes + 1);
tree_parent.resize(N_nodes + 1);
heavy_child.resize(N_nodes + 1);
chain_head.resize(N_nodes + 1);
hld_pos.resize(N_nodes + 1);
hld_node_map.resize(N_nodes + 1);
for (int i = 0; i < N_nodes - 1; ++i) {
int u, v;
cin >> u >> v;
adj_list[u].push_back(v);
adj_list[v].push_back(u);
}
dfs1(1, 0, 1); // 从节点1开始DFS，深度为1
dfs2(1, 1);
// 线段树初始化
seg_tree_nodes.resize(4 * (N_nodes + 1)); // 4*N for segment tree
build_segment_tree(1, 1, N_nodes);
for (int i = 0; i < M_queries; ++i) {
int u, v;
cin >> u >> v;
int lca_node = get_lca(u, v);
// 如果 u 和 v 在 LCA 的不同子树中，则 u 到 v 的路径要求 u 和 v 方向相反
if (u != lca_node && v != lca_node) {
unite_sets(u, v + N_nodes);
unite_sets(u + N_nodes, v);
}
// 处理从 u 到 LCA 的路径
while (chain_head[u] != chain_head[lca_node]) {
// update range for path segment.
// If tree_parent[chain_head[u]] is lca_node, we should exclude the edge (chain_head[u], tree_parent[chain_head[u]])
// because it is handled by the overall merge for (u,v) path.
// The condition (tree_parent[chain_head[u]] == lca_node) is actually for the specific implementation.
// In a typical HLD, for a path from u to lca, we mark segments from id[top[u]] to id[u]
// and then move u to parent[top[u]].
update_segment_tree(1, hld_pos[chain_head[u]], hld_pos[u], N_nodes);
u = tree_parent[chain_head[u]];
}
// 处理 u 到 LCA 路径上的剩余部分
if (u != lca_node) { // if u is not lca_node itself
update_segment_tree(1, hld_pos[lca_node] + 1, hld_pos[u], N_nodes);
}
// 处理从 v 到 LCA 的路径
while (chain_head[v] != chain_head[lca_node]) {
update_segment_tree(1, hld_pos[chain_head[v]], hld_pos[v], N_nodes);
v = tree_parent[chain_head[v]];
}
// 处理 v 到 LCA 路径上的剩余部分
if (v != lca_node) { // if v is not lca_node itself
update_segment_tree(1, hld_pos[lca_node] + 1, hld_pos[v], N_nodes);
}
}
// 检查矛盾并计算方案数
long long num_fixed_edges = 0; // 记录有多少条边被"固定"了方向
for (int i = 1; i <= N_nodes; ++i) {
// 如果 find_set(i) == find_set(i + N_nodes)，则表示 i 必须同时处于两种矛盾状态，无解
if (find_set(i) == find_set(i + N_nodes)) {
cout << 0 << "\n";
return 0;
}
// 统计有多少对 (i, i+N) 的代表节点被合并，每合并一对 (i,j) 和 (i+N,j+N)
// 或 (i,j+N) 和 (i+N,j) 都相当于固定了一条边的方向
// 这里通过统计有多少节点不是其自身的 DSU 代表来计算，
// 每个成功的 unite_sets 操作会减少一个独立分量
// (i != find_set(i)) + (i + N_nodes != find_set(i + N_nodes))
// 这表示 DSU 中有多少个节点不是其所在集合的根。
// 总非根节点数 / 2 得到的是有效合并的次数，即固定方向的边数。
// 假设每个 union 操作只涉及两个节点，且是(A,B)和(A+N,B+N)或(A,B+N)和(A+N,B)。
// 那么每个逻辑上的边方向固定会对应2次find_set/unite_sets操作 (即2个节点被连接)。
// total_non_root_nodes 实际上是 2*N - num_components。
// (2*N - num_components)/2 = N - num_components/2
// num_fixed_edges += (i != find_set(i)) + (i + N_nodes != find_set(i + N_nodes));
}
// 重新计算自由度
int independent_components = 0;
for (int i = 1; i <= N_nodes; ++i) {
// 遍历所有节点 i，如果 i 是某个集合的代表，且 i+N 也在不同的集合中，
// 并且 i+N 所属的集合的代表也不是 i，则这是一个独立的自由选择对
if (find_set(i) == i && find_set(i + N_nodes) == i + N_nodes) {
// If i and i+N_nodes are both roots, and not connected, then it is a free choice.
// This doesn't quite match the N-1 - (tot >> 1) formula directly.
// The number of total components is counted from 1 to 2N.
// For each component root R, if it is smaller than or equal to N_nodes, it represents a free choice.
// total_components_count = 0;
// for (int k=1; k<=2*N_nodes; ++k) if (find_set(k)==k) total_components_count++;
// The exponent is total_components_count / 2.
// This can be simplified. Each edge has 2 directions.
// N-1 edges initially. Each constraint reduces freedom.
// The number of remaining free choices is N_nodes - (number of effective unions).
// (2*N - tot) / 2 is the correct exponent. Here, tot is number of elements not equal to their representative.
// The original code's "tot" definition and usage `n - 1 - (tot >> 1)` points to `(tot >> 1)`
// being the count of edges whose directions are fixed.
// Let's count roots for i and i+N separately.
if (find_set(i) == i) independent_components++;
if (find_set(i + N_nodes) == i + N_nodes) independent_components++;
}
}
// The actual exponent is (total number of connected components for 2N nodes) / 2
// Each (i, i+N) pair forms two 'nodes' in the DSU.
// If find_set(i) != find_set(i+N) for all i, then we have 2-SAT consistency.
// The number of free choices (each yielding 2 configurations) is `C/2` where C is number of DSU components.
// DSU components calculation:
int total_components = 0;
for(int k = 1; k <= 2 * N_nodes; ++k) {
if(parent_dsu[k] == k) {
total_components++;
}
}
long long exponent = total_components / 2;
// The original formula `n - 1 - (tot >> 1)` could be `(N_nodes - 1)` initial free edges,
// minus `(num_fixed_edges/2)` for those that become fixed by constraints.
// This implies `exponent = N_nodes - 1 - (num_fixed_edges / 2)` where num_fixed_edges is
// the count of parent_dsu changes that took place in this context.
// Let's use the standard method: (total components) / 2
cout << power_mod(2, exponent) << "\n";
return 0;
}
