洛谷P7918 【洛谷月赛LGR
这道题是普及-，结果我比赛时想了整整一个小时。。。果然我还是太菜了啊QAQ
题目大意
解题思路
佬曰：“有人看到这道题直接网络流。”
网络流？最大独立集？大可不必。题目中最关键的一句话其实是
注意：输入数据不保证 gcd ( a , b ) = 1 \gcd(a,b)=1 gcd(a,b)=1。
真是一语点醒梦中人。事实上，我们需要充分利用 a a a, b b b是整数的条件。两条直线 a i x + b i y + c i = 0 a_ix+b_iy+c_i=0 aix+biy+ci=0与 a j x + b j y + c j = 0 a_jx+b_jy+c_j=0 ajx+bjy+cj=0平行，当且仅当 a i b j = a j b i a_ib_j=a_jb_i aibj=ajbi（或者说它们斜率相等）。如果我们将每对 ( a i , b i ) (a_i,b_i) (ai,bi)预处理成 ( a i gcd ( a i , b i ) , b i gcd ( a i , b i ) ) (\frac{a_i}{\gcd(a_i,b_i)},\frac{b_i}{\gcd(a_i,b_i)}) (gcd(ai,bi)ai,gcd(ai,bi)bi)（如果 gcd ( a i , b i ) ≠ 0 \gcd(a_i,b_i)\ne 0 gcd(ai,bi)=0），那么平行的直线其 ( a i gcd ( a i , b i ) , b i gcd ( a i , b i ) ) (\frac{a_i}{\gcd(a_i,b_i)},\frac{b_i}{\gcd(a_i,b_i)}) (gcd(ai,bi)ai,gcd(ai,bi)bi)是相等的（例如 3 x + 5 y + 3 = 0 3x+5y+3=0 3x+5y+3=0和 9 x + 15 y + 8 = 0 9x+15y+8=0 9x+15y+8=0，都可以处理成 ( 3 , 5 ) (3,5) (3,5)）。每条直线的斜率都被归约为互质的数对。而这样的数对不相等的直线一定会相交，因为斜率不相等。我们将平行的直线合并为一“类”，假设共有 k k k类，两类直线之间一定会有交点。假设每类所含直线个数分别为 d 1 , d 2 , … , d k d_1,d_2,\dots,d_k d1,d2,…,dk。
我比赛时的想法是：总的交点个数为 ∑ i = 1 k − 1 ∑ j = i + 1 k d i d j = ( d 1 + d 2 + ⋯ + d k ) 2 − ( d 1 2 + d 2 2 + ⋯ + d k 2 ) 2 \sum \limits_{i=1}^{k-1} \sum \limits_{j=i+1}^kd_id_j=\frac{(d_1+d_2+\dots+d_k)^2-(d_1^2+d_2^2+\dots+d_k^2)}{2} i=1∑k−1j=i+1∑kdidj=2(d1+d2+⋯+dk)2−(d12+d22+⋯+dk2)。按 d i d_i di从小到大选取覆盖的直线，每次能覆盖 d i ( d i + 1 + d i + 2 + ⋯ + d n ) d_i(d_{i+1}+d_{i+2}+\dots+d_n) di(di+1+di+2+⋯+dn)个点。直到能覆盖到所有交点为止。
正解： 后来一想，发现其实答案是 n − max i = 1 n d i n- \text{max}_{i=1}^nd_i n−maxi=1ndi。因为既然要覆盖所有的点，只能有一类直线不被选取，其他类的直线必须被选取。那么就舍弃数量最多的一类直线。
关于只能有一类直线被舍弃，可以用反证法。假如有两类直线都被舍弃，则这两类之间的交点无法被任何其他类的直线覆盖，所以最多只能舍弃一类。
时间复杂度： O ( n log n ) O(n \log n) O(nlogn)。
代码实现
代码中，我们使用mp（std::map<pair<ll, ll>, ll>类型）来统计数对为pair<ll, ll>的直线的个数（即 d i d_i di）。
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <queue>
#include <map>
#include <functional>using namespace std;typedef long long ll;
typedef unsigned long long ull;inline ll read() // 快速读入
{ll ret = 0;char sgn = 0;char c;while(!isdigit(c = getchar())) if(c == '-') sgn = 1;ret = c ^ 48;while(isdigit(c = getchar())) ret = (ret << 1) + (ret << 3) + (c ^ 48);return sgn ? -ret : ret;
}const int MAXN = 1e5 + 5;
ll n, a[MAXN], b[MAXN], c[MAXN]; // a[i]x + b[i]y + c[i] = 0
map<pair<ll, ll>, ll> mp;ll gcd(ll ai, ll bi) // 最大公约数
{return bi ? gcd(bi, ai % bi) : ai;
}void ins(ll ai, ll bi) // 插入一条直线
{ll g = gcd(ai, bi);if(!g) g = 1;// 如果最大公约数为0，就将ai, bi同时除1，相当于啥都没干pair<ll, ll> p(ai / g, bi / g);// 找到直线对应的数对（每类直线数对相等）if(mp.find(p) == mp.end()) // 如果mp中没有找到该数对mp[p] = 1; // 新建该数对（新建一类），数量为1else ++mp[p]; // 否则该类直线个数+1
}int main()
{n = read();for(ll i = 1; i <= n; ++i)a[i] = read(), b[i] = read(), ins(a[i], b[i]), c[i] = read();ll ans = 0;for(map<pair<ll, ll>, ll>::iterator i = mp.begin(); i != mp.end(); ++i)ans = max(ans, i->second); // 找到数量最多的一类直线cout << n - ans << '\n'; // 输出答案return 0;
}
发布评论