CF1575D Divisible by Twenty-Five 题解

fxwqctb · 2023-10-20 20:14:45 · 题解

本蒟蒻的第一篇题解，请大家笑纳。
感谢管理员大大指出了笔误。

题目传送门

一、题目分析

思路

我们都知道，0 是任何数的倍数，所以 0 要特判。当输入 0、\_、X 的情况，应该先输出 1，并且 return 0 。

因为判断是否为 25 的倍数，只需要判断最后两位，当最后两位为 25、50、75、00 时，这个数就为 25 的倍数。
注意：本题规定所有数字都不能含有前导 0(0 本身除外)。所以当 \text{字符串长度}\le2 时，你需要注意不能有 00 这种情况。

\_ 的可能性

因为要考虑前导 0 的情况，所以我们可以把字符串分为两种。

当 \text{字符串长度}\ge3 时

当 \text{字符串长度}\ge3 时，每一个 \_ 都可以表示 0-9，但是一下情况需要注意。

• 如果 \_ 在最高位，那么它的取值只能为 1-9。
• 如果字符串是以 \_5 结尾，则 \_ 只能为 2 或 7。
• 如果字符串是以 \_0 结尾，则 \_ 只能为 0 或 5。
• 如果字符串是以 5\_ 或 0\_ 结尾，则 \_只能为 0。
• 如果字符串是以 2\_ 或 7\_ 结尾，则 \_只能为 5。
• 如果字符串是以 \_\_结尾，则末尾两位只能为 00、25、50、75。
• 其余情况都为无解。

  当 \text{字符串长度}\le2 时

  当 \text{字符串长度}\le2 时，有一下几种情况。

• 如果字符串是 \_5，则 \_ 只能为 2 或 7。
• 如果字符串是 \_0，则 \_ 只能为 5。
• 如果字符串是 5\_，则 \_只能为 0。
• 如果字符串是 2\_ 或 7\_，则 \_只能为 5。
• 如果字符串是 \_\_ 结尾，则末尾两位只能为 25、50、75。
• 其余情况都为无解。

X 的可能性

因为每一个 X 都表示同一个数字，所以这时你就要考虑最高位的问题。

当 \text{字符串长度}\ge3 时

当 \text{字符串长度}\ge3 时，X 可以表示 0-9，但是一下情况需要注意。

• 如果 X 在最高位，那么它的取值只能为 1-9。
• 如果字符串是以 X5 结尾，则 X 只能为 2 或 7。
• 如果字符串是以 X0 结尾，则 X 只能为 0 或 5，如果 X 为 0，还要考虑最高位。
• 如果字符串是以 5X 或 0X 结尾，则 X只能为 0，并且还要考虑最高位。
• 如果字符串是以 2X 或 7X 结尾，则 X只能为 5。
• 如果字符串是以 XX结尾，则 X只能为 0，并且也要考虑最高位。
• 其余情况都为无解。

  当 \text{字符串长度}\le2 时

  当 \text{字符串长度}\le2 时。

• 如果字符串是 X5，则 X 只能为 2 或 7。
• 如果字符串是 X0，则 X 只能为 5。
• 如果字符串是 5X，则 X只能为 0。
• 如果字符串是 2X 或 7X，则 X只能为 5。
• 如果字符串是 XX，则无解，因为不能出现 00。
• 如果字符串是 X\_ 或 \_X 结尾，则只有 25、50、75 的情况。
• 其余情况都为无解。

二、统计个数

很显然，本题需要统计 X 和 \_ 的数量。
而最高位和最后两位都需要另外统计。

统计字符个数的代码：

char a[10000]={};
cin>>a;
int x=0,y=0;  //x表示字符X的数量，y表示字符_的数量
for(int i=1;i<strlen(a)-2;i++)  //strlen()函数是求字符串的长度
{
    if(a[i]=='X')x++;
    if(a[i]=='_')y++;
}

三、计算数量

而最高位是否为 X 或 \_，需要特殊处理。

int w=0,z=0;//w表示最高位是否为X，z表示最高位是否为_。
if(a[0]=='X')w=1;
if(a[0]=='_')z=1;

当最后两位能够成的数量求出来时，结果也就算出来了，可以推出以下代码。

1/*前面这个数字表示后两位构成的种数*/*(w==1?9:x==0?1:1)/*a?b:c 是三目运算符，若a为真则返回b，否则返回c，前面的三目运算符表示对第一个字符为X的情况特判*/*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y)));//后面的自行理解

四、AC代码

以下是我的完整代码：

#include<bits/stdc++.h> //你熟悉的万能头
using namespace std;
char a[10]={};
int main()
{
    cin>>a;
    if(strlen(a)<=2)  //当a的长度≤2时的情况
    {
        if(strlen(a)==1)
        {
            if(a[0]=='0'||a[0]=='X'||a[0]=='_')cout<<1;  ///特判
            else cout<<0;
            return 0;
        }
        else
        {
            if((a[0]=='2'||a[0]=='7')&&a[1]=='5')cout<<1;
            else if(a[0]=='5'&&a[1]=='0')cout<<1;
            else if(a[0]=='X'&&a[1]=='5')cout<<2;
            else if(a[0]=='_'&&a[1]=='5')cout<<2;
            else if(a[0]=='X'&&a[1]=='0')cout<<1;
            else if(a[0]=='_'&&a[1]=='0')cout<<1;
            else if(a[0]=='X'&&a[1]=='X')cout<<0;
            else if(a[0]=='X'&&a[1]=='_')cout<<3;
            else if(a[0]=='_'&&a[1]=='X')cout<<3;
            else if(a[0]=='_'&&a[1]=='_')cout<<3;
            else if(a[0]=='2'&&a[1]=='X')cout<<1;
            else if(a[0]=='5'&&a[1]=='X')cout<<1;
            else if(a[0]=='7'&&a[1]=='X')cout<<1;
            else if(a[0]=='2'&&a[1]=='_')cout<<1;
            else if(a[0]=='5'&&a[1]=='_')cout<<1;
            else if(a[0]=='7'&&a[1]=='_')cout<<1;
                                        //所有情况
            else cout<<0;
        }
        return 0;
    }
    int x=0,y=0,w=0,z=0;//X个数、_个数、第一位是否为X、第一位是否为_
    for(int i=1;i<strlen(a)-2;i++)
    {
        if(a[i]=='X')x++;
        if(a[i]=='_')y++;
                //统计X和_的个数
    }
    if(a[0]=='0')//以0开头的情况
    {
        cout<<0;
        return 0;
    }
    if(a[0]=='X')w=1;
    if(a[0]=='_')z=1;
    if(a[strlen(a)-1]=='5')
    {
        if(a[strlen(a)-2]=='2'||a[strlen(a)-2]=='7')cout<<(w==1?9:x==0?1:10)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y)));
        else if(a[strlen(a)-2]=='X')cout<<(long long int)(2*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y))));
        else if(a[strlen(a)-2]=='_')cout<<(long long int)(2*(w==1?9:x==0?1:10)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y))));
        else cout<<0;
    }
    else if(a[strlen(a)-1]=='0')
    {
        if(a[strlen(a)-2]=='5'||a[strlen(a)-2]=='0')cout<<(w==1?9:x==0?1:10)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y)));
        else if(a[strlen(a)-2]=='X')cout<<(long long int)(((w==1)?1:2)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y))));
        else if(a[strlen(a)-2]=='_')cout<<(long long int)(2*(w==1?9:x==0?1:10)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y))));
        else cout<<0;
    }
    else if(a[strlen(a)-1]=='X')
    {
        if(a[strlen(a)-2]=='X')cout<<((w==1)?0:1)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y)));
        else if(a[strlen(a)-2]=='_')cout<<(long long int)(((w==1)?2:4)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y))));
        else if(a[strlen(a)-2]=='2'||a[strlen(a)-2]=='7')cout<<(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y)));
        else if(a[strlen(a)-2]=='5'||a[strlen(a)-2]=='0')cout<<((w==1)?0:1)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y)));
        else cout<<0;
    }
    else if(a[strlen(a)-1]=='_')
    {
        if(a[strlen(a)-2]=='X')cout<<(long long int)(((w==1)?3:4)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y))));
        else if(a[strlen(a)-2]=='_')cout<<(long long int)(4*(w==1?9:x==0?1:10)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y))));
        else if(a[strlen(a)-2]=='2'||a[strlen(a)-2]=='5'||a[strlen(a)-2]=='7'||a[strlen(a)-2]=='0')cout<<(long long int)((w==1?9:x==0?1:10)*(z==1?9*((y==0)?1:(pow(10,y))):(y==0?1:pow(10,y))));
        else cout<<0;
    }
    else cout<<0;
                            //以上是所有情况
    return 0;
}

END