题解 | #卡片#

2021 牛客 OI 赛前集训营-普及组(第二场) 卡片题解

非常简单,只需要爆搜！

大致思路;

• 第一步:先写个搜索，从n个数里面选k个数，并把选的数记录下来。 也就是说，可以定义一个$num\left[i\right]num[i]$num[i]表示第i次选择时选择是a数组的第几个数

• 第二步:对你选择的数再搞一个搜索，作用是全排列，然后把你选择数拼(就是题目所说的“排列”）起来，看看你拼的这个数是否跟之前重复。如果没重复，计数器++。

某一些需要注意的细节:

1. 在你拼数的时候，你会发现很难实现（对于我来说），所以我们把a数组定义成$string\backslash rm\; string$string类型，就可以直接加。

实现代码:

string now="";//你把你拼的数放在这个里面
string+= 你要拼的每个数

2. 拼完数后，判断拼的数是否重复看起来也很难实现，那么可以定义一个$mapmap$map

实现代码:

map<string,bool> vis;//如果不懂可以去网上搜
if(vis[now]==0){
  	vis[now]=1;//把他标记成用过的
  	计数器++
}

3. 全排列的话可以参考：这篇博文

综上，完整代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,k;
string a[15];
int ans[1005];
map<string,bool>vis;
int cnt;
void dfs(int i){
	if(i>k){
		int num=1;
		for(int j=1;j<=k;j++){
			num*=j;
		}
		while(num--){
			next_permutation(ans+1,ans+k+1);
			string t="";
			for(int j=1;j<=k;j++){
				t+=a[ans[j]];//拼出来的数 
			} 
			if(vis[t]==0){
				vis[t]=1;
				cnt++;
			}
		}
	}
	for(int j=ans[i-1]+1;j<=n;j++){
		ans[i]=j;
		dfs(i+1);
	}
}
int main(){
	freopen("2.in","r",stdin);
	freopen("2.out","w",stdout);
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
	dfs(1);
	cout<<cnt<<endl;
}

如果不懂，请私信我。

可以给我一个关注吗？