6.13随笔(牛客练习赛C二维动点)
好好打比赛每场都或多或少有些收获,昨天被牛客的C卡死,细节满满,今天早上又写了很久,收获还是蛮大的
辗转相除法求最大公约数
原理什么的就不说了,我之前的写法都是
1 | ll gcd(ll x, ll y) |
这种写法挺常见的,不过有一个弊端,就是如果y为0的时候会出现%0
的RE
稍微改一下:
1 | ll gcd(ll x, ll y) |
这样的话如果y为0,会输出x
另外一点题外话:关于0和一个数a的最大公约数,我百度到有两种说法,一种说是数a,另一种说是不存在。
用上面的写法2默认最大公约数是数a,但是最主要的是规避的RE问题
存储斜率
斜率问题也是经常遇到的,不过我之前都是直接存成浮点,昨天才意识到最正确的方式应该是存成pair,毕竟之前也提到了浮点数是有精度问题的。(虽然现在还没被卡过,不过以后要注意了)
题目:传送门
题目大意不说了,直接说思路
比较简单的两种情况:
直接到达(0):需要到达的点就是原点
一次到达:需要到达的点与原点练成的直线经过一个存在的点
两次到达情况比较复杂,但是三次才能到达只有一种情况,就是之前只存在两个点,并且与要到达的点 形成平行四边形的时候,如下图:
证明略(不会)
AC代码:
浮点解法:
1 | map<double, int> mp1; |
pair解法:
1 | map<pair<ll, ll>, ll> mp; |