洛谷P2789题解：DFS解决直线交点数问题

一、问题描述

给定n条直线，其中可能存在平行关系，求这些直线所有可能的交点数。需要计算不同的交点数有多少种情况。

二、算法核心思想

本解决方案采用深度优先搜索(DFS)算法：

1. 将直线分组，每组中的直线互相平行

2. 计算不同分组方式产生的交点数

3. 使用数组记录已出现的交点数

4. 最终统计不同的交点数

三、完整代码实现（带详细注释）

#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;
}

四、算法分步解析

1. 数据结构准备：

• 定义最大直线数和交点数常量

• 使用vis数组标记已出现的交点数

• 定义全局变量n和ans

2. DFS函数实现：

• 基线条件：所有直线分配完毕时记录交点数

• 递归过程：枚举平行线组的大小

• 交点计算：平行线组与其他直线的交点数公式

3. 主函数流程：

• 输入直线数n

• 初始化标记数组

• 调用DFS函数开始搜索

• 输出结果

五、常见误区与调试技巧

1. 忘记初始化标记数组

2. 递归终止条件错误

3. 交点计算公式错误

4. 数组大小设置不足