2022-2023:teams:kunkunkun:2022-nowcoder-10
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2022-2023:teams:kunkunkun:2022-nowcoder-10 [2022/08/27 18:20] polaraid |
2022-2023:teams:kunkunkun:2022-nowcoder-10 [2022/09/03 09:50] (当前版本) polaraid |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== 2022 牛客暑期多校训练营10 ====== | ====== 2022 牛客暑期多校训练营10 ====== | ||
| + | ===== B ===== | ||
| + | |||
| + | **题目大意：给定$n*n$的矩形，需要选定一个起点，使得起点到所有数字的最小距离的最大值最小** | ||
| + | |||
| + | **考虑二分答案，则对于每种数字，合法的区域是若干菱形的并，若所有颜色的区域的交非空，则当前答案合法** | ||
| + | |||
| + | **菱形是比较难维护的，考虑曼哈顿距离转切比雪夫距离，可以把菱形等价为矩形** | ||
| + | |||
| + | **对于每种数字来说，需要求若干矩形的并，离散化之后能够在$O(k^2)$的时间复杂度内求出区域并** | ||
| + | |||
| + | **之后要求矩形的交，可以利用二阶差分，将每种数字的对应区域加一，最后格子内的数为$m$，就表示该点能够在合法步数内到达所有数字** | ||
| + | |||
| ===== F-Shannon Switching Game? ===== | ===== F-Shannon Switching Game? ===== | ||
| 题目大意：给定一个无向图，初始时有一个token在s点，两个玩家Join Player和Cut Player轮流行动，CutPlayer先动。Cut Player每次可以移除一条和token所在位置相邻的边, Join Player每次可以将token沿着一条未删除边移动, 如果token在某刻被移动到t则Join Player获胜，否则Cut Player获胜，求双方最优策略下的胜者。\\ | 题目大意：给定一个无向图，初始时有一个token在s点，两个玩家Join Player和Cut Player轮流行动，CutPlayer先动。Cut Player每次可以移除一条和token所在位置相邻的边, Join Player每次可以将token沿着一条未删除边移动, 如果token在某刻被移动到t则Join Player获胜，否则Cut Player获胜，求双方最优策略下的胜者。\\ | ||
| 行 5: | 行 17: | ||
| 时间复杂度 $O(n+m)$ | 时间复杂度 $O(n+m)$ | ||
| + | ===== Replay ===== | ||
| + | |||
| + | H是个签到。 | ||
| + | |||
| + | I是一个队伍里三个人都一直在玩的题，最开始啥思路都没有，后来突然想到了减转化成加的形式，于是很快就过了。 | ||
| + | |||
| + | F罗皓天一直在玩，之后也是很轻松过掉了。 | ||
| + | |||
| + | E题是一个费用流。最开始想到一个费用流做法，然后想了想觉得不太行，于是又想了一个网络流做法。 | ||
| + | |||
| + | 然后高湘一想到了我最开始想到的费用流做法，仔细想了想之后发现好像还挺行的，于是写了A了。 | ||
| + | |||
| + | ===== Dirt ===== | ||
| + | |||
| + | 无 | ||
2022-2023/teams/kunkunkun/2022-nowcoder-10.1661595635.txt.gz · 最后更改: 2022/08/27 18:20 由 polaraid
