解题思路

n 条封闭曲线画在平面上，每两条交于 2 点，问把平面分成几个区域。

找规律（递推）：

• 1 条曲线：把平面分成 2 个区域
• 2 条曲线：4 个区域
• 每增加一条曲线，它和之前的每条曲线交 2 点，会被分成若干段，每段把原有区域一分为二

递推公式：A(1) = 2，A(n) = A(n-1) + 2(n-1)

因为第 n 条曲线与前面 n-1 条曲线各交 2 点，被分成 2(n-1) 段，多分出 2(n-1) 个区域。

举例：

• n=1：2
• n=2：2 + 2×1 = 4
• n=3：4 + 2×2 = 8

参考代码

#include <iostream>
using namespace std;

int main() {
    long long n, x;
    cin >> n;

    x = 2;  // 1 条曲线分 2 个区域
    for (long long i = 2; i <= n; i++) {
        x += 2 * (i - 1);  // 每加一条多 2(n-1) 个区域
    }

    cout << x << endl;
    return 0;
}

复杂度分析

• 时间复杂度：O(N)，递推 n 次
• 空间复杂度：O(1)