社区讨论

选数,求多项式时间复杂度算法

学术版参与者 5已保存回复 5

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mhk77sbl
此快照首次捕获于
2025/11/04 14:39
4 个月前
此快照最后确认于
2025/11/04 14:39
4 个月前
查看原帖

选数,求多项式时间复杂度算法

题目背景

因为本人太弱在做CSP-S2024T2时脑抽想出来的问题,和机房大佬讨论之后没有思考出除暴搜以外的算法来解决这个问题,故在这里求助。本人第一次写题面,若描述不清晰或有疏漏请见谅。
如果有类似的题目,希望大佬留下题号或链接!

题目描述

给定 nn 个数集,第 ii 个数集为 XiX_i
尝试找出一个元素个数最少的数集 AA ,使得每个 XiX_i 都存在至少一个元素属于 AA (即 Xi,a:(aXi)(aA)\forall X_i, \exists a : (a \in X_i) \land (a \in A) )。
求出这个数集 AA 所包含的元素个数。

输入格式

第一行有一个整数,表示数集个数 nn
接下来n行:
ii 行有一个整数 mim_i ,表示 XiX_i 的元素个数,接下来是 mim_i 个整数,表示 XiX_i 的元素。

输出格式

一个整数,数集 AA 所包含的元素个数。

样例 #1

样例输入 #1

CPP
3
3 1 2 3
3 4 5 6
3 1 2 4

样例输出 #1

CPP
2

提示

样例 #1 解释

A={1,4}A=\{1,4\}A={2,4}A=\{2,4\}

数据范围

元素范围在INT_MIN和INT_MAX之间。

回复

5 条回复,欢迎继续交流。

正在加载回复...