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

差别

这里会显示出您选择的修订版和当前版本之间的差别。

到此差别页面的链接

--- 2022-2023:teams:kunkunkun:2022-nowcoder-10 [2022/08/27 17:49]
polaraid
+++ 2022-2023:teams:kunkunkun:2022-nowcoder-10 [2022/09/03 09:50] (当前版本)
polaraid
@@ 行 1: / 行 1: @@
 ====== 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获胜，求双方最优策略下的胜者。\\
@@ 行 5: / 行 17: @@
 时间复杂度 $O(n+m)$
-===== G =====
+===== Replay =====
+H是个签到。
-**题目大意：给定只包含'r'、'e'、'd'、'?'四种字符的字符串，其中'?'可表示为任意字符，询问该字符串是否能被拆为若干个"red"**
+I是一个队伍里三个人都一直在玩的题，最开始啥思路都没有，后来突然想到了减转化成加的形式，于是很快就过了。
-**和括号匹配类似，要求从左到右$cnt( r )\geq cnt(e)\geq cnt(d)$，并且从右到左$cnt( r )\leq cnt(e)\leq cnt(d)$**
+F罗皓天一直在玩，之后也是很轻松过掉了。
-**字母'e'的限制是关键，如果解决了字母'e'的限制，只要对所有'?'，从左到右依次放'r'、'e'、'd'即可**
+E题是一个费用流。最开始想到一个费用流做法，然后想了想觉得不太行，于是又想了一个网络流做法。
-**用并查集维护某位置左边最近'?'的位置，然后从左到右扫一遍字符串，若'e'的数量不够，则把左边最近的'?'改为'e'**
+然后高湘一想到了我最开始想到的费用流做法，仔细想了想之后发现好像还挺行的，于是写了A了。
-**同理，从右向左做一遍类似的操作，就可以解决'e'的限制**
+===== Dirt =====
-**解决'e'的限制之后，按顺序填好剩下'?'的值，然后检查字符串是否合法**
+无

2022-2023/teams/kunkunkun/2022-nowcoder-10.1661593761.txt.gz · 最后更改: 2022/08/27 17:49 由 polaraid