用户工具

站点工具


2022-2023:teams:kunkunkun:2022-nowcoder-10

2022 牛客暑期多校训练营10

B

题目大意:给定$n*n$的矩形,需要选定一个起点,使得起点到所有数字的最小距离的最大值最小

考虑二分答案,则对于每种数字,合法的区域是若干菱形的并,若所有颜色的区域的交非空,则当前答案合法

菱形是比较难维护的,考虑曼哈顿距离转切比雪夫距离,可以把菱形等价为矩形

对于每种数字来说,需要求若干矩形的并,离散化之后能够在$O(k^2)$的时间复杂度内求出区域并

之后要求矩形的交,可以利用二阶差分,将每种数字的对应区域加一,最后格子内的数为$m$,就表示该点能够在合法步数内到达所有数字

F-Shannon Switching Game?

题目大意:给定一个无向图,初始时有一个token在s点,两个玩家Join Player和Cut Player轮流行动,CutPlayer先动。Cut Player每次可以移除一条和token所在位置相邻的边, Join Player每次可以将token沿着一条未删除边移动, 如果token在某刻被移动到t则Join Player获胜,否则Cut Player获胜,求双方最优策略下的胜者。
从 $t$ 考虑,能够走到 $t$ 的点与 $t$ 必有两条及以上的边相连,将这些点和 $t$ 加入集合,若其他点有两条及以上的边连向该集合,则再将这些点加入集合,最后若 $s$ 在集合中则 Join Player 胜利,否则 Cut Player 胜利。
时间复杂度 $O(n+m)$

Replay

H是个签到。

I是一个队伍里三个人都一直在玩的题,最开始啥思路都没有,后来突然想到了减转化成加的形式,于是很快就过了。

F罗皓天一直在玩,之后也是很轻松过掉了。

E题是一个费用流。最开始想到一个费用流做法,然后想了想觉得不太行,于是又想了一个网络流做法。

然后高湘一想到了我最开始想到的费用流做法,仔细想了想之后发现好像还挺行的,于是写了A了。

Dirt

2022-2023/teams/kunkunkun/2022-nowcoder-10.txt · 最后更改: 2022/09/03 09:50 由 polaraid