2022-2023:teams:kunkunkun:2022-nowcoder-加赛

差别

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

到此差别页面的链接

--- 2022-2023:teams:kunkunkun:2022-nowcoder-加赛 [2022/08/24 09:59]
sd_ltt 创建
+++ 2022-2023:teams:kunkunkun:2022-nowcoder-加赛 [2022/09/02 14:21] (当前版本)
purplewonder
@@ 行 4: / 行 4: @@
 由于矩阵的反对称性，只考虑右上角的矩阵，对于第 $i$ 行，当第 $j$ 列为 W 时，其 $i+1\sim j$ 列都必须为 W，当第 $j$ 列为 E 时，其 $j\sim n$ 列都必须为 E，对于每行最早出现的 E 的列数必须是不严格递增的。特别地，对于第一行，当 E 第一次出现在第 $j$ 列时，$j\sim n$ 行都必须为 W。根据以上规则 DP 即可。\\
 时间复杂度 $O(n^3)$
+===== G =====
+**题目大意：给定只包含'r'、'e'、'd'、'?'四种字符的字符串，其中'?'可表示为任意字符，询问该字符串是否能被拆为若干个"red"**
+**和括号匹配类似，要求从左到右$cnt( r )\geq cnt(e)\geq cnt(d)$，并且从右到左$cnt( r )\leq cnt(e)\leq cnt(d)$**
+**字母'e'的限制是关键，如果解决了字母'e'的限制，只要对所有'?'，从左到右依次放'r'、'e'、'd'即可**
+**用并查集维护某位置左边最近'?'的位置，然后从左到右扫一遍字符串，若'e'的数量不够，则把左边最近的'?'改为'e'**
+**同理，从右向左做一遍类似的操作，就可以解决'e'的限制**
+**解决'e'的限制之后，按顺序填好剩下'?'的值，然后检查字符串是否合法**
+===== K-Killer Sajin's Matrix =====
+构造一个大小为 n · m 的二维网格，使其中有 k 个 1，其余均为 0。并且该网格的每一行和每一列的和均为奇数。\\
+将 $k$ 分别分解为 $n$ 个小于 $m$ 的奇数作为每行的 $1$ 的个数和 $m$ 个小于 $n$ 的奇数作为每列的 $1$ 的个数。当分解尽可能平均时可以最大可能的保证有解，当且仅当 $n,m$ 为奇数且 $k=nm-2$ 时无解。\\
+ps:比赛时过了但结束后被自己用 3 3 7 给hack了。
+===== Replay =====
+（有人写了忘保存）
+M，H比较签到。
+E题是一道挺结论的题目，试了几次错才想到比较正确的规律。
+虽然有试错，但是可以发现如果只有一个错误要试，还是比较容易的。
+J是个链表题。一直以来链表题都是各种小错不断。（但是这次1A了）
+之后K题，罗皓天想了个做法，队伍里感觉都很可做，于是就写了。也过了。但是事后发现是错解。
+最后开的是G。想了一个比较合理的线段树做法，但是写到一半发现有一个操作完全不会实现。高湘一想到的做法应该是比较正确的。
+===== Dirt =====
+E题最开始交的两发是错解。
+K题全程都比较玄学。

2022-2023/teams/kunkunkun/2022-nowcoder-加赛.1661306350.txt.gz · 最后更改: 2022/08/24 09:59 由 sd_ltt