2022-2023:teams:just_ridiculous:2022.07.23_牛客多校第二场
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:just_ridiculous:2022.07.23_牛客多校第二场 [2022/07/27 13:45] cacu |
2022-2023:teams:just_ridiculous:2022.07.23_牛客多校第二场 [2022/08/28 18:24] (当前版本) laiang8086 |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| 若光源高于凸包，求内部凸包的顶部经过投影之后与内部凸包底部的交。套半平面交即可，但要注意处理两射线（半平面）平行的情况。 | 若光源高于凸包，求内部凸包的顶部经过投影之后与内部凸包底部的交。套半平面交即可，但要注意处理两射线（半平面）平行的情况。 | ||
| + | ==== C ==== | ||
| + | 博弈相关思维题。nim游戏中，必输一方要使操作次数最大，必胜一方要使操作次数最小。 | ||
| + | 观察样例发现（猜），当异或和为0时的下一次操作，可以只取一个石子，同时使得取完之后对方也只能取一个石子。 | ||
| + | |||
| + | 若先手必胜，先手要保证取完之后异或和为0，在此基础上使取石子数最多。 | ||
| + | |||
| + | 若先手必输，先手要只取一个石子，同时使得取完之后对方也只能取一个石子。 | ||
| + | |||
| + | 对于先手必输情况不是很好算，但注意到：从大小为x的堆取一个石子之后，实际上异或和变成了x xor (x-1),这种取值种类只有log级别，因此可以维护。 | ||
| ==== D ==== | ==== D ==== | ||
| 图论，每个有向边权值为分数c/a，可以给所有权值乘一系数w，问w的最大值，使得图中没有权值乘积大于1的环。 | 图论，每个有向边权值为分数c/a，可以给所有权值乘一系数w，问w的最大值，使得图中没有权值乘积大于1的环。 | ||
| 行 24: | 行 33: | ||
| 以根号n为单位构造形如789456123的序列即可。 | 以根号n为单位构造形如789456123的序列即可。 | ||
| + | ==== H ==== | ||
| + | 将上下行分开。贪心，每次取终点最高的作为答案，每次贪心地塞人进电梯。 | ||
| + | 塞人方法：终点从高到低找，超过m个人了就找终点小于最高起点的。 | ||
| + | 再把上下行的多次行程中拼凑起来，将最大的拼到最大的就行了，取max。 | ||
| ==== I ==== | ==== I ==== | ||
| 构造矩阵乘法即可。 | 构造矩阵乘法即可。 | ||
| - | ===== 赛中记录 ===== | + | ===== 赛中记录 Replay===== |
| 开局还是按照我们队的常规分配，jrt从后往前，hqy从前往后，lcj在中间来读题，同时观察榜单寻找可做的。 | 开局还是按照我们队的常规分配，jrt从后往前，hqy从前往后，lcj在中间来读题，同时观察榜单寻找可做的。 | ||
| 然后hqy主攻G题，jrt看了看K题想到了一个三维的DP，但是转移复杂度太高，遂转而看D，lcj主攻E题。 | 然后hqy主攻G题，jrt看了看K题想到了一个三维的DP，但是转移复杂度太高，遂转而看D，lcj主攻E题。 | ||
| 行 44: | 行 57: | ||
| 16:00~17:00 | 16:00~17:00 | ||
| 换hqy上机来尝试K题，未果 | 换hqy上机来尝试K题，未果 | ||
| - | ===== 不足之处 ===== | + | ===== 不足之处 Dirt===== |
| D题没想到判负环，也没想到通过取对数化乘除为加减解决精度问题 | D题没想到判负环，也没想到通过取对数化乘除为加减解决精度问题 | ||
| 全队整体水平偏低，许多题目和算法都没有思路 | 全队整体水平偏低，许多题目和算法都没有思路 | ||
2022-2023/teams/just_ridiculous/2022.07.23_牛客多校第二场.1658900715.txt.gz · 最后更改: 2022/07/27 13:45 由 cacu
