$$\color{Purple}{kuangbin题解目录}$$
描述
有一种彩票,购买和获奖规则如下。
每张彩票在购买时,需要你从 $1 \\sim N$ 中挑选 $M$ 个不同的数字,并将它们印到彩票上。
在开奖时,举办方从 $1 \\sim N$ 中挑选 $R$ 个不同的数字作为获奖数字,如果这 $R$ 个数字都出现在了一张彩票上,则该彩票中奖。
给定 $N,M,R$,请你判断至少要买多少张彩票,才能确保自己一定中奖。
输入格式
第一行包含整数 $T$,表示共有 $T$ 组测试数据。
每组数据占一行包含三个整数 $N,M,R$。
输出格式
每组数据输出一个结果,每个结果占一行。
结果表示为 Case #x: y
,其中 $x$ 是组别编号(从 $1$ 开始),$y$ 表示所需购买的彩票最少数量。
数据范围
$1 \\le R \\le M \\le N \\le 8$
输入样例:
3
2 1 1
2 2 1
2 2 2
输出样例:
Case #1: 2
Case #2: 1
Case #3: 1
思路
- 用
重复覆盖问题
的做法解决,但是过不了的(经典毒瘤题),不得不打表AC
- 构建的$01$矩阵中,$n$个选$r$个,共有$C_{n}^{r}$种选法,每种选法需要被覆盖,对应于其
纵坐标
;$n$个选$m$ 个,共有$C_{n}^{m}$种选法,每种选法对应其横坐标
.- 然后套用
舞蹈链板子
即可.
代码
- $Dancing\ Links$($tle$)
// Problem: 一个简单的数学问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/4241/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-17 14:42:56
//
// 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 (10)
#define MAXM 100
#define MAXP 10000
using namespace std;
typedef long long ll;
const int inf=0x3f3f3f3f;
int t;
int n,m,r;
int C[MAXN][MAXN];
int one_cnt[1<<MAXN],num[1<<MAXN];
int lowbit(int x)
{
return x&-x;
}
struct Dancing_Links_Node{
int Up;
int Down;
int Left;
int Right;
int row;//行数
int col;//列数
};
int cnt=0;//记录结点个数
Dancing_Links_Node node[MAXP];
int f_row[MAXM];//记录每行的第一个元素
int c_cnt[MAXM];//每列元素个数
int res;
int vis[MAXM];
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;//更新结点个数
res=inf;
memset(f_row,-1,sizeof(f_row));
}
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);
}
}
void init()
{
for(int i=0;i<MAXN;i++)
{
num[1<<i]=i;
for(int j=0;j<=i;j++)
{
if(j==0)
C[i][j]=1;
else C[i][j]=C[i-1][j]+C[i-1][j-1];
}
}
for(int i=0;i<1<<MAXN;i++)
for(int j=i;j>=1;j-=lowbit(j))
one_cnt[i]++;
}
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
init();
cin >> t;
while(t--)
{
cin >> n >> m >> r;
Init_Node(C[n][r]);
int temp_cnt1=0;
for(int i=1;i<1<<n;i++)
if(one_cnt[i]==m)
{
temp_cnt1++;
int temp_cnt2=0;
for(int j=1;j<1<<n;j++)
if(one_cnt[j]==r)
{
temp_cnt2++;
int flag=1;
for(int k=0;k<n;k++)
if((j>>k&1)&&(i>>k&1)==0)
{
flag=0;
break;
}
if(flag==1)
Insert_Node(temp_cnt1,temp_cnt2);
}
}
dance(0);
cout << "Case #" << (Cas++) << ": " << res << endl;
}
return 0;
}
- 打表
// Problem: 一个简单的数学问题
// Contest: AcWing
// URL: https://www.acwing.com/problem/content/description/4241/
// Memory Limit: 64 MB
// Time Limit: 1000 ms
// Date: 2023-01-17 15:22:26
//
// 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>
using namespace std;
typedef long long ll;
int t;
int n,m,r;
//res[i][j][k]
int res[10][10][10]={//注意计算时下标从0开始
{//i=1
{1},//j=1
},
{//i=2
{2},//j=1
{1,1},//j=2
},
{//i=3
{3},//j=1
{2,3},//j=2
{1,1,1},//j=3
},
{//i=4
{4},//j=1
{2,6},//j=2
{2,3,4},//j=3
{1,1,1,1},//j=4
},
{//i=5
{5},//j=1
{3,10},//j=2
{2,4,10},//j=3
{2,3,4,5},//j=4
{1,1,1,1,1},//j=5
},
{//i=6
{6},//j=1
{3,15},//j=2
{2,6,20},//j=3
{2,3,6,15},//j=4
{2,3,4,5,6},//j=5
{1,1,1,1,1,1},//j=6
},
{//i=7
{7},//j=1
{4,21},//j=2
{3,7,35},//j=3
{2,5,12,35},//j=4
{2,3,5,9,21},//j=5
{2,3,4,5,6,7},//j=6
{1,1,1,1,1,1,1},//j=7
},
{//8
{8},//j=1
{4,28},//j=2
{3,11,56},//j=3
{2,6,14,70},//j=4
{2,4,8,20,56},//j=5
{2,3,4,7,12,28},//j=6
{2,3,4,5,6,7,8},//j=7
{1,1,1,1,1,1,1,1},//j=8
},
};
int main()
{
// ios::sync_with_stdio(false);
// cin.tie(0),cout.tie(0);
int Cas=1;
cin >> t;
while(t--)
{
cin >> n >> m >> r;
cout << "Case #" << (Cas++) << ": " << res[n-1][m-1][r-1] << endl;
}
return 0;
}
跟我的这么像