Codeforces Round #558 (Div. 2) A-C解题报告

这场有点可惜,ABC都是一眼题,Bmap卡了erase,C没想到用map+set存这个

A题:不难看出n/2为界限,注意当m=0的时候。我为了保险和1去了max输出
代码:https://paste.ubuntu.com/p/VmSF4VQgsx/

B题:B1的数据暴力可以过,我们来看看B2的怎么解决。1e5个数,可以开双层map或者,一层计数数组,一层map。就是写起来有点绕,剩10分钟才写出来,还是wa。。。。
代码:https://paste.ubuntu.com/p/RSk9HVBHxH/

C题:C思路很简单,一条线可以与其他跟他斜率不同的相交。
这里我推出来一个公式(防精度):

对于直线方程式ax+by+c=0
我们需要两个元素确定直线y = kx+b 一个是k一个是b
把上面一般式除过来
k = a/b
b = c/b
k又等于两点纵坐标之差/两点横坐标之差
k = dy/dx =a/b
所以dy/gcd(dy,dx)=a
dx/gcd(dy,dx) = b
再带入一个点坐标可以得到c
如此一来完美的避开了double 精度问题
可以用map<pair<int,int>,set<int,int>>mp
当我为了写起来方便 给一个数×1e4+另一个数存起来了。

代码:https://paste.ubuntu.com/p/V8MmTDFrdr/
(全改ll是因为我有次debug怕是这边问题 快捷键修改了)

人一我百,人十我万。
原文地址:https://www.cnblogs.com/AlexPanda/p/12520335.html