题目链接：http://acm.hnu.cn/online/?action=problem&type=show&id=12813&courseid=267
解题思路：DP，数位DP，比赛时候太蠢写了个187行的DP，结果一看标程37行，给跪。
解题代码：
这是标程
1 #include <cstdio> 2 #include <cstdlib> 3 #include <cstring> 4 #include <algorithm> 5 #include <iostream> 6 #include <cmath> 7 #include <queue> 8 #include <map> 9 #include <stack> 10 #include <list> 11 #include <vector> 12 using namespace std; 13 #define LL __int64 14 const LL M=1e9+7; 15 char s1[1010],s[1010],s2[1010]; 16 LL dp[100][3]; 17 int main() 18 { 19 // freopen("in.txt","r",stdin); 20 // freopen("out.txt","w",stdout); 21 while (gets(s)) 22 { 23 memset(dp,0,sizeof(dp)); 24 if (s[0]=='0') break; 25 gets(s1);gets(s2); 26 int l=strlen(s); 27 dp[l][0]=1; 28 for (int i=l-1;i>=0;i--) // 从右到左第几位 29 for (int p=0;p<2;p++) // p表示是否进位0,1 30 if (dp[i+1][p]>0) //表示上一位是否存在 31 for (int j=0;j<10;j++) // 假设s上i位的数字是j 32 { 33 if (i==0 && j==0) continue; //最高位不能为0 34 if (s[i]=='?' || s[i]-'0'==j) 35 for (int k=0;k<10;k++) //假设s1上的i位数字是k 36 { 37 if (i==0 && k==0) continue; 38 if (s1[i]=='?' || s1[i]-'0'==k) 39 if (s2[i]=='?' || s2[i]-'0'==(j+k+p)%10) 40 dp[i][(j+k+p)/10]=(dp[i][(j+k+p)/10]+dp[i+1][p])%M; 41 } 42 } 43 cout<<dp[0][0]<<endl; 44 } 45 return 0; 46 }
下面是我蠢代码
1 // File Name: b.cpp 2 // Author: darkdream 3 // Created Time: 2014年07月19日 星期六 12时59分09秒 4 5 #include<vector> 6 #include<list> 7 #include<map> 8 #include<set> 9 #include<deque> 10 #include<stack> 11 #include<bitset> 12 #include<algorithm> 13 #include<functional> 14 #include<numeric> 15 #include<utility> 16 #include<sstream> 17 #include<iostream> 18 #include<iomanip> 19 #include<cstdio> 20 #include<cmath> 21 #include<cstdlib> 22 #include<cstring> 23 #include<ctime> 24 #define LL long long 25 26 using namespace std; 27 28 char a[200]; 29 char b[200]; 30 char c[200]; 31 int ia[200]; 32 int ib[200]; 33 int ic[200]; 34 int len ; 35 void change() 36 { 37 for(int i= 0 ;i < len ;i ++) 38 { 39 if(a[i] == '?') 40 { 41 ia[len-i] = 11; 42 }else{ 43 ia[len-i] = a[i]-'0'; 44 } 45 } 46 for(int i= 0 ;i < len ;i ++) 47 { 48 if(b[i] == '?') 49 { 50 ib[len-i] = 11; 51 }else{ 52 ib[len-i] = b[i]-'0'; 53 } 54 } 55 for(int i= 0 ;i < len ;i ++) 56 { 57 if(c[i] == '?') 58 { 59 ic[len-i] = 11; 60 }else{ 61 ic[len-i] = c[i] -'0'; 62 } 63 } 64 65 } 66 LL sdp[12][12][12]; 67 LL sdp1[12][12][12]; 68 LL adp[12][12][12]; 69 LL adp1[12][12][12]; 70 void init() 71 { 72 memset(sdp,0,sizeof(sdp)); 73 memset(adp,0,sizeof(adp)); 74 memset(adp1,0,sizeof(adp1)); 75 memset(sdp1,0,sizeof(sdp1)); 76 for(int i = 0 ;i <= 9 ;i ++) 77 for(int j = 0 ;j <= 9 ;j ++) 78 { 79 if(i +j <= 9) 80 { 81 int t = i + j ; 82 sdp[11][11][11] ++; 83 sdp[11][11][j] ++; 84 sdp[11][i][11] ++; 85 sdp[11][i][j] ++; 86 sdp[t][11][11] ++ ; 87 sdp[t][11][j] ++; 88 sdp[t][i][11] ++; 89 sdp[t][i][j]++; 90 } 91 if(i + j > 9) 92 { 93 int t = (i+j) % 10 ; 94 sdp1[11][11][11] ++; 95 sdp1[11][11][j] ++; 96 sdp1[11][i][11] ++; 97 sdp1[11][i][j] ++; 98 sdp1[t][11][11] ++ ; 99 sdp1[t][11][j] ++; 100 sdp1[t][i][11] ++; 101 sdp1[t][i][j]++; 102 } 103 if(i+j+1 <= 9) 104 { 105 int t = i + j + 1; 106 adp[11][11][11] ++; 107 adp[11][11][j] ++; 108 adp[11][i][11] ++; 109 adp[11][i][j] ++; 110 adp[t][11][11] ++ ; 111 adp[t][11][j] ++; 112 adp[t][i][11] ++; 113 adp[t][i][j]++; 114 } 115 if(i+j+1 > 9){ 116 int t = (i+j+1) % 10 ; 117 adp1[11][11][11] ++; 118 adp1[11][11][j] ++; 119 adp1[11][i][11] ++; 120 adp1[11][i][j] ++; 121 adp1[t][11][11] ++ ; 122 adp1[t][11][j] ++; 123 adp1[t][i][11] ++; 124 adp1[t][i][j]++; 125 } 126 } 127 } 128 LL dp[200][3]; 129 #define M 1000000007 130 LL lenans(int a, int b, int c,int t) 131 { 132 LL sum = 0 ; 133 // printf("%d %d %d %d ",a,b,c,t); 134 for(int i = 1;i <= 9;i ++) 135 { 136 if(i == a || a == 11) 137 for(int j = 1;j <= 9 ;j ++ ) 138 { 139 if((j == b || b == 11)) 140 { if(i +j + t<= 9 && (i+j+t == c || c == 11)) 141 sum ++ ; 142 143 // printf("%d %d %d %d ",i,j,i+j+t,c); 144 } 145 } 146 } 147 // printf("%lld ",sum); 148 return sum; 149 } 150 int main(){ 151 init(); 152 while(scanf("%s",a) != EOF) 153 { 154 if( a[0] == '0' ) 155 break; 156 scanf("%s %s",b,c); 157 len = strlen(a); 158 change(); 159 // 1 not 160 // 2 yes 161 // for(int i =1 ;i <= len ;i ++) 162 // printf("%d ",ic[i]); 163 // printf(" "); 164 memset(dp,0,sizeof(dp)); 165 dp[0][1] = 1; 166 dp[0][2] = 0; 167 for(int i = 1;i <= len ;i ++) 168 { 169 int ta,tb,tc; 170 tc = ic[i]; 171 ta = ia[i]; 172 tb = ib[i]; 173 if(i != len ) 174 { 175 dp[i][1] = (dp[i-1][1]*sdp[tc][ta][tb] % M + dp[i-1][2]*adp[tc][ta][tb] %M) % M; 176 dp[i][2] = (dp[i-1][1]*sdp1[tc][ta][tb] % M + dp[i-1][2]*adp1[tc][ta][tb] %M) % M; 177 }else{ 178 dp[i][1] = (dp[i-1][1]*lenans(ta,tb,tc,0) % M + dp[i-1][2]*lenans(ta,tb,tc,1)% M)% M; 179 } 180 // printf("%lld %lld ",dp[i][1],dp[i][2]); 181 } 182 printf("%lld ",dp[len][1]); 183 // printf("%lld",sdp[11][11][11]); 184 } 185 186 return 0; 187 }