2022-2023:teams:just_ridiculous:2022.07.23_牛客多校第二场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:just_ridiculous:2022.07.23_牛客多校第二场 [2022/07/26 21:42] infinity0 创建 |
2022-2023:teams:just_ridiculous:2022.07.23_牛客多校第二场 [2022/08/28 18:24] (当前版本) laiang8086 |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 2022.07.23 牛客多校第二场 ====== | ====== 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在中间来读题，同时观察榜单寻找可做的。 | 开局还是按照我们队的常规分配，jrt从后往前，hqy从前往后，lcj在中间来读题，同时观察榜单寻找可做的。 | ||
| 然后hqy主攻G题，jrt看了看K题想到了一个三维的DP，但是转移复杂度太高，遂转而看D，lcj主攻E题。 | 然后hqy主攻G题，jrt看了看K题想到了一个三维的DP，但是转移复杂度太高，遂转而看D，lcj主攻E题。 | ||
| 行 17: | 行 57: | ||
| 16:00~17:00 | 16:00~17:00 | ||
| 换hqy上机来尝试K题，未果 | 换hqy上机来尝试K题，未果 | ||
| - | ===== 不足之处 ===== | + | ===== 不足之处 Dirt===== |
| D题没想到判负环，也没想到通过取对数化乘除为加减解决精度问题 | D题没想到判负环，也没想到通过取对数化乘除为加减解决精度问题 | ||
| 全队整体水平偏低，许多题目和算法都没有思路 | 全队整体水平偏低，许多题目和算法都没有思路 | ||
2022-2023/teams/just_ridiculous/2022.07.23_牛客多校第二场.1658842931.txt.gz · 最后更改: 2022/07/26 21:42 由 infinity0
