用户工具

站点工具


2022-2023:teams:just_ridiculous:2022.07.23_牛客多校第二场

这是本文档旧的修订版!


2022.07.23 牛客多校第二场

题解

B

计算几何,其实思路很简单,但是代码麻烦,需要一些细节处理以及套板子。

题意:给一个有厚度有高度的凸包,给一个三维坐标为光源,问凸包内被光照射的面积。

讨论光源的位置:

若光源高度小于凸包高度,面积为内部凸包面积或0;

若光源高于凸包,求内部凸包的顶部经过投影之后与内部凸包底部的交。套半平面交即可,但要注意处理两射线(半平面)平行的情况。

D

图论,每个有向边权值为分数c/a,可以给所有权值乘一系数w,问w的最大值,使得图中没有权值乘积大于1的环。

w可以二分,重点是如何处理“图中没有权值乘积大于1的环”。

可以考虑取对数,这样边的权值从w*c/a变成了log(w) + log© - log(a),问图中是否有权值之和大于0的环。

再对所有权值取负数,就变成了判负环问题,套Bellman-ford算法。

G

构造题猜结论。

以根号n为单位构造形如789456123的序列即可。

赛中记录

开局还是按照我们队的常规分配,jrt从后往前,hqy从前往后,lcj在中间来读题,同时观察榜单寻找可做的。 然后hqy主攻G题,jrt看了看K题想到了一个三维的DP,但是转移复杂度太高,遂转而看D,lcj主攻E题。 接着在半个小时左右,hqy上机解决了G题,然后换lcj上机做E题,jrt先和hqy讨论了一下D题,觉得就是找环算倍率再取倒数,感觉复杂度都差不多,然后jrt就转而看J题了。

13:30 此时lcj的E题交了一发WA了,考虑到这个题已经耗了不少时间,于是决定换jrt写J题,lcj再检查一下E题的式子。14:00左右过了J题

14:00~15:00 过了J题之后,让lcj再上机调了调E题,还是无果。然后由jrt写D题,hqy转而思考K题。不过D题的找环出现了问题。用Tarjan找SCC的做法是错的,而暴力找又会超时,故D题dirt了两发。

15:00~16:00 jrt和lcj找出了E题中公式的问题,也做出了修改,但还是得不出正确的公式,故E又WA了几发

16:00~17:00 换hqy上机来尝试K题,未果

不足之处

D题没想到判负环,也没想到通过取对数化乘除为加减解决精度问题 全队整体水平偏低,许多题目和算法都没有思路 赛时过于依赖于排行榜,总想着把过的人很多题搞定而导致卡题。对于一时通过少的题目未给予重视,之后出现卡题时还是应该及时切换,读一读其他题。

2022-2023/teams/just_ridiculous/2022.07.23_牛客多校第二场.1658845408.txt.gz · 最后更改: 2022/07/26 22:23 由 infinity0