首页 > 集合操作
开通博客写题解
头像 Dear㉿You
发表于 2020-10-05 21:10:37
集合操作 分析 简化：S 中小于 x 的元素不超过 m 个 = 集合中以1开头的公差为1的数列的最长长度小于等于m 解释：假设这个集合里没有1，那么肯定存在一种情况，删去1能使这个集合合法。于是我们的目标转为——求以1为开头公差为1的长度小于等于m的数列个数（有点长，注意断句）。通过直接枚举数列的 展开全文
去ta的博客 赞 (3) 回复(0) 收起
头像 Deep_Dark_FAntasy♂
发表于 2020-09-26 18:53:25
思路：很容易知道所有的情况共有2^n个，然后我们思考不可能存在的情况有多少种。我们知道每次都可以从前m+1个种取一个。当我们左边减少0个，那么右边m+1到n中任意数字减少都不行，因此答案有2^(n-m-1)-1种(真子集都是不存在的情况，-1是因为自己一个不去)当我们左边m+1个中减少1个，那么答案 展开全文
去ta的博客 赞 (2) 回复(0) 收起
头像 zrzring
发表于 2020-10-14 20:51:55
更好的阅读体验 这种题一般都需要用到容斥 因为操作可以改变顺序，原题就变成了 将到的排列分成两个集合，，对于每个元素，都最多有个，求划分方案数 考虑枚举集合的大小，为了满足条件，时可以选择任意的数放入，时只能在从到里选择个 #include <iostream> #include & 展开全文
去ta的博客 赞 (1) 回复(0) 收起
查看本题
查看本题讨论

等你来战

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

扫描二维码，进入QQ群

扫码关注“比赛自动姬”