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)$。 | 总时间复杂度 $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
