题集见

 

入门题，检验刚才自己有没有看懂

注意一些细节。

的确挺套路的

#include
     
      #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 15;int a[MAXN], dp[MAXN][MAXN][MAXN], len; //dp数组记录除了lead和limit以外其他的东西 int dfs(int pos, int pre, int lead, int sum, int limit){    if(pos > len) return sum;    if(dp[pos][pre][sum] != -1 && !limit && !lead) return dp[pos][pre][sum]; //记忆化的时候记得limit和lead     int l = limit ? a[len-pos+1] : 9, res = 0; //注意是倒序存的，所以是len-pos+1    _for(i, 0, l)    {        if(!i && lead) res += dfs(pos + 1, pre, lead, sum, limit && (i == l)); //先看是不是前导0         else if(i && lead) res += dfs(pos + 1, i, 0, sum | (i == 4), limit && (i == l)); //看是不是第一位         else res += dfs(pos + 1, i, 0, sum | (i == 4) | (pre == 6 && i == 2), limit && (i == l)); //正式处理     }    return (!limit && !lead) ? dp[pos][pre][sum] = res : res; //记忆化的时候记得limit和lead }int part(int x){    if(x < 0) return 0; //0的处理     memset(dp, -1, sizeof(dp));    len = 0; int t = x;     for(; x; x /= 10) a[++len] = x % 10;    return t - dfs(1, 0, 1, 0, 1);}int main(){    int n, m;    while(scanf("%d%d", &n, &m))    {        if(n == 0 && m == 0) break;        printf("%d\n", part(m) - part(n - 1));    }    return 0;}
     

 

继续套路

#include
     
      #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 15;int a[MAXN], dp[MAXN][MAXN][MAXN], len;int dfs(int pos, int pre, int ans, int lead, int limit){    if(pos > len) return ans;    if(dp[pos][pre][ans] != -1 && (!limit && !lead)) return dp[pos][pre][ans];    int l = limit ? a[len-pos+1] : 9, res = 0;    _for(i, 0, l)    {        if(!i && lead) res += dfs(pos + 1, pre, ans, lead, limit & (i == l));        else if(i && lead) res += dfs(pos + 1, i, ans, 0, limit & (i == l));        else res += dfs(pos + 1, i, ans & (abs(i - pre) >= 2), 0, limit & (i == l));    }    return (!limit && !lead) ? dp[pos][pre][ans] = res : res;}int part(int x){    if(x == 0) return 1;    memset(dp, -1, sizeof(dp));    len = 0;     for(; x; x /= 10) a[++len] = x % 10;    return dfs(1, 0, 1, 1, 1);}int main(){    int a, b;    scanf("%d%d", &a, &b);     printf("%d\n", part(b) - part(a - 1));    return 0;}
     

 

第一次这么轻松做出紫题

一样套模板，爽啊

#include
     
      #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;typedef long long ll;const int MAXN = 20;const int MAXM = 1e6 + 10;ll dp[MAXN][MAXN];int a[MAXN], len;ll dfs(int pos, int ans, int lead, int limit, int key){    if(pos > len) return ans;    if(dp[pos][ans] != -1 && (!lead && !limit)) return dp[pos][ans];    int l = limit ? a[len-pos+1] : 9; ll res = 0;    _for(i, 0, l)    {        if(!i && lead) res += dfs(pos + 1, ans, lead, limit && (i == l), key);        else res += dfs(pos + 1, ans + (i == key), 0, limit && (i == l), key);    }    return (!lead && !limit) ? dp[pos][ans] = res : res;}ll part(ll x, int i){    memset(dp, -1, sizeof(dp));    len = 0;    for(; x > 0; x /= 10) a[++len] = x % 10;    return dfs(1, 0, 1, 1, i);}inline ll work(ll a, ll b, int i){    return a ? part(b, i) - part(a - 1, i) : part(b, i) - part(a, i) + (i == 0);}int main(){    ll a, b;    scanf("%lld%lld", &a, &b);    _for(i, 0, 9)         printf("%lld%c", work(a, b, i), i == 9 ? '\n' : ' ');    return 0;}
     

 

注意数字很大，要用字符串存储

然后就没啥了，又独立做出紫题

#include
     
      #define add(a, b) a = (a + b) % mod#define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;const int MAXN = 12;const int MAXM = 1e3 + 10;const int mod = 1e9 + 7;int dp[MAXM][MAXN][MAXN][2];int a[MAXM], len;char s1[MAXM], s2[MAXM];int dfs(int pos, int pre, int ppre, int ans, int lead, int limit){    if(pos > len) return ans;    if(dp[pos][pre][ppre][ans] != -1 && (!lead && !limit)) return dp[pos][pre][ppre][ans];    int l = limit ? a[len-pos+1] : 9; int res = 0;    _for(i, 0, l)    {        if(!i && lead) add(res, dfs(pos + 1, pre, ppre, ans, lead, limit && (i == l)));        else if(i && lead) add(res, dfs(pos + 1, i, pre, ans, 0, limit && (i == l)));        else add(res, dfs(pos + 1, i, pre, ans | (i == pre) | (i == ppre), 0, limit && (i == l)));    }    return (!lead && !limit) ? dp[pos][pre][ppre][ans] = res : res;}int part(char* s){    memset(dp, -1, sizeof(dp));    len = strlen(s + 1);    _for(i, 1, len) a[i] = s[len - i + 1] - '0';    return dfs(1, -1, -1, 0, 1, 1);}int judge(char* s){    _for(i, 2, strlen(s + 1))        if(s[i] == s[i-2] || s[i] == s[i-1])            return 1;    return 0;}int main(){    scanf("%s%s", s1 + 1, s2 + 1);    if(s1[1] == 0 && strlen(s1 + 1) == 1) printf("%d\n", (part(s2) - part(s1) + mod) % mod);    else printf("%d\n", (part(s2) - part(s1) + mod + judge(s1)) % mod);    return 0;}
     

 

一开始想的时候当前的数肯定是不能记到答案里的

当然如果知道模数，一直取模就可以限制范围，就很好了

但问题是我们并不知道模数，这就比较尴尬了

就一直卡在这

然而正解非常暴力，但却是对的。

既然不知道模数，那就枚举模数

最后判断一下数字和是不是当前模数且能否整除就好了。

我为什么没想到呢？

注意数位dp要开long long

#include
     
      #define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;typedef long long ll;const int MAXN = 20;ll dp[MAXN][MAXN*10][MAXN*10];int a[MAXN], len, mod;ll dfs(int pos, int num, int state, int lead, int limit){    if(pos > len) return num == mod && state == 0;    if(dp[pos][num][state] != -1 && (!lead && !limit)) return dp[pos][num][state];    int l = limit ? a[len-pos+1] : 9; ll res = 0;    _for(i, 0, l)    {        if(!i && lead) res += dfs(pos + 1, num, state, lead, limit && (i == l));        else if(i && lead) res += dfs(pos + 1, i, i % mod, 0, limit && (i == l));        else res += dfs(pos + 1, num + i, (state * 10 + i) % mod, 0, limit && (i == l));    }    return (!lead && !limit) ? dp[pos][num][state] = res : res;}ll part(ll x){    len = 0;    for(; x; x /= 10) a[++len] = x % 10;    ll res = 0;    for(mod = 1; mod <= len * 9; mod++)    {        memset(dp, -1, sizeof(dp));        res += dfs(1, 0, 0, 1, 1);    }    return res;}int main(){    ll a, b;    scanf("%lld%lld", &a, &b);    printf("%lld\n", !a ? part(b) - part(a) : part(b) - part(a - 1));    return 0;}
     

 

用二进制统计就好了

不过很奇怪的是一开始我数组开的大小是50

因为用程序输出1e15最多的位数是47

但是交上去会WA一个点

改成51就过了

以后只要空间剩余多，就多开一些吧，程序中有些神奇的地方可能会比理论上最大值超出一些

#include
     
      #define mul(a, b) a = (a * b) % mod#define REP(i, a, b) for(register int i = (a); i < (b); i++)#define _for(i, a, b) for(register int i = (a); i <= (b); i++)using namespace std;typedef long long ll;const int MAXN = 51;const int mod = 10000007;ll dp[MAXN][MAXN];int a[MAXN], len;ll dfs(int pos, int ans, int lead, int limit){    if(pos > len) return max(1, ans);    if(dp[pos][ans] != -1 && (!limit && !lead)) return dp[pos][ans];    int l = limit ? a[len-pos+1] : 1; ll res = 1;    _for(i, 0, l)    {        if(!i && lead) mul(res, dfs(pos + 1, ans, lead, limit && (i == l)));        else mul(res, dfs(pos + 1, ans + i, 0, limit && (i == l)));    }    return (!limit && !lead) ? dp[pos][ans] = res : res;}ll part(ll x){    len = 0;    for(; x; x >>= 1) a[++len] = x & 1;    memset(dp, -1, sizeof(dp));    return dfs(1, 0, 1, 1);}int main(){    ll a;    scanf("%lld", &a);    printf("%lld\n", part(a));    return 0;}
     

 

总结

感觉都是套路，掌握套路就好了

相信自己已经掌握了数位dp