首页 > 生涯回忆录
开通博客写题解
头像 __故人__
发表于 2020-11-23 20:12:13
题意 求出所以子集中最小没有出现的正整数之和。 分析 我们可以考虑一个元素的贡献，我们先考虑如果这个数 可以作为答案，那么 的每个元素至少选取了一次。那么根据乘法原理， 的总方案为 。 表示 这个数出现的次数。那么 的元素，可以选也可以不选总的方案数为 。上面的指数也可以通过前缀和维 展开全文
去ta的博客 赞 (8) 回复(1) 收起
头像 do_while_true
发表于 2020-11-22 23:14:38
题目链接 简要题意：给定一个集合，求集合里面每一个子集的 MEX。 这里定义一个集合的 MEX 为这个集合最小的没有出现的数 考虑一个数作为 MEX 在几个子集里面出现，首先它能成为 MEX 需要小于它的自然数都至少出现一个，也就是它必须小于等于给定的集合的 MEX。 枚举每一个 MEX，记录每个 展开全文
去ta的博客 赞 (7) 回复(0) 收起
头像 Bernard5
发表于 2020-11-22 23:31:25
题意 给定一个集合，问它的所有子集里，最小的没出现过的正整数之和是多少。 solution 先桶一遍。因为只有个数，所以每个区间的贡献（也就是每个区间没出现过的最小正整数）的取值范围必定在。所以其实桶只需要统计范围内就可以了。 那么只需要遍历桶： #include <bits/stdc++. 展开全文
去ta的博客 赞 (5) 回复(0) 收起
查看本题
查看本题讨论

相关比赛

等你来战

查看全部
牛客竞赛，专业的竞技算法训练平台

扫描二维码，进入QQ群

扫码关注“比赛自动姬”