$$\color{Purple}{kuangbin题解目录}$$
描述
给定 $n$ 个整数,请你从中选出尽可能多的数。
要求对于任意两个选出的数 $a$ 和 $b$,均满足 $a$ 不能整除 $b$ 并且 $b$ 不能整除 $a$。
输出能够选择的数的最大数量。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据第一行包含整数 $n$。
第二行包含 $n$ 个整数。
输出格式
每组数据输出一行结果,一个整数,表示能够选择的数的最大数量。
数据范围
$1 \\le T \\le 10$,
$1 \\le n \\le 1000$,
给出的数的取值范围 $\[1,2^{63}-1\]$。
输入样例:
1
3
1 2 3
输出样例:
2
思路
- 首先声明该题用
Dancing Links
可在$hdu$上通过,在$Acwing$上会$tle$;- 这里大体说一下
Dancing Links
的解法,首先可看出该题与之前的重复覆盖问题
的差别在于该题求最大值
之前题求最小值
,故在剪枝的过程是相反的,其他的操作不变;- 在构建的$01$矩阵中,横坐标为$n$个数,纵坐标也为$n$个数,枚举任意两个数$i,j$,若两数能相除(可理解为
a[i]%a[j]==0||a[j]%a[i]==0
),就将其插入到链中,表示选择了第$i$个数的话就不选择第$j$个数;- 最后求
最大重复覆盖问题即可
.
- 正解
- 可以转化为
二分图匹配
的最大独立集
问题的模型,在有整除关系的两个数之间建立边,从而构建整个二分图。这样,满足条件的数,即之间没有边相连的两个数.就满足独立集的定义,求出最大独立集即可.最大独立集=顶点数-最小顶点覆盖=顶点数-最大匹配
代码
- $Dancing Links$($tle$)
// Problem: 整除
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4240/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-16 20:54:06
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 1010
#define MAXM 1001010
using namespace std;
typedef long long ll;
int t,n;
ll a[MAXN];
struct Dancing_Links_Node{
int Up;
int Down;
int Left;
int Right;
int row;//行数
int col;//列数
};
int cnt=0;//记录结点个数
Dancing_Links_Node node[MAXM];
int f_row[MAXN];//记录每行的第一个元素
int c_cnt[MAXN];//每列元素个数
int res;
int vis[MAXN];
int f()
{
int res=0;
memset(vis,0,sizeof(vis));
for(int i=node[0].Right;i!=0;i=node[i].Right)
if(vis[i]==0)
{
vis[i]=1;
res++;
for(int j=node[i].Down;j!=i;j=node[j].Down)
for(int k=node[j].Right;k!=j;k=node[k].Right)
vis[node[k].col]=1;
}
return res;
}
void Init_Node(int num)//初始化head和列元素,将其上下左右指针指好,行数和列数可不用初始化
{
for(int i=0;i<=num;i++)
{
node[i].Left=i-1;//左-1
node[i].Right=i+1;//右+1
node[i].Up=i;//上下指向自己
node[i].Down=i;
c_cnt[i]=0;//列个数清空
}
node[0].Left=num;//让head的左边指向最后一个的列元素
node[num].Right=0;//让最后一个的列元素的右边指向head
cnt=num;//更新结点个数
memset(f_row,-1,sizeof(f_row));
res=0;//最大重复覆盖问题
}
void Insert_Node(int x,int y){//插入新节点(按顺序放)
//更新具体值
node[++cnt].row=x;//更新行数
node[cnt].col=y;//更新列数
//先处理该结点的所在列链上的情况
node[cnt].Down=node[y].Down;//更新当前元素的指向下面
node[node[y].Down].Up=cnt;//之前的最后一个元素指向最后
node[cnt].Up=y;
node[y].Down=cnt;
//然后处理该结点的所在行链上的情况
if(f_row[x]<0)//表示该结点是其所在行的第一个元素
{
node[cnt].Left=cnt;//自己指向自己
node[cnt].Right=cnt;//自己指向自己
f_row[x]=cnt;//更新当前行的第一个元素
}
else//表示该结点不是其所在行的第一个元素
{
node[cnt].Right=node[f_row[x]].Right;
node[node[f_row[x]].Right].Left=cnt;
node[cnt].Left=f_row[x];
node[f_row[x]].Right=cnt;
}
c_cnt[y]++;//当前列元素+1
}
//与精准覆盖的差别在于删除、恢复和dance函数
void Remove_Link(int y)//删除该列
{
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
node[node[i].Right].Left=node[i].Left;
node[node[i].Left].Right=node[i].Right;
}
}
void Resume_Link(int y)//恢复该列
{
for(int i=node[y].Up;i!=y;i=node[i].Up)//枚举列链中的元素
{
node[node[i].Right].Left=i;
node[node[i].Left].Right=i;
}
}
void dance(int depth)//depth表示答案的个数(所搜的层数)
{
//注意剪枝的方向改变了
if(f()+depth<=res)//剪枝
return ;
if(node[0].Right==0)//如果head.right=head,说明有解,输出答案
{
res=depth;
return ;
}
int y=node[0].Right;//取列元素y=head.right
for(int i=node[0].Right;i!=0;i=node[i].Right)//剪枝(减少搜索树的分叉)
if(c_cnt[i]<c_cnt[y])
y=i;
for(int i=node[y].Down;i!=y;i=node[i].Down)
{
Remove_Link(i);//注不能是node[i].col
for(int j=node[i].Right;j!=i;j=node[j].Right)
Remove_Link(j);
dance(depth+1);
//先右后左
for(int j=node[i].Left;j!=i;j=node[j].Left)
Resume_Link(j);
Resume_Link(i);
}
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int t;
cin >> t;
while(t--)
{
cin >> n;
for(int i=1;i<=n;i++)
cin >> a[i];
Init_Node(n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
if(a[i]%a[j]==0||a[j]%a[i]==0)
Insert_Node(i,j);
dance(0);
cout << res << endl;
}
return 0;
}
- 二分匹配(正解)
// Problem: 整除
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4240/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-16 21:34:39
//
// Powered by CP Editor (https://cpeditor.org)
/**
* @author : SDTBU_LY
* @version : V1.0.0
* @上联 : ac自动机fail树上dfs序建可持久化线段树
* @下联 : 后缀自动机的next指针DAG图上求SG函数
**/
#include<iostream>
#include<cstring>
#include<algorithm>
#define MAXN 1010
using namespace std;
typedef long long ll;
int t,n;
ll a[MAXN];
int g[MAXN][MAXN];
int vis[MAXN];
int match[MAXN];
int find(int x)
{
for(int i=1;i<=n;i++)
{
if(vis[i]==0&&g[x][i]==1)
{
vis[i]=1;
if(match[i]==0||find(match[i])==1)
{
match[i]=x;
return 1;
}
}
}
return 0;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
cin >> t;
while(t--)
{
cin >> n;
memset(g,0,sizeof(g));
memset(match,0,sizeof(match));
for(int i=1;i<=n;i++)
cin >> a[i];
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
if(a[j]%a[i]==0)
g[i][j]=1;
int res=0;
for(int i=1;i<=n;i++)
{
memset(vis,0,sizeof(vis));
if(find(i)==1)
res++;
}
cout << n-res << endl;
}
return 0;
}