2020-2021:teams:i_dont_know_png:multi2020-nowcoder-8

差别

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

到此差别页面的链接

--- 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-8 [2020/08/04 00:15]
nikkukun 创建
+++ 2020-2021:teams:i_dont_know_png:multi2020-nowcoder-8 [2020/08/07 18:27] (当前版本)
qxforever
@@ 行 51: / 行 51: @@
 总时间复杂度 $O(n \log n)$。
+===== G - Game Set =====
+Solved by qxforever.
+==== 题目描述 ====
+给 $n$ 张互不相同的牌，每张牌有 $4$ 条属性，每个属性有 $3$ 种。还有一种额外属性表示可以取任意属性。问能否找到一个三张牌的集合，满足每张牌的每种属性都相同/不同。$T\le 1000$，$n\le 256$
+==== 解题思路 ====
+比赛的时候想的很麻烦，用 $8$ 位二进制数表示一张牌的状态，预处理了所有合法的三元组。算了下复杂度还是很紧，又加了一些优化。
+其实在 $21$ 张牌中必定存在满足条件的集合，直接 $n^3$ 搜就可以了。
+===== I - Interesting Computer Game =====
+Solved by Potassium.
+==== 题目描述 ====
+给两个长为 $n$ 的数组 $a,b$，对于每个下标 $i$，任选 $a_i$ 或 $b_i$ 加入到集合中，问最终集合最大有多大。$1 \le N \le 10^5$。
+==== 解题思路 ====
+一开始用左部 $i$ 右部 $a_i,b_i$ 的二分图做最大匹配，但复杂度显然并不对。
+考虑 $(a_i,b_i)$ 连边，每条边选择一个端点或不选。对于一个连通块，如果没有环，那必然所有边都可以被选中；否则，环上所有点显然可以全部选中，归纳可知必然所有点都可以被选中。

2020-2021/teams/i_dont_know_png/multi2020-nowcoder-8.1596471314.txt.gz · 最后更改: 2020/08/04 00:15 由 nikkukun