题目链接：点击打开链接
题意：
给出长度为n的2个数字串S ,T（有些位置为?表示可以随便填数字）
求：有多少种填充方式使得 S[i]>T[i] && S[j] <T[j]
思路：
先求出ans表示所有填充方式，，ans = 10^num, num为2个串?的总个数
dp[0][i]表示长度为i 且对于任意的 j( 1<=j<=i)满足 S[j]<=T[j] 的填充方案数
dp[1][i] 表示 S[j]==T[j]
dp[2[i] 表示 S[j]>=T[j]
则答案= ans – dp[0][n] – dp[1][n] + dp[2][n];
#include<bits/stdc++.h>const int inf = 1e8;const double eps = 1e-8;const double pi = acos(-1.0);const int mod = 1e9+7;template <class T> inline bool rd(T &ret) {char c; int sgn;if(c=getchar(),c==EOF) return 0;while(c!='-'&&(c<'0'||c>'9')) c=getchar();sgn=(c=='-')?-1:1;ret=(c=='-')?0:(c-'0');while(c=getchar(),c>='0'&&c<='9') ret=ret*10+(c-'0');ret*=sgn;return 1; } template <class T> inline void pt(T x) {if (x <0) { putchar('-');x = -x; }if(x>9) pt(x/10);putchar(x%10+'0'); }using namespace std;typedef long long ll;typedef pair<int,int> pii;const int N = 1e5+10;int n;char s[2][N];ll dp[3][N];void mul(ll &x, ll y){x = (x*y)%mod;}void add(ll &x, ll y){x = (x+y)%mod;}int main(){while(cin>>n){scanf("%s", s[0]+1);scanf("%s", s[1]+1);ll ans = 1;for(int i = 0; i < 3; i++)dp[i][0] = 1;ll a, b, c;for(int i = 1; i <= n; i++){if(s[0][i] == '?' && s[1][i] == '?'){a = c = 45; b = 10;mul(ans, 100);}else if(s[0][i] == '?'){mul(ans, 10);a = s[1][i]-'0';b = 1;c = 9-a;}else if(s[1][i] == '?'){mul(ans, 10);c = s[0][i]-'0';b = 1;a = 9-c;}else {a = s[0][i]<s[1][i];b = s[0][i]==s[1][i];c = s[0][i]>s[1][i];}dp[0][i] = dp[0][i-1]*(a+b)%mod;dp[1][i] = dp[1][i-1]*b%mod;dp[2][i] = dp[2][i-1]*(b+c)%mod;}ans -= dp[0][n];ans -= dp[2][n];ans += dp[1][n];ans %= mod;if(ans<0)add(ans, mod);pt(ans%mod); puts("");}return 0;}
旁观者的姓名永远爬不到比赛的计分板上。
