洛谷 CF1743APassword 题解-Toy模板网

这篇具有很好参考价值的文章主要介绍了洛谷 CF1743APassword 题解。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目

链接

https://www.luogu.com.cn/problem/CF1743A

字面描述

Password

题面翻译

已知一个长度为四的，只包含字符 $0,1,2,\dots ,9$ 的字符串中不会出现哪些字符，求可能的字符串的数量。

题目描述

Monocarp has forgotten the password to his mobile phone. The password consists of $ 4 $ digits from $ 0 $ to $ 9 $ (note that it can start with the digit $ 0 $ ).

Monocarp remembers that his password had exactly two different digits, and each of these digits appeared exactly two times in the password. Monocarp also remembers some digits which were definitely not used in the password.

You have to calculate the number of different sequences of $ 4 $ digits that could be the password for Monocarp’s mobile phone (i. e. these sequences should meet all constraints on Monocarp’s password).

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 200 $ ) — the number of testcases.

The first line of each testcase contains a single integer $ n $ ( $ 1 \le n \le 8 $ ) — the number of digits for which Monocarp remembers that they were not used in the password.

The second line contains $ n $ different integers $ a_1, a_2, \dots a_n $ ( $ 0 \le a_i \le 9 $ ) representing the digits that were not used in the password. Note that the digits $ a_1, a_2, \dots, a_n $ are given in ascending order.

输出格式

For each testcase, print one integer — the number of different $ 4 $ -digit sequences that meet the constraints.

样例 #1

样例输入 #1

2
8
0 1 2 4 5 6 8 9
1
8

样例输出 #1

6
216

提示

In the first example, all possible passwords are: “3377”, “3737”, “3773”, “7337”, “7373”, “7733”.

思路

很简单，就是枚举文章来源地址https://www.toymoban.com/news/detail-418919.html

代码实现

#include<bits/stdc++.h>
using namespace std;

const int maxn=20;
int t,n,x,ans;
int cnt[maxn];
int main(){
	scanf("%d",&t);
	while(t--){
		memset(cnt,0,sizeof(cnt));
		ans=0;
		scanf("%d",&n);
		for(int i=1;i<=n;i++){
			scanf("%d",&x);
			cnt[x]=-1;
		}
		for(int i=0;i<=9;i++){
			if(cnt[i]==-1)continue;
			++cnt[i];
			for(int j=0;j<=9;j++){
				if(cnt[j]==-1)continue;
				++cnt[j];
				for(int k=0;k<=9;k++){
					if(cnt[k]==-1)continue;
					++cnt[k];
					for(int l=0;l<=9;l++){
						if(cnt[l]==-1)continue;
						++cnt[l];
						bool flag=true;
						int tot=0;
						for(int p=0;p<=9;p++){
							if(cnt[p]==0)continue;
							else if(cnt[p]==-1)continue;
							else if(cnt[p]==2)++tot;
							else {
								flag=false;
								break;
							}
						}
						--cnt[l];
						if(!flag||tot!=2)continue;
						//printf("go\n");
						++ans;
					}
					--cnt[k];
				}
				--cnt[j];
			}
			--cnt[i];
		}
		printf("%d\n",ans);
	}
	return 0;
}