SWEET round3 T1题解

· · 题解

（前言）

蒟蒻我顿时被吓晕了……然后发现比赛时间推前了一个小时…… ## 正文开始 作为一场`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分

欧 耶