刷題之路-數論
洛谷P2789直線交點
傳送門
題目描述
![](https://img.laitimes.com/img/__Qf2AjLwojIjJCLyojI0JCLiAzNfRHLGZkRGZkRfJ3bs92YsYTMfVmepNHLyElaNVTRU10dVpHW3BjMMBjVtJWd0ckW65UbM5WOHJWa5kHT20ESjBjUIF2X0hXZ0xCMx81dvRWYoNHLrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdssmch1mclRXY39CXldWYtlWPzNXZj9mcw1ycz9WL49zZuBnL3AjM4UjNzATM1AzMwEjMwIzLc52YucWbp5GZzNmLn9Gbi1yZtl2Lc9CX6MHc0RHaiojIsJye.png)
做題思路
n條直線,當其中有r條平行時,有兩類交點:r條平行線與其它直線的交點,以及剩下的(n - r)條直線的交點。因為題目要求無三線共點,是以第一類的交點個數可以直接求,個數為r * (n - r)。第二類的交點,可以遞歸求,因為它可以視為(n - r)條直線求交點。
是以,用一個數組标記出現過的交點數,最後進行統計。
代碼
#include<iostream>
#include<map>
#include<set>
#include<vector>
#include<algorithm>
#include<cstring>
#include<string>
#include<queue>
#include<functional>
#include<cmath>
#include<cstdlib>
using namespace std;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
typedef pair<int, int> pii;
typedef long long ll;
const int N = 10000;
bool st[N];
//x就是n - r,r為平行線條數,k是目前已有交點數
void f(int x, int k)
{
if (x == 0)
{
st[k] = 1;
return;
}
//對剩下的進行遞歸求出平行線條數從1到x的情況
for (int i = 1; i <= x; i++) f(x - i, i * (x - i) + k);
}
int main()
{
int n;
cin >> n;
f(n, 0);
int ans = 0;
for (int i = 0; i <= n * (n + 1) / 2; i++)
{
if (st[i]) ans++;
}
cout << ans;
return 0;
}