CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 2022.07.23 牛客多校第二场 ======
===== 题解 =====
==== B ====
计算几何，其实思路很简单，但是代码麻烦，需要一些细节处理以及套板子。

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

讨论光源的位置：

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

若光源高于凸包，求内部凸包的顶部经过投影之后与内部凸包底部的交。套半平面交即可，但要注意处理两射线（半平面）平行的情况。
==== C ====
博弈相关思维题。nim游戏中，必输一方要使操作次数最大，必胜一方要使操作次数最小。

观察样例发现（猜），当异或和为0时的下一次操作，可以只取一个石子，同时使得取完之后对方也只能取一个石子。

若先手必胜，先手要保证取完之后异或和为0，在此基础上使取石子数最多。

若先手必输，先手要只取一个石子，同时使得取完之后对方也只能取一个石子。

对于先手必输情况不是很好算，但注意到：从大小为x的堆取一个石子之后，实际上异或和变成了x xor (x-1),这种取值种类只有log级别，因此可以维护。
==== D ====
图论，每个有向边权值为分数c/a，可以给所有权值乘一系数w，问w的最大值，使得图中没有权值乘积大于1的环。

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

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

再对所有权值取负数，就变成了判负环问题，套Bellman-ford算法。
==== G ====
构造题猜结论。

以根号n为单位构造形如789456123的序列即可。
==== H ====
将上下行分开。贪心，每次取终点最高的作为答案，每次贪心地塞人进电梯。
塞人方法：终点从高到低找，超过m个人了就找终点小于最高起点的。
再把上下行的多次行程中拼凑起来，将最大的拼到最大的就行了，取max。
==== I ====

构造矩阵乘法即可。

===== 赛中记录 Replay=====
开局还是按照我们队的常规分配，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题，未果
===== 不足之处 Dirt=====
D题没想到判负环，也没想到通过取对数化乘除为加减解决精度问题
全队整体水平偏低，许多题目和算法都没有思路
赛时过于依赖于排行榜，总想着把过的人很多题搞定而导致卡题。对于一时通过少的题目未给予重视，之后出现卡题时还是应该及时切换，读一读其他题。
CVBB ACM Team

用户工具

站点工具

页面工具
