HDU 4979
A simple math problem.
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 40 Accepted Submission(s): 9
Problem Description
Dragon loves lottery, he will try his luck every week. One day, the lottery company brings out a new form of lottery called accumulated lottery. In a normal lottery, you pick 7 numbers from N numbers. You will get reward according to how many numbers you match. If you match all 7 numbers, you will get the top prize for 1 billion dollars!!! Unlike normal lottery, an M-accumulated lottery allows you to pick M numbers from N numbers. If M is big enough, this may significantly increase your possibility to win. (Of course it cost more…) Some people buy multiple accumulated lotteries to guarantee a higher possibility to get the top prize. Despite of this, it’s still not worthy to guarantee a top prize.Knowing this, Dragon changes his target to second tier prize. To get a second tier prize, you need to contain all of the R numbers with M numbers picked.Given N, M and R, Dragon wants to know how many M-accumulated lotteries he needs to buy, so that he can guarantee that he can get at least the second tier prize.
Input
The first line of input contains only one integer T, the number of test cases. For each case, there’s a single line contains N, M and R(1<=R<=M<=N<=8).
Output
Each output should occupy one line. Each line should start with “Case #i: “, with i implying the case number. For each case, just output the result with no other leading or tailing spaces.
Sample Input
3 2 1 1 2 2 1 2 2 2
Sample Output
Case #1: 2 Case #2: 1 Case #3: 1
Source
2014 Multi-University Training Contest 10
相等在 N个数的组合C(n,m) 中选择最少的个数，覆盖所有 C(n,k)的组合。
可以用Dancing Links的可重复覆盖去搞。 这题比较恶心的就是要打表。 比赛的时候打表一直出不来 8 5 4 这组数据。 于是有了很多狂交80次来猜8 5 4 这个结果的故事。 除了8 5 4其余打表都很快的、。 8 5 4 好像要打好久。 8 5 4 结果其实是 20. AC程序：
/* ***
Author :kuangbin
Created Time :2014/8/21 17:10:33
File Name :09_2.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
int a[] = {
0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,2,0,0,0,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,3,0,0,0,0,0,0,0,0,2,3,0,0,0,0,0,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,4,0,0,0,0,0,0,0,0,2,6,0,0,0,0,0,0,0,2,3,4,0,0,0,0,0,0,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,5,0,0,0,0,0,0,0,0,3,10,0,0,0,0,0,0,0,2,4,10,0,0,0,0,0,0,2,3,4,5,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,6,0,0,0,0,0,0,0,0,3,15,0,0,0,0,0,0,0,2,6,20,0,0,0,0,0,0,2,3,6,15,0,0,0,0,0,2,3,4,5,6,0,0,0,0,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,7,0,0,0,0,0,0,0,0,4,21,0,0,0,0,0,0,0,3,7,35,0,0,0,0,0,0,2,5,12,35,0,0,0,0,0,2,3,5,9,21,0,0,0,0,2,3,4,5,6,7,0,0,0,1,1,1,1,1,1,1,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,8,0,0,0,0,0,0,0,0,4,28,0,0,0,0,0,0,0,3,11,56,0,0,0,0,0,0,2,6,14,70,0,0,0,0,0,2,4,8,0,56,0,0,0,0,2,3,4,7,12,28,0,0,0,2,3,4,5,6,7,8,0,0,1,1,1,1,1,1,1,1,
};
int main()
{
//freopen(“in.txt”,”r”,stdin);
//freopen(“out.txt”,”w”,stdout);
int T;
int iCase = 0;
scanf("%d",&T);
while(T--){
iCase++;
int n,m,r;
scanf("%d%d%d",&n,&m,&r);
if(n == 8 && m == 5 && r == 4){
printf("Case #%d: 20\\n",iCase);
continue;
}
printf("Case #%d: %d\\n",iCase,a\[n\*9\*9+m*9+r\]);
}
return 0;
}
打表程序：
/* ***
Author :kuangbin
Created Time :2014/8/21 16:23:46
File Name :09.cpp
************************************************ */
#include <stdio.h>
#include <string.h>
#include
#include
#include
#include
#include
#include
#include
#include <math.h>
#include <stdlib.h>
#include <time.h>
using namespace std;
const int MaxM = 1515+10+1000;
const int MaxN = 1515+10+1000;
const int maxnode = MaxN * MaxM;
const int INF = 0x3f3f3f3f;
struct DLX
{
int n,m,size;
int U[maxnode],D[maxnode],R[maxnode],L[maxnode],Row[maxnode],Col[maxnode];
int H[MaxN],S[MaxM];
int ansd;
void init(int _n,int _m)
{
n = _n;
m = _m;
for(int i = 0;i <= m;i++)
{
S[i] = 0;
U[i] = D[i] = i;
L[i] = i-1;
R[i] = i+1;
}
R[m] = 0; L[0] = m;
size = m;
for(int i = 1;i <= n;i++)H[i] = -1;
}
void Link(int r,int c)
{
// printf(“%d %d\n”,r,c);
++S[Col[++size]=c];
Row[size] = r;
D[size] = D[c];
U[D[c]] = size;
U[size] = c;
D[c] = size;
if(H[r] < 0)H[r] = L[size] = R[size] = size;
else
{
R[size] = R[H[r]];
L[R[H[r]]] = size;
L[size] = H[r];
R[H[r]] = size;
}
}
void remove(int c)
{
for(int i = D[c];i != c;i = D[i])
L[R[i]] = L[i], R[L[i]] = R[i];
}
void resume(int c)
{
for(int i = U[c];i != c;i = U[i])
L[R[i]] = R[L[i]] = i;
}
bool v[MaxM];
int f()
{
int ret = 0;
for(int c = R[0]; c != 0;c = R[c])v[c] = true;
for(int c = R[0]; c != 0;c = R[c])
if(v[c])
{
ret++;
v[c] = false;
for(int i = D[c];i != c;i = D[i])
for(int j = R[i];j != i;j = R[j])
v[Col[j]] = false;
}
return ret;
}
void Dance(int d)
{
if(d + f() >= ansd)return;
if(R[0] == 0)
{
if(d < ansd)ansd = d;
return;
}
int c = R[0];
for(int i = R[0];i != 0;i = R[i])
if(S[i] < S[c])
c = i;
for(int i = D[c];i != c;i = D[i])
{
remove(i);
for(int j = R[i];j != i;j = R[j])remove(j);
Dance(d+1);
for(int j = L[i];j != i;j = L[j])resume(j);
resume(i);
}
}
};
DLX g;
int a[MaxN];
int b[MaxM];
long long C[20][20];
void init2(){
C[0][0] = 1;
for(int i = 1;i < 20;i++){
C[i][0] = C[i][i] = 1;
for(int j = 1;j < i;j++)
C[i][j] = C[i-1][j] + C[i-1][j-1];
}
}
int main()
{
//freopen(“in.txt”,”r”,stdin);
freopen(“out.txt”,”w”,stdout);
init2();
int T;
int n,m,r;
int iCase = 0;
scanf(“%d”,&T);
//while(T–){
for(n = 0;n < 9;n++)
for(m = 0;m < 9;m++)
for(r = 0;r < 9;r++){
if(n == 0 || m == 0 || r == 0){
printf("0,");
continue;
}
if( !(r <= m && m <= n) ){
printf("0,");
continue;
}
iCase++;
// scanf("%d%d%d",&n,&m,&r);
if(n == 8 && m == 5 && r == 4){
printf("0,");
continue;
}
int cnt1 = 0;
int cnt2 = 0;
for(int i = 0;i < (1<<n);i++){
int cc = 0;
for(int j = 0;j < n;j++)
if(i&(1<<j))
cc++;
if(cc == m)a\[++cnt1\] = i;
if(cc == r)b\[++cnt2\] = i;
}
g.init(cnt1,cnt2);
for(int i = 1;i <= cnt1;i++)
for(int j = 1;j <= cnt2;j++)
if((a\[i\]|b\[j\]) == a\[i\])
g.Link(i,j);
long long tmp = C\[n\]\[r\];
long long tmp2 = C\[m\]\[r\];
g.ansd = tmp;
g.Dance(0);
printf("%d,",g.ansd);
//printf("Case #%d: %d\\n",iCase,g.ansd);
}
// }
return 0;
}
