思路：数位dp ， dp[i][j]表示位数为i且首位数为j的数 符合条件的个数。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #define N 500010 #define INF 10000000 #define LL long long #define eps 10E-9 #define mem(a) memset(a,0,sizeof(a)) #define w(a) while(a) #define s(a) scanf(%d,&a) #define ss(a,b) scanf(%d%d,&a,&b) #define sss(a,b,c) scanf(%d%d%d,&a,&b,&c) #define MAXN 9999 #define MAXSIZE 10 #define DLEN 4 #define MAXN 9999 #define MAXSIZE 10 const int mod=1e9+9; using namespace std; int dp[7][10]; void init(){//初始化打表 mem(dp); dp[0][0]=1; for(int i=1; i<7; i++){ for(int j=0; j<10; j++){ for(int k=0; k<10; k++){ if(j!=4&&!(j==6&&k==2)) dp[i][j] += dp[i-1][k]; } } } } int solve(int n){//返回满足条件且小于n的数的个数 int digit[10]; int len = 0, ans = 0; while(n){ digit[++len]=n%10; n/=10; } digit[len+1]=0;//safety for(int i=len; i; i--){//逐位计算 for(int j=0; j if(j!=4&&!(j==2&&digit[i+1]==6)) ans += dp[i][j]; } if(digit[i]==4||(digit[i]==2&&digit[i+1]==6)) break; } return ans; } int main() { int s,e; init(); w(~ss(s,e)&&(s|e)){ cout< } return 0; }
?