【Codeforces】CF367D Sereja and Sets (数学)
2024-10-21 03:02:32
题目大意
1到n这n个正整数被分成了m个不相交的集合(集合不一定连续),现在从这m个集合中选出最少个数的集合,满足对于[1,n]中任意一个长度为d的区间都至少有一个数字出现在已选集合中。(1 <= d <= n <= 100000, 1 <= m <= 20)
输入输出样例
输入样例1
3 2 2
1 2
2 1 3
输出样例1
1
输入样例2
5 1 1
5 4 5 3 2 1
输出样例2
1
输入样例3
7 3 1
4 1 3 5 7
2 2 6
1 4
输出样例3
3
分析
本来想贪心做的,手玩半天样例玩不出答案而且还不知道怎么写,最后选择了屈服
考虑一个长度为d的区间如果符合条件,那么这个区间内包含的数的所属集合中任选一个,这个区间就是合法的,
暂时称这些集合为每段区间的合法集合,这些集合可以组成一个集合组(集合的集合,姑且叫它合法集合组
题目转化为选出数量最少集合组成一个集合组,这个集合组满足与所有的区间的合法集合组都有交集(交集的元素是若干个集合
直接求答案不好求,我们反过来试试
对于每个区间的合法集合组,它的补集及其子集一定是不合法的,把这些集合组都去掉,剩下的集合组就是合法的了
然后枚举找出最小的集合组即可
具体实现的话,从大到小枚举集合组,枚举到一个不合法的集合组就把它的子集都打上标记,枚举到合法的就更新答案
Code
#include<cstdio>
#include<algorithm>
using namespace std;
int n,m,d,I,ans,ori[],mp[],vis[];
int main()
{
scanf("%d%d%d",&n,&m,&d);I=(<<m)-;ans=m;
for(int i=,a,k;i<=m;i++){scanf("%d",&k);while(k--)scanf("%d",&a),ori[a]=i;}
for(int i=;i<=d;i++)vis[ori[i]]++;
for(int l=,r=d;r<=n;vis[ori[l]]--,l++,r++,vis[ori[r]]++)
{int st=;for(int i=;i<=m;i++)if(vis[i])st|=<<(i-);mp[I-st]=;}
for(int st=I;st>=;st--)
if(mp[st]){for(int j=;j<=m;j++)if(st&(<<(j-)))mp[st^(<<(j-))]=;}
else ans=min(__builtin_popcount(st),ans);
printf("%d\n",ans);
}
最新文章
- Java类访问权限修饰符
- 安装升级npm依赖
- 玩转WIN7的MKLINK
- JavaBean基本用法示例(二)
- Linux压力测试工具Tsung安装、使用和图形报表生成
- 【python】list。列表
- Right Column - 右侧栏目
- JY03-HTML/CSS-京东02
- nefu 903 字符串去星
- iptables原理详解以及功能说明
- PyQt4 初试牛刀二
- chrome开发工具指南(十三)
- 新版Azure Automation Account 浅析(三) --- 用Runbook管理AAD Application Key
- [测试题]gentree
- 001 Nibiru SDK 调试工具介绍
- FAST MONTE CARLO ALGORITHMS FOR MATRICES II (快速的矩阵分解策略)
- Perl数组和hash相关函数
- linux 如何快速的查找日志中你所要查找的信息
- confluence部署与破解
- 【CF914G】Sum the Fibonacci 快速??变换模板