传送门:HDU3335
【题意】给出n个整数,求一个最大的集合,使得集合中所有数互相不能整除(a%b != 0, b%a != 0);
【分析】网上好多都是二分匹配。在斌神的DLX专题里看到的这题才想到用DLX来做,可是最终还是看了别人的题解才会的;可以以每个数分别建成行列01矩阵,i行j列表示j列能被i整除,则只要求出最大的行能覆盖满所有列即可;由于求可重复覆盖的DLX中会去掉同一列已有1的所有其他行的1,则正好把有冲突的数都去掉了,求出最大行就是最大的集合。
【AC CODE】15ms
#include <cstdio> #include <cstring> #include <cctype> #include <cmath> #include <set> //#include <unordered_set> #include <queue> #include <stack> #include <vector> #include <string> #include <algorithm> using namespace std; typedef long long LL; #define rep(i,a,n) for(int i = a; i < n; i++) #define repe(i,a,n) for(int i = a; i <= n; i++) #define per(i,n,a) for(int i = n; i >= a; i--) #define clc(a,b) memset(a,b,sizeof(a)) const int INF = 0x3f3f3f3f, MAXN = 1000+10, M = MAXN*MAXN; int lt[M],rt[M],up[M],down[M],col[M],tol,cnt[MAXN]; LL a[MAXN]; void init(int maxc) { repe(i,0,maxc) lt[i] = i-1,rt[i] = i+1,up[i] = down[i] = i; lt[0] = maxc,rt[maxc] = 0; tol = maxc+1; clc(cnt,0); } int f() { int ans = 0; for(int c = rt[0];c;c = rt[c]) ans++; return ans; } void remove(int c) { for(int i = down[c]; i != c; i = down[i]) lt[rt[i]] = lt[i], rt[lt[i]] = rt[i], --cnt[col[i]]; } void reset(int c) { for(int i = up[c]; i != c; i = up[i]) lt[rt[i]] = rt[lt[i]] = i, ++cnt[col[i]]; } int mx; void dfs(int d) { if(d+f() <= mx) return; if(!rt[0]) { if(mx < d) mx = d; return; } int c = rt[0]; for(int i = rt[0];i;i = rt[i]) if(cnt[c] > cnt[i]) c = i; for(int i = down[c]; i != c; i = down[i]) { remove(i); for(int j = rt[i]; j != i; j = rt[j]) remove(j); dfs(d+1); for(int j = lt[i]; j != i; j = lt[j]) reset(j); reset(i); } } int main() { #ifdef SHY freopen("d:\\1.txt", "r", stdin); #endif int t; scanf("%d", &t); while(t--) { int n; scanf("%d", &n); repe(i,1,n) scanf("%I64d", &a[i]); init(n); repe(i,1,n) { int ft = tol; repe(j,1,n) { if(a[i]%a[j] == 0 || a[j]%a[i] == 0) { col[tol] = j; lt[tol] = tol-1,rt[tol] = tol+1,up[tol] = up[j], down[tol] = j; down[up[j]] = tol, up[j] = tol; cnt[j]++,tol++; } } if(ft != tol) lt[ft] = tol-1,rt[tol-1] = ft; } mx = 0; dfs(0); printf("%d\n",mx); } return 0; }