洛谷P7918 【洛谷月赛LGR-096 Div.2 T2】 [Kubic] Lines题解

2023-11-21 16:20

本文主要是介绍洛谷P7918 【洛谷月赛LGR-096 Div.2 T2】 [Kubic] Lines题解,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

这道题是普及-,结果我比赛时想了整整一个小时。。。果然我还是太了啊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=1k1j=i+1kdidj=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 nmaxi=1ndi。因为既然要覆盖所有的点,只能有一类直线不被选取,其他类的直线必须被选取。那么就舍弃数量最多的一类直线。
关于只能有一类直线被舍弃,可以用反证法。假如有两类直线都被舍弃,则这两类之间的交点无法被任何其他类的直线覆盖,所以最多只能舍弃一类。

时间复杂度: O ( n log ⁡ n ) O(n \log n) O(nlogn)

代码实现

代码中,我们使用mpstd::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;
}

这篇关于洛谷P7918 【洛谷月赛LGR-096 Div.2 T2】 [Kubic] Lines题解的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/403539

相关文章

C++ | Leetcode C++题解之第393题UTF-8编码验证

题目: 题解: class Solution {public:static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num &

C语言 | Leetcode C语言题解之第393题UTF-8编码验证

题目: 题解: static const int MASK1 = 1 << 7;static const int MASK2 = (1 << 7) + (1 << 6);bool isValid(int num) {return (num & MASK2) == MASK1;}int getBytes(int num) {if ((num & MASK1) == 0) {return

C - Word Ladder题解

C - Word Ladder 题解 解题思路: 先输入两个字符串S 和t 然后在S和T中寻找有多少个字符不同的个数(也就是需要变换多少次) 开始替换时: tips: 字符串下标以0开始 我们定义两个变量a和b,用于记录当前遍历到的字符 首先是判断:如果这时a已经==b了,那么就跳过,不用管; 如果a大于b的话:那么我们就让s中的第i项替换成b,接着就直接输出S就行了。 这样

【秋招笔试】9.07米哈游秋招改编题-三语言题解

🍭 大家好这里是 春秋招笔试突围,一起备战大厂笔试 💻 ACM金牌团队🏅️ | 多次AK大厂笔试 | 大厂实习经历 ✨ 本系列打算持续跟新 春秋招笔试题 👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸 ✨ 笔试合集传送们 -> 🧷春秋招笔试合集 🍒 本专栏已收集 100+ 套笔试题,笔试真题 会在第一时间跟新 🍄 题面描述等均已改编,如果和你笔试题看到的题面描述

LeetCode 第414场周赛个人题解

目录 Q1. 将日期转换为二进制表示 原题链接 思路分析 AC代码 Q2. 范围内整数的最大得分 原题链接 思路分析 AC代码 Q3. 到达数组末尾的最大得分 原题链接 思路分析 AC代码 Q4. 吃掉所有兵需要的最多移动次数 原题链接 思路分析 AC代码 Q1. 将日期转换为二进制表示 原题链接 Q1. 将日期转换为二进制表示 思路分析

牛客小白月赛100部分题解

比赛地址:牛客小白月赛100_ACM/NOI/CSP/CCPC/ICPC算法编程高难度练习赛_牛客竞赛OJ A.ACM中的A题 #include<bits/stdc++.h>using namespace std;#define ll long long#define ull = unsigned long longvoid solve() {ll a,b,c;cin>>a>>b>

P2858 [USACO06FEB] Treats for the Cows G/S 题解

P2858 题意 给一个数组。每天把最左或者最右的东西卖掉,第 i i i个东西,第 d a y day day天卖出的价格是 a [ i ] ∗ d a y a[i]*day a[i]∗day。 记忆化搜索 void dfs(int l,int r,int day,ll sum){if(v[l][r]>=sum)return;v[l][r]=sum;if(l>r)//这就是dp答案{

高精度计算(代码加解析,洛谷p1601,p1303)除法待更新

目录 高精度加法 高精度减法 高精度乘法 高精度加法 我们知道在c++语言中任何数据类型都有一定的表示范围。当两个被加数很大时,正常加法不能得到精确解。在小学,我们做加法都采用竖式方法。那么我们也只需要按照加法进位的方式就能得到最终解。 8 5 6+ 2 5 5-------1 1 1 1 加法进位: c[i] = a[i] + b[i];if(c[i] >=

洛谷 凸多边形划分

T282062 凸多边形的划分 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 先整一个半成品,高精度过两天复习一下补上 #include <iostream>#include <algorithm>#include <set>#include <cstring>#include <string>#include <vector>#include <map>

能量项链,洛谷

解释:  环形dp问题还是考虑将环拉直,可以参考我上一篇文章:环形石子合并 [2 3 5 10 2] 3 5 10 将环拉直,[]内是一个有效的区间,可以模拟吸收珠子的过程,         如[2 3 5] <=>(2,3)(3,5)    2是头,3是中间,5是尾 len >= 3:因为最后[2 10 2]是最小的可以合并的有效区间 len <= n + 1因为[2 3