1、 hdoj 2089 不要62
题意： 不吉利数为数中含有4或者62, 单个6或者单个2或者26都不是不吉利数; 求给定区间里的吉利数;
//代码1 ; #include <cstdio> #define MAXN 10 #include <cstring> using namespace std; int dp[MAXN][3]; // dp[i][0] 长度为i, 不含有不吉利数字 <1> // dp[i][1] 长度为i, 不存在不吉利数字, 且最高位为2; <1> // dp[i][2] 长度为i, 含有不吉利数字 <2> void init() { dp[0][0]=1; dp[0][1]=dp[0][2]=0; for(int i=1; i<= 10; i++) { dp[i][0]= dp[i-1][0]*9 - dp[i-1][1]; //在最高位 加上除4以外的9个数字, 但要减去2之前加上6的情况; dp[i][1]= dp[i-1][0]; //在不含不吉利数的最高位加上2 ; dp[i][2]= dp[i-1][2]*10 + dp[i-1][0] + dp[i-1][1]; //在已有不吉利数的最高位加上(1~9)任意数字 + 无不吉利数的最高位加上4 + 2前面加上6; } } int bit[MAXN]; int solve(int n) { int len=0; memset(bit, 0, sizeof(bit)); int tmp=n; while(n) { bit[++len]= n%10; n /= 10; } int ans=0; int flag=0; for(int i=len; i>=1; i--) { ans= ans + bit[i]*dp[i-1][2]; //由上位所有不吉利数推导; (不含前导零, 所以乘以bit[i];); if(flag) ans+= bit[i]*dp[i-1][0]; //之前出现的不吉利数字 ; else { if(bit[i] >4) ans +=dp[i-1][0]; //最高位将会出现4; if(bit[i] >6) ans +=dp[i-1][1]; //i-1长度的最高位已经为2, 6将会加到最高位; if(bit[i+1]== 6 && bit[i] >2) ans +=dp[i][1]; //出现62 ; } if(bit[i+1] ==6&& bit[i]==2) flag =1; if(bit[i]== 4) flag=1; } if(flag) ans++; return tmp-ans; //所有的数减去不吉利数 ; } int main() { int n, m; init(); while(scanf("%d%d", &n, &m) != EOF) { if(!n && !m) break; int ans=solve(m)- solve(n-1); printf("%d ", ans); } return 0; }
//记忆化搜索(不好理解!! ); #include <cstdio> #include <cstring> const int N = 10; using namespace std ; int bit[N]; int dp[N][2];// dp[i][is6] is the number of i-len digits with (if prevent number is 6), its digits are from 0-9 int dfs(int len, bool is6, bool ismax) { if(len==0) return 1; if(!ismax && dp[len][is6] >= 0) return dp[len][is6]; int cnt=0; int Max= ismax? bit[len]: 9; for(int i=0; i<= Max; i++) //枚举数位 ; { if(i==4 || is6 && i == 2) // unluck digit continue; cnt += dfs(len-1, i==6, ismax && i==Max); } return ismax? cnt: dp[len][is6]= cnt; } int solve(int num) { int len=0; while(num) { bit[++len]=num%10; num /= 10; } return dfs(len, false, true); } int main() { int n, m; while(scanf("%d%d", &n, &m) != EOF) { if(!n && !m) break; memset(dp, -1, sizeof(dp)); printf("%d ", solve(m)-solve(n-1)); } return 0; }
2、 hdoj 3555 Bomb
给一个区间中含有49的数的个数, 4, 9必须相邻 ; (神奇的姿势, 找啊找啊找不同)
#include <cstdio> #include <cstring> const int N = 21; typedef long long LL; LL dp[N][3]; //dp[i][0]; 不含49; //dp[i][1]; 最高位为9; //dp[i][2]; 含有49 ; using namespace std; void init() /***/ { dp[0][0]=1; dp[0][1]=0; dp[0][2]=0; for(int i=1; i<=N; i++) { dp[i][0]=dp[i-1][0]*10-dp[i-1][1]; dp[i][1]=dp[i-1][0]; dp[i][2]=dp[i-1][2]*10+dp[i-1][1]; } } int bit[N]; LL solve(LL n) { int len=0; memset(bit, 0, sizeof(bit)); while(n) { bit[++len]=n%10; n /= 10; } bit[len+1]=0; LL ans=0; int flag=0; for(int i=len; i>=1; i--) { ans=ans+bit[i]*dp[i-1][2]; if(flag) ans=ans+ bit[i]*dp[i-1][0]; else { if(bit[i]> 4) ans += dp[i-1][1]; if(bit[i+1]==4 && bit[i]>9) ans += dp[i][1]; } if(bit[i+1]==4 && bit[i]== 9) flag=1; } if(flag) ans++; return ans; } int main() { int t; LL N; init(); scanf("%d", &t); while(t--) { scanf("%lld", &N); printf("%I64d ", solve(N)-solve(0)); } return 0; }
3、UEST Cwindy数
题意: 相邻数位大小<=2的数的个数 ;
#include <cmath> #include <cstdio> #include <cstring> using namespace std; inline int abs(int a){ return a<0? a*(-1):a; } int dp[15][10]; //dp[i][j]表示长度为i, 最高位为j的windy的个数 ; void init() { memset(dp, 0, sizeof(dp)); for(int i=0; i< 10; i++) dp[1][i]=1; for(int i=2; i<=10; i++) for(int j=0; j< 10; j++){ for(int k=0; k<= j-2; k++) //最高位加一位 dp[i][j] += dp[i-1][k]; for(int k=j+2; k<10; k++) dp[i][j] += dp[i-1][k]; } } int bit[20]; int solve(int n){ if(n==0) return 0; int len=0; while(n) { bit[++len]= n%10; n /=10; } bit[len+1]= -10; int ans=0; bool flag= true; for(int i=1; i< len; i++) for(int j=1; j<= 9; j++) ans +=dp[i][j]; for(int j=1; j<bit[len];j++) ans += dp[len][j]; for(int i=len-1; i>= 1; i--) { for(int j=0; j<bit[i]; j++) if(abs(bit[i+1]- j) >= 2) ans+= dp[i][j]; if(abs(bit[i+1]- bit[i])< 2) { flag= false ; break; } } if(flag) ans++; return ans; } int main () { int a, b; init(); while(scanf("%d%d", &a, &b) != EOF) { printf("%d ", solve(b)- solve(a-1)); } return 0; }