洛谷2789题解：直线交点数的递归求解与优化（附代码详解）

一、题目解读

洛谷2789题要求计算n条直线在平面上两两相交时产生的不同交点数量。题目强调“不同”交点，需排除重复情况。解题关键在于如何高效枚举所有可能的交点组合，并避免重复计数。

二、解题思路

参考代码采用递归算法，核心思想是分组枚举平行线：将n条直线分为若干平行线组，每组内部无交点，组与组之间产生交点。通过递归搜索所有分组可能性，计算交点总数。为避免重复，使用vis数组标记已出现的交点数，仅统计未出现的值。

三、解题步骤

1. 初始化：定义vis数组标记交点数，ans记录不同交点数量。

2. 递归函数DFS：

参数now为剩余直线数，sum为当前累计交点数。

当now=0时，若sum未被标记，则新增ans并标记。

循环枚举当前平行线组直线数i（1≤i≤now），计算交点数i*(now-i)，递归处理剩余now-i条直线。

3. 主函数：输入n，初始化后调用dfs(n,0)，输出ans。

四、代码与注释

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 25; // 最大直线数
const int MAXS = 300; // 最大可能交点数

bool vis[MAXS]; // 标记已出现的交点数
int n, ans = 0;

// 递归搜索所有可能的交点数
// now: 剩余需要分配的直线数
// sum: 当前累计的交点数
void dfs(int now, int sum) {
    if (now == 0) { // 所有直线已分配完毕
        if (!vis[sum]) { // 如果这个交点数未出现过
            vis[sum] = true;
            ans++;
        }
        return;
    }
    
    // 枚举当前平行线组的直线数i
    for (int i = 1; i <= now; i++) {
        // 当前i条平行线与其他now-i条直线产生i*(now-i)个交点
        // 递归处理剩余的now-i条直线
        dfs(now - i, sum + i * (now - i));
    }
}

int main() {
    cin >> n;
    memset(vis, false, sizeof(vis));
    dfs(n, 0); // 初始状态：n条直线待分配，0个交点
    cout << ans << endl;
    return 0;
}

五、总结

本解法通过递归枚举平行线分组，结合标记数组避免重复，巧妙解决了交点计数问题。时间复杂度受递归深度和标记数组大小影响，适用于小规模数据（如n≤25）。对于更大规模问题，可探索动态规划或组合数学优化。理解递归搜索的逻辑和去重技巧，有助于解决类似组合计数问题。