自动搬运

查看原文

来自洛谷，原作者为

	wpy233 你弱归你弱，py比你弱。 stO 所有关注我的巨佬 Orz

搬运于2025-08-24 22:15:00，当前版本为作者最后更新于2019-12-28 14:48:11，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

（前言）

$14:11$，偶打开电脑，看见有 巨佬 已经狂切了$4$题……

蒟蒻我顿时被吓晕了……然后发现比赛时间推前了一个小时……

正文开始

作为一场unRating比赛的$T1$，这道题目真的是印证了比赛描述中的那段话：

比赛良心！没有毒瘤模拟题！没有毒瘤数据结构题！
尤！其！是！没有毒瘤的数学推公式题！
无论你是小学六年级还是高中生，都有足够的数学功底 A 掉前 4 题！

---

题意简述

给你一个密码，每个字符位置上都有$v_i$种选择。

而且，现在有一些组合是已经尝试过的（不必再尝试一遍，同一种组合只会试一次），问还要多少次才能试出密码。

题目分析

让我们对 『题意简述』 里的话来逐句翻译。

---

给你一个密码，每个字符位置上都有$v_i$种选择。

即：一共要尝试$v_1 v_2 v_3 ... v_n$次。

为什么呢？因为你可以是第一次尝试成功，第二次尝试成功，第三次尝试成功……第$v_1 v_2 v_3 ... v_n$次尝试成功。由于题目中是“最少”多少次，所以你必须把你自己看得非常倒霉→_→（虽然这种情况出现的可能性很小）

---

而且，现在有一些组合是已经尝试过的（不必再尝试一遍，同一种组合只会试一次），

即：若$d$字符串上的第$i$位都是第$i$位的$v_i$种选择之一，我们就可以$ans--$（因为每种选择互不相同）

举个例子：
现在密码有2位。
第一位的可能性有：0123
第二位的可能性有：2345
即：ans=4*4=16.
而：给出的有2种尝试：
12
36
第一种：第一位1在可能的尝试中出现了，第二位2在可能的尝试中也出现了，所以ans--，ans变为15.
第二种：第一位3在可能的尝试中出现了，第二位6在可能的尝试中没有出现。所以ans不变。ans仍为15.
所以最终答案是15.

---

代码实现

对于答案不是$-1$的情况：

我们可以将每个字符可能出现的情况都存下来。每输入一个$d_i$就将$d_i$的每一位都判断一遍。如果每一位都在给定的尝试范围以内就$ans--$。最后输出。

对于答案是$-1$的情况：

边输入边判断一遍。如果每一位给定的尝试范围中都没有给定的密码的那一位，输出$-1$然后return 0即可。

注意$ans$的范围

一开始我以为每一位都是$1$~$9$中的任意一个，每位只有$9$种可能。这样算，答案最大为

$9^{18}=150,094,635,296,999,121<9,223,372,036,854,775,807$

然后发现，每一位都可以取$0$~$9$中共$10$个数……

然后long long还没爆？QAQ？

所以窝为什么要开unsigned long long？？？

脑抽现场

吐槽

样例强？！

一开始我在代码中把true和false写反了……

结果还是跑过了四个样例？？？你们确定这样例强度够高？？？能查出低级错误？？？

AC代码放心抄

#include <bits/stdc++.h>//I love 万能头
using namespace std;
int n,k;
int a[19];
bool b[19][10];//定义
unsigned long long ans=1;//貌似只要long long……
int main()
{
	cin>>n>>k;//输入
	string mima;
	cin>>mima;//密码
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];//输入第i位可能的情况
		bool flag=false;//定义标记变量
		for(int j=1;j<=a[i];j++)
		{
			char t;
			cin>>t;//输入第i位的第j种可能
			if(t==mima[i-1]) flag=true;//如果这种情况与密码的第i位相同就标记成可能
			b[i][t-48]=true;//标记第i位第j种可能尝试
		}
		if(!flag)//没有？？？
		{
			cout<<-1<<endl;
			return 0;//直 接 歇 菜
		}
		ans*=a[i];//排列组合
	}
	string p;
	for(int i=1;i<=k;i++)//判断尝试的密码是否符合要求
	{
		cin>>p;//输入第i个尝试的字符串
		bool flag=true;//定义标记变量
		for(int j=0;j<n;j++)
			if(!b[j+1][p[j]-48])//第j+1位没有在给定的尝试中出现过？！
			{
				flag=false;
				break;//歇 菜 + 1
			}
		if(flag) ans--;//是尝试的组合之一，答案-1
	}
	cout<<ans<<endl;//输出
	return 0;//完结撒花
}

提交……

Waiting……

Judging……

Accepted 100分

欧 耶