1 条题解

  • 0
    @ 2025-5-27 13:13:39

    解决思路

    这个问题的核心在于计算有多少种方式可以将a中的问号替换为数字,使得最终的数字字符串a大于字符串b。我们可以通过以下步骤来解决:

    1. 遍历字符串:逐个字符比较a和b的对应位置。
    2. 处理确定字符:当a的当前字符不是问号时,直接比较:
      • 如果a[i] > b[i],则后面的问号可以任意填充(每个有10种可能),直接计算总数并结束。
      • 如果a[i] < b[i],则无论后面怎么填充都无法使a大于b,直接结束。
    3. 处理问号字符:当遇到问号时,计算该位置填充大于b[i]的数字时的可能性,并递归考虑剩余问号的可能性。

    算法分析

    • 时间复杂度:O(n),其中n是字符串的长度。我们只需要遍历字符串一次。
    • 空间复杂度:O(1),只使用了常数级别的额外空间。

    代码

    #include<iostream>
    #include<cstring>
    #include<cstdio>
    #include<cmath>
    using namespace std;
    
    // 计算a的b次方
    long long power(long long a,long long b) {
        long long ans=1;
        for(int i=1;i<=b;i++) ans *=a;
        return ans;
    }
    
    int main() {
        char a[20],b[20];
        while(scanf("%s",a)==1&&strcmp(a,"#")!=0) {
            scanf("%s",b);
            int cur=0,sum=0; // cur:当前已处理的问号数,sum:总问号数
            long long ans=0;
            
            // 计算总问号数
            for(int i=0;a[i];i++) if(a[i]=='?') sum++;
            
            for(int i=0;a[i];i++) {
                if(a[i]!='?') {
                    // 非问号字符直接比较
                    if(a[i]>b[i]) {
                        ans += power(10,sum-cur); // 后面问号可以任意填
                        break;
                    }
                    else if(a[i]<b[i]) break; // 无法满足条件
                }
                else if(a[i]=='?') {
                    cur++;
                    // 当前问号填大于b[i]的数字有(9-(b[i]-'0'))种可能
                    // 后面还有(sum-cur)个问号可以任意填
                    ans += power(10,sum-cur)*(9-(b[i]-'0'));
                }
            }
            printf("%lld\n",ans);
        }
        return 0;
    }
    
    • 1

    信息

    ID
    2341
    时间
    1000ms
    内存
    256MiB
    难度
    5
    标签
    递交数
    2
    已通过
    1
    上传者