洛谷P2789题解：递归算法与避免重复计算的技巧

rhsgfswg

一、题目解读

洛谷P2789题要求计算n条直线在平面上两两相交产生的交点总数。题目强调交点不重复，需考虑平行线情况。关键点在于如何高效枚举所有可能的交点组合，并排除重复结果。

二、解题思路

采用递归算法，核心思想是“分治+标记”。通过枚举每条线与其他线的平行关系，将问题分解为子问题：当前线与其他线平行或相交。为避免重复统计，使用全局数组A标记已存在的交点数，仅当新交点数未被记录时才累加。

三、解题步骤

1. 输入处理：获取总直线数n，初始化sum=0，A数组全0。

2. 递归函数plan(p,m)：

○ 终止条件：p=0时，若m未出现，更新sum并标记A[m]。

○ 递归逻辑：枚举平行线数r(p到1)，计算r条平行线与剩余p-r条线的交点数r*(p-r)，递归调用plan(p-r, m+r*(p-r))。

3. 主函数：调用plan(n,0)，输出sum。

四、代码与注释

1. #include <iostream>
   
2. #include <algorithm>
   
3. 
   
4. // 全局变量
   
5. int sum = 0;          // 总交点数之和
   
6. int p, n, r;          // p为剩余线数，n为总直线数，r为平行线数
   
7. bool A[100000] = {0}; // A[i]=1表示i个交点已存在，避免重复统计
   
8. 
   
9. // 递归函数：计算交点数
   
10. // p：剩余线数（当前待处理的线数）
    
11. // m：当前已计算的交点数
    
12. void plan(int p, int m) {
    
13.     // 终止条件：当剩余线数为0时，记录当前交点数
    
14.     if (p == 0) {
    
15.         if (A[m] == 0) { // 若该交点数未出现过，计入sum
    
16.             sum++;
    
17.         }
    
18.         A[m] = 1; // 标记为已存在
    
19.     } else {
    
20.         // 枚举平行线数量r（从p到1）
    
21.         for (int r = p; r >= 1; r--) {
    
22.             // 计算r条平行线与剩余p-r条线的交点数：r*(p-r)
    
23.             int newM = m + r * (p - r);
    
24.             // 递归处理剩余p-r条线
    
25.             plan(p - r, newM);
    
26.         }
    
27.     }
    
28. }
    
29. 
    
30. int main() {
    
31.     std::cin >> n; // 输入总直线数n
    
32.     plan(n, 0);    // 从n条线开始递归，初始交点数为0
    
33.     std::cout << sum << std::endl; // 输出总交点数之和
    
34.     return 0;
    
35. }

复制代码

五、总结

本解法巧妙利用递归将复杂枚举转化为子问题求解，结合标记数组高效去重。核心在于理解平行线产生的交点数公式r*(p-r)，并通过分治策略逐层递归。时间复杂度受递归深度影响，但通过避免重复计算显著优化结果。该思路对组合数学类问题具有参考价值。

来源：信奥之路