ural 1057 Amount of Degrees （数位DP）
详见：刘聪的论文，写的很详细......
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
int f[35][35]; //前 i 位有 j 个 1 的个数...
int x,y,b;
int pos[35];
int len;
void init() { //预处理
memset(f,0,sizeof(f));
f[0][0] = 1;
for(int i=1; i<=32; i++) {
f[i][0] = f[i-1][0];
for(int j=1; j<=i; j++) {
f[i][j] = f[i-1][j-1] + f[i-1][j];
}
}
}
int solve(int t,int k) {
len = 1;
while(t) {
pos[len++] = t % b;
t /= b;
}
int ans = 0;
for(int i=len-1; i>=1; i--) {
if(pos[i] > 1) {
ans += f[i-1][k] + f[i-1][k-1];
break;
} else if(pos[i] == 1) {
ans += f[i-1][k];
k --;
}
if(k < 0) break;
}
return ans;
}
int main() {
init();
int k;
while(scanf("%d%d%d%d",&x,&y,&k,&b) != EOF) {
printf("%d\n",solve(y+1,k) - solve(x,k));
}
return 0;
}
hdu 2089 不要62
题意：找出【x,y】区间内，满足不存在4且不存在62的数的个数
先预处理出前i位，j作为最高位时符合要求的数的个数。然后对于0--n的总个数，从高位到低位，枚举小于n的每一位。
#include <cstdio>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int f[11][11];
int n,m;
int pos[11];
void init() {
memset(f,0,sizeof(f));
f[0][0] = 1;
for(int i=1; i<7; i++) {
for(int j=0; j<=9; j++) {
if(j == 4) continue;
for(int k=0; k<=9; k++) {
if(j == 6 && k == 2) continue;
f[i][j] += f[i-1][k];
}
}
}
}
int solve(int x) {
memset(pos,0,sizeof(pos));
int len = 0;
int flag = 1;
while(x) {
pos[++len] = x % 10;
if(pos[len] == 4 || (pos[len] == 6 && pos[len-1] == 2)) flag = 0;
x /= 10;
}
int ans = 0;
if(flag) ans ++;
for(int i=len; i>=1; i--) {
for(int j=0; j<pos[i]; j++) {
if(j == 4) continue;
if( i < len && pos[i+1] == 6 && j == 2) continue;
ans += f[i][j];
}
if(pos[i] == 4 || (i < len && pos[i+1] == 6 && pos[i] == 2)) break;
}
return ans;
}
int main() {
init();
while(scanf("%d%d",&n,&m)) {
if(n == 0 && m == 0) break;
printf("%d\n",solve(m) - solve(n-1));
}
return 0;
}
递归写法：
int dp[10][3]; int pos[10]; int dfs(int p,int buff,int flag) { if(p == -1) return (buff == 0 || buff == 1); if(flag == 0 && dp[p][buff] != -1) return dp[p][buff]; int ans = 0; int end = flag ? pos[p] : 9; for(int i=0; i<=end; i++) { if(i == 4 || buff == 2 || (i == 2 && buff == 1)) ans += dfs(p-1,2,(flag && i == end)); else if(i == 6) ans += dfs(p-1,1,(flag && i == end)); else ans += dfs(p-1,0,(flag && i == end)); } if(!flag) dp[p][buff] = ans; return ans; } int solve(int x) { int len = 0; while(x) { pos[len++] = x % 10; x /= 10; } return dfs(len - 1,0,1); } int main() { memset(dp,-1,sizeof(dp)); int n,m; while(scanf("%d%d",&n,&m) && (n + m)) { printf("%d\n",solve(m) - solve(n-1)); //printf("%d\n",m - solve(m) - (n - 1 - solve(n - 1))); } return 0; }
hdu 3652 B-number
此题求的是存在连续的‘13’且能被13整除的数的个数
试试递归写法...记忆化dp
#include <iostream> #include <algorithm> #include <cmath> #include <functional> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <climits>//形如INT_MAX一类的 using namespace std; int dp[15][15][15][2]; int pos[15]; int dfs(int p,int pre,int mod,int buff,bool flag) { // p 表示当前处理位置， pre 表示前驱数字， buff 为目标状态（此题包括mod == 0）， flag 表示此位置是否能枚举任意数字 if(p == -1) return (buff && !mod); if(flag == 0 && dp[p][pre][mod][buff] != -1) return dp[p][pre][mod][buff]; int ans = 0; int end = flag ? pos[p] : 9; for(int i=0; i<=end; i++) { if(pre == 1 && i == 3) ans += dfs(p - 1,i,(mod * 10 + i) % 13,1,(flag && i == end)); else ans += dfs(p - 1,i,(mod * 10 + i) % 13,buff,(flag && i == end)); } if(!flag) dp[p][pre][mod][buff] = ans; return ans; } int solve(int n) { int len = 0; while(n) { pos[len++] = n % 10; n /= 10; } return dfs(len - 1,0,0,0,1); } int main() { int n; memset(dp,-1,sizeof(dp)); while(scanf("%d",&n) != EOF) { printf("%d\n",solve(n)); } return 0; }
poj 3252 Round Numbers
在区间【l,r】内的数当二进制表示时，求出满足条件的个数，条件为：0的个数大于等于1的个数。
需要考虑前导0
#include <iostream> #include <algorithm> #include <cmath> #include<functional> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> using namespace std; int pos[40]; int dp[40][40][40]; int len ; int dfs(int p,int num0,int num,int flag,int first) { if(p == -1) { if(num0 >= num) return 1; return 0; } if(flag == 0 && dp[p][num0][num] != -1) return dp[p][num0][num]; int ans = 0; int end = flag ? pos[p] : 1; for(int i=0; i<=end; i++) { if(first) { if(i == 0) ans += dfs(p-1,num0,num,(flag && i == end),1); if(i == 1) ans += dfs(p-1,num0,num + 1,(flag && i == end),0); } else { if(i == 0) ans += dfs(p-1,num0 + 1,num,(flag && i == end),0); if(i == 1) ans += dfs(p-1,num0,num + 1,(flag && i == end),0); } } if(!flag) dp[p][num0][num] = ans; return ans; } int solve(int x) { len = 0; while(x) { pos[len ++] = x % 2; x /= 2; } return dfs(len - 1,0,0,1,1); } int main() { int n,m; memset(dp,-1,sizeof(dp)); // while(scanf("%d",&n) != EOF) { // printf("%d\n",solve(n)); // } scanf("%d%d",&n,&m); printf("%d\n",solve(m) - solve(n-1)); return 0; }hdu 3709 balanced number
在[x,y]区间内求满足条件的数，条件是该数以某一位为轴心，其他位的权值为数位值 * 偏移量 ，要求轴心左边与右边权值和相等。
#include <iostream> #include <algorithm> #include <cmath> #include<functional> #include <cstdio> #include <cstdlib> #include <cstring> #include <string> #include <vector> #include <set> #include <queue> #include <stack> #include <climits>//形如INT_MAX一类的 #define MAX 100005 #define INF 0x7FFFFFFF #define REP(i,s,t) for(int i=(s);i<=(t);++i) #define ll __int64 using namespace std; int pos[20]; ll dp[20][20][2222]; ll dfs(int p,int mid,int sum,int flag) { if(p == -1) return sum == 0; if(sum < 0) return 0; if(flag == 0 && dp[p][mid][sum] != -1) return dp[p][mid][sum]; int end = flag ? pos[p] : 9; ll ans = 0; for(int i=0; i<=end; i++) { ans += dfs(p - 1,mid,sum + (p - mid) * i, (flag && i == end)); } if(!flag) return dp[p][mid][sum] = ans; return ans; } ll solve(ll x) { int len = 0; while(x) { pos[len++] = x % 10; x /= 10; } ll ans = 0; for(int i=0; i<len; i++) { ans += dfs(len-1,i,0,1); } return ans - len + 1; // 减去前导零的情况 } int main() { memset(dp,-1,sizeof(dp)); int T; scanf("%d",&T); ll n,m; while(T--) { scanf("%I64d%I64d",&n,&m); printf("%I64d\n",solve(m) - solve(n-1)); } return 0; }