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

一、题目解读

洛谷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。

四、代码与注释

#include <iostream>
#include <algorithm>

// 全局变量
int sum = 0;          // 总交点数之和
int p, n, r;          // p为剩余线数，n为总直线数，r为平行线数
bool A[100000] = {0}; // A[i]=1表示i个交点已存在，避免重复统计

// 递归函数：计算交点数
// p：剩余线数（当前待处理的线数）
// m：当前已计算的交点数
void plan(int p, int m) {
    // 终止条件：当剩余线数为0时，记录当前交点数
    if (p == 0) {
        if (A[m] == 0) { // 若该交点数未出现过，计入sum
            sum++;
        }
        A[m] = 1; // 标记为已存在
    } else {
        // 枚举平行线数量r（从p到1）
        for (int r = p; r >= 1; r--) {
            // 计算r条平行线与剩余p-r条线的交点数：r*(p-r)
            int newM = m + r * (p - r);
            // 递归处理剩余p-r条线
            plan(p - r, newM);
        }
    }
}

int main() {
    std::cin >> n; // 输入总直线数n
    plan(n, 0);    // 从n条线开始递归，初始交点数为0
    std::cout << sum << std::endl; // 输出总交点数之和
    return 0;
}

五、总结

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