1 条题解
-
0
解决思路
这个问题的核心在于计算有多少种方式可以将a中的问号替换为数字,使得最终的数字字符串a大于字符串b。我们可以通过以下步骤来解决:
- 遍历字符串:逐个字符比较a和b的对应位置。
- 处理确定字符:当a的当前字符不是问号时,直接比较:
- 如果a[i] > b[i],则后面的问号可以任意填充(每个有10种可能),直接计算总数并结束。
- 如果a[i] < b[i],则无论后面怎么填充都无法使a大于b,直接结束。
- 处理问号字符:当遇到问号时,计算该位置填充大于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
- 上传者