洛谷题单指南-数学基础问题-P2789 直线交点数

原题链接：https://www.luogu.com.cn/problem/P2789

题意解读：n条直线可以形成不同交点数的方案数。

解题思路：

对于n = 1、2、3、4的情况进行模拟：

n = 1时，有1种不同的交点数

n = 2时，有2种不同的交点数

n = 3时，有3种不同的交点数

n = 4时，有5种不同的交点数

对n = 4的情况，分情况讨论：

如果有4条直线平行，交点数：平行线数 * 剩余线数 = 4 * (4 - 4) = 0

如果有3条直线平行，剩余1条直线与3条平行线的交点数：平行线数 * 剩余线数 = 3 * (4 - 3) = 3

如果有2条直线平行，剩余2条直线与2条平行线的交点数：平行线数 * 剩余线数 = 2 * (4 - 2) = 2，剩余2条直线之间的交点数可能是0或者1，回到了2的情况

如果有1条直线平行（所有4条都不平行），剩余3条直线与1条平行线的交点数：平行线数 * 剩余线数 = 1 * (4 - 1) = 3

核心思路是枚举不同直线条数下可以形成多少种交点数，

设f(n, x)表示剩余n条直线，累计已有x个交点

仍以n = 4为例来演示如何枚举

- f(4, 0)表示剩余4条直线，已有0个交点

- 当有1条直线平行，剩下3条直线与之产生1 * (4-1) = 3个交点，表示为f(3, 3 + 0)

  - 对f(3, 3)继续处理

  - 当有1条直线平行，剩下2条直线与之产生1 * (3-1) = 2个交点，表示为f(2, 2 + 3)

    - 对f(2, 5)继续处理

    - 当有1条直线平行，剩余1条直线与之产生1 * (2-1) = 1个交点，表示为f(1, 1 + 5)

      - 对f(1, 6)继续处理

      - 当有1条直线平行，剩余0条直线与之产生1 * (1 - 1) = 0个交点，表示为f(0, 0 + 6)

    - 当有2条直线平行，剩余0条直线与之产生2 * (2-2) = 0个交点，表示为f(0, 0 + 5)

  - 当有2条直线平行，剩下1条直线与之产生2 * (3-2) = 2个交点，表示为f(1, 2 + 3)

    - 对f(1, 5)继续处理

    - 当有1条直线平行，剩余0条直线与之产生1 * (1 - 1) = 0个交点，表示为f(0, 0 + 5)

  - 当有3条直线平行，剩余0条直线与之产生3 * (3-3) = 0个交点，表示为f(0, 0 + 3)

- 当有2条直线平行，剩余2条直线与之产生2 * (4-2) = 2个交点，表示为f(2, 2 + 0)

  - 对f(2, 2)继续处理

  - 当有1条直线平行，剩余1条直线与之产生1 * (2-1) = 1个交点，表示为f(1, 1 + 2)

    - 对f(1, 3)继续处理

    - 当有1条直线平行，剩余0条直线与之产生1 * (1-1) = 0个交点，表示为f(0, 0 + 3)

  - 当有2条直线平行，剩余0条直线与之产生2 * (2-2) = 0个交点，表示为f(0, 0 + 2)

- 当有3条直线平行，剩余1条直线与之产生3 * (4-3) = 3个交点，表示为f(1, 3 + 0)

- 当有4条直线平行，剩余0条直线与之产生0 * (4 - 4) = 0个交点，表示为f(0, 0 + 0)

可以看出，对于f(n, x)的处理是一个递归的过程，当n == 0的时候，x的值就是一个可能的交点数，有可能重复，通过hash进行记录即可，最后统计不同交点数的个数。

hash数组的大小开多大？也就是最多有多少个交点？

以n条直线为例，

第1条线开始，最多有0个交点

第2条线与前1条线最多有1个交点

第3条线与前2条线最多有2个交点

第n条线与前n-1条线最多有n-1个交点

因此，总交点数最多有0+1+2+......+n-1 = n * (n-1) / 2

n最多是25，交点数最多25*24/2 = 300。

100分代码：

#include <bits/stdc++.h>
using namespace std;

int n, ans;
bool h[500];

//剩余n条直线，累计已有x个交点
void f(int n, int x)
{
    if(n == 0) h[x] = true;
    for(int i = 1; i <= n; i++) //枚举i条直线平行的情况
    {
        f(n - i, i * (n - i) + x); //当有i条直线平行，考虑剩余n - i条直线，累计已有i * (n - i) + x个交点的情况
    }
}

int main()
{
    cin >> n;
    f(n, 0);
    for(int i = 0; i <= 500; i++)
    {
        if(h[i]) ans++;
    }
    cout << ans;
    return 0;
}