題解：
有一種彩票，共有n個數字，其中r個為獲獎數字，每張彩票上選擇m個不同數字，若m個數字鐘包含r個獲獎數字則獲獎。問至少要買多少彩票彩能保證獲獎。其中n>=m>=r。舉例：n=6,m=3,r=2。隻用買6張彩票即可。{1,2,3}，{1,4,5}，{1,3,6}，{2,4,6}，{2,5,6}，{3,4,5}。
題解：
就拿上述的6,3,2來說，買{1,2,3}，那麼保證了{1,2},{2,3},{1,3}是獎勵數字的時候會獲獎，那麼題目就可以找出所有彩票的對應可達獲獎數字。之後就能發現這是一個精确覆寫問題，用DLX算法。其中每清單示獲獎的可能數字，行表示彩票上的可能數字。由于列元素可以重複出現，是以是一個變形的精确覆寫（每列可以被覆寫多次）雖然1<=r<=m<=n<=8，但将所有情況都弄出來需要耗大量時間，是以需要用打表的方式解決。
在正常的DLX算法+A*算法的思想剪枝（就是判斷在目前情況下到符合情況至少需要的次數），耗時需要20分鐘左右。。怎麼看出題人都是在坑人
。之後将所有情況打表輸出即可。
打表耗時：
AC代碼：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cctype>
#include <ctime>
using namespace std;
int ans[8][8][8]={
{
{1}
},
{
{2},
{1,1}
},
{
{3},
{2,3},
{1,1,1}
},
{
{4},
{2,6},
{2,3,4},
{1,1,1,1}
},
{
{5},
{3,10},
{2,4,10},
{2,3,4,5},
{1,1,1,1,1}
},
{
{6},
{3,15},
{2,6,20},
{2,3,6,15},
{2,3,4,5,6},
{1,1,1,1,1,1}
},
{
{7},
{4,21},
{3,7,35},
{2,5,12,35},
{2,3,5,9,21},
{2,3,4,5,6,7},
{1,1,1,1,1,1,1}
},
{
{8},
{4,28},
{3,11,56},
{2,6,14,70},
{2,4,8,20,56},
{2,3,4,7,12,28},
{2,3,4,5,6,7,8},
{1,1,1,1,1,1,1,1}
}
};
int main()
{
int n,m,r,T,tt=0;
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&r);
printf("Case #%d: %d\n",++tt,ans[n-1][m-1][r-1]);
}
return 0;
}
打表代碼：
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <queue>
#include <map>
#include <set>
#include <vector>
#include <cctype>
#include <ctime>
using namespace std;
const int maxn=100;
const int maxnode=1000;
const int maxr=100;
const int INF=1e9;
struct DLX{
int n,sz; //列數，結點總數
int S[maxn]; //各列結點數
int row[maxnode],col[maxnode]; //各結點行列編号
int L[maxnode],R[maxnode],U[maxnode],D[maxnode];//十字連結清單
int ansd,ans[maxr]; //解
int vis[maxn]; //A*算法時标記求過的列
void init(int n)
{
this->n=n;
//虛拟結點
for(int i=0;i<=n;i++)
{
U[i]=i;D[i]=i;L[i]=i-1;R[i]=i+1;
}
R[n]=0;L[0]=n;
sz=n+1;
memset(S,0,sizeof(S));
ansd=INF;
}
void addRow(int r,vector<int>columns)
{
int first=sz;
for(int i=0;i<columns.size();i++)
{
int c=columns[i];
L[sz]=sz-1;R[sz]=sz+1;D[sz]=c;U[sz]=U[c];
D[U[c]]=sz;U[c]=sz;
row[sz]=r;col[sz]=c;
S[c]++;sz++;
}
R[sz-1]=first;L[first]=sz-1;
}
//順着連結清單A，周遊除s外的其他元素
#define FOR(i,A,s) for(int i=A[s];i!=s;i=A[i])
void remove(int c)
{
FOR(i,D,c)
{
L[R[i]]=L[i];
R[L[i]]=R[i];
}
}
void restore(int c)
{
FOR(i,U,c)
{
L[R[i]]=i;
R[L[i]]=i;
}
}
int A()//A*思想，求出要找到結果至少還要選擇的行數
{
int i,j,k,res=0;
memset(vis,0,sizeof(vis));
FOR(i,R,0)
{
if(!vis[i])
{
res++;
vis[i]=1;
FOR(j,D,i)
FOR(k,R,j)
vis[col[k]]=1;
}
}
return res;
}
//d為遞歸深度
void dfs(int d)
{
if(R[0]==0) //找到解
{
ansd=min(ansd,d); //記錄解得長度
return ;
}
if(d+A()>=ansd)return ;
//找S最小的列c
int c=R[0]; //第一個為删除的列
FOR(i,R,0)if(S[i]<S[c])c=i;
//remove(c); //删除第c列
FOR(i,D,c) //用結點i所在行覆寫第c列
{
remove(i);
FOR(j,R,i)remove(j); //删除結點i所在行能覆寫的所有其他列
dfs(d+1);
FOR(j,L,i)restore(j); //恢複結點i所在行能覆寫的所有其他列
restore(i);
}
//restore(c); //恢複第c列
}
int solve()
{
dfs(0);
if(ansd==INF)return 0;
return ansd;
}
}dlx;
vector<int>row[maxr];
vector<int>v;
int c[10][10];
int vis[1025];
int bitcount[1025];
int get(int x)
{
int ans=0;
while(x)
{
ans+=(x&1);
x=x>>1;
}
return ans;
}
void init()
{
int i,j,k;
memset(c,0,sizeof(c));
c[0][0]=1;
for(i=1;i<=8;i++)
{
c[i][0]=1;
for(j=1;j<=i;j++)
c[i][j]=c[i-1][j]+c[i-1][j-1];
}
for(i=0;i<(1<<8);i++)
{
bitcount[i]=get(i);
}
}
int main()
{
freopen("D:\\in.txt","r",stdin);
freopen("D:\\out.txt","w",stdout);
double a = clock();
init();
int n,m,r;
while(scanf("%d%d%d",&n,&m,&r)!=EOF)
{
int i,j,k,t=0;
dlx.init(c[n][r]);
memset(vis,0,sizeof(vis));
for(i=1,k=0;i<(1<<n);i++)
{
if(bitcount[i]==r)vis[i]=++k;
}
for(i=1;i<=c[n][m];i++)
{
row[i].clear();
}
for(i=1;i<(1<<n);i++)
{
if(bitcount[i]==m)
{
t++;
for(j=i;j;j=(j-1)&i)
{
if(bitcount[j]==r)
row[t].push_back(vis[j]);
}
dlx.addRow(t,row[t]);
}
}
printf("%d %d %d:%d\n",n,m,r,dlx.solve());
}
double b = clock();
printf("%lf\n", (b - a) / CLOCKS_PER_SEC); //運作時間
return 0;
}