当前位置：首页 > news >正文

CCF CSP认证第4题‘校门外的树‘：用‘打表‘预处理，我拿下了100分

news 2026/5/16 10:54:00

CCF CSP认证第4题'校门外的树'：用'打表'预处理，我拿下了100分

考场上的计时器滴答作响，我盯着屏幕上的题目描述——"校门外的树"。这道看似简单的动态规划题，却让不少考生在考场上折戟沉沙。作为经历过多次CSP认证的老手，我深知这类题目往往暗藏玄机。本文将完整还原我的解题思路，从最初的困惑到灵光一现的"打表"优化，最终实现100分通过的完整过程。

1. 题目理解与初步分析

题目描述大致如下：校门外有一条长度为L的道路，两旁种有树木。每棵树都有一个美观度值，我们需要选择若干棵树进行修剪，使得最终保留的树木满足"美观"条件——即任意两棵相邻保留树木的位置编号的最大公约数为1。目标是求出所有可能的美观修剪方案数。

关键难点解析：

美观条件的转化：题目中的"美观"定义实则是数学上的互质关系
数据规模挑战：L的范围可能达到10^5级别，暴力解法必然超时
动态规划适用性：方案计数问题通常考虑DP，但状态设计需要巧妙

注意：在竞赛环境中，快速识别题目本质（这里是数论+DP的结合）比立即编码更重要

2. 核心思路：打表预处理约数关系

面对这个题目，我的第一个突破点是意识到需要预处理每个数的约数。这一步是后续动态规划的基础，也是优化时间复杂度的关键。

2.1 约数预处理实现

const int MAX_L = 1e5 + 5; vector<vector<int>> divisors(MAX_L); void preprocess() { for (int i = 1; i < MAX_L; ++i) { for (int j = i; j < MAX_L; j += i) { divisors[j].push_back(i); } } }

这段代码使用筛法预处理了1到MAX_L范围内每个数的所有约数，时间复杂度为O(L log L)，完全在可接受范围内。

2.2 为什么需要预处理？

实时计算代价高：对于每个位置，如果实时计算其约数，整体复杂度将无法承受
多次查询需求：DP过程中需要频繁查询约数信息
空间换时间：预处理后，所有约数信息O(1)可查

3. 动态规划状态设计与转移

有了约数预处理的基础，接下来就是设计动态规划的状态和转移方程。

3.1 状态定义

定义dp[i]表示考虑前i棵树时的合法方案数。我们需要找到从dp[j]转移到dp[i]的条件。

关键观察：

当选择第i棵树时，前一棵选择的树j必须满足pos[i]和pos[j]互质
这个条件可以转化为：pos[j]不能与pos[i]共享任何约数

3.2 转移方程优化

直接实现这个思路会导致O(n^2)的复杂度，对于L=1e5来说不可行。于是我想到了使用前缀和和容斥原理来优化：

vector<int> dp(L + 1, 0); vector<int> sum(L + 1, 0); dp[0] = 1; sum[0] = 1; for (int i = 1; i <= L; ++i) { dp[i] = sum[i - 1]; for (int d : divisors[i]) { if (d != i) { dp[i] -= sum_multiples[d]; } } sum[i] = sum[i - 1] + dp[i]; for (int d : divisors[i]) { sum_multiples[d] += dp[i]; } }

这个实现通过维护sum数组（前缀和）和sum_multiples数组（各约数的贡献和），将复杂度优化到了O(L log L)。

4. 边界处理与最终实现

在实际编码中，还需要注意几个关键细节：

模数处理：题目通常要求对结果取模，需要在每次运算后及时取模
初始化条件：dp[0] = 1表示空方案的基准情况
负数处理：减法操作后可能出现负数，需要加上模数再取模

完整代码框架如下：

#include <bits/stdc++.h> using namespace std; const int MOD = 1e9 + 7; const int MAX_L = 1e5 + 5; vector<vector<int>> divisors(MAX_L); vector<int> dp(MAX_L, 0); vector<int> sum(MAX_L, 0); vector<int> sum_multiples(MAX_L, 0); void preprocess() { for (int i = 1; i < MAX_L; ++i) { for (int j = i; j < MAX_L; j += i) { divisors[j].push_back(i); } } } int solve(int L) { preprocess(); dp[0] = 1; sum[0] = 1; for (int i = 1; i <= L; ++i) { dp[i] = sum[i - 1]; for (int d : divisors[i]) { if (d != i) { dp[i] = (dp[i] - sum_multiples[d] + MOD) % MOD; } } sum[i] = (sum[i - 1] + dp[i]) % MOD; for (int d : divisors[i]) { sum_multiples[d] = (sum_multiples[d] + dp[i]) % MOD; } } return dp[L]; } int main() { int L; cin >> L; cout << solve(L) << endl; return 0; }