0pts 数位dp 带注释 求调
查看原帖
0pts 数位dp 带注释 求调
1025891
XiaoYiii楼主2024/8/16 23:19

rt

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 15;
ll f[N][10][2][2][2][2], l, r, L, R;//第几位,数字是几,上一位是否与这一位相等,有没有4、8、连续三个
int a[N], n;
void init(ll x){
    int cnt = 0;
    while(x){
        ++cnt;
        a[n - cnt + 1] = x % 10;
        x /= 10;
    }
}
ll solve(ll x, ll & op){
    ll ret = 0ll;
    init(x);
    for(int j = 1; j <= a[1] - 1; j++){
        for(int p = 0; p <= 1; p++) ret += f[1][j][p][0][1][1] + f[1][j][p][1][0][1] + f[1][j][p][0][0][1];
    }
    int o = (a[1] == 4), s = (a[1] == 8), t = 0, cnt = 0;
    for(int i = 2; i <= n; i++){
        for(int j = 0; j <= a[i] - 1; j++){
            if(j == 4 && s) continue;
            if(j == 8 && o) continue;
            //后面有连续的三段情况一定可以
            for(int p = 0; p <= 1; p++){
                ret += f[i][j][p][1][0][1] + f[i][j][p][0][1][1] + f[i][j][p][0][0][1];
            }
            //前面有三段的情况下后面可以没有三段
            if(t || (j == a[i - 1] && cnt)){
                for(int p = 0; p <= 1; p++){
                    ret += f[i][j][p][1][0][0] + f[i][j][p][0][1][0] + f[i][j][p][0][0][0];
                }
            }
            //i - 1, i, i + 1 构成三段后面也可以没有三段
            else if(j == a[i - 1]){
                ret += f[i][j][1][1][0][0] + f[i][j][1][0][1][0] + f[i][j][1][0][0][0];
            }
        }
        o |= (a[i] == 4);
        s |= (a[i] == 8);
        if(a[i] == a[i - 1]){
            t |= cnt;
            cnt = 1;
        }
        else cnt = 0;
        if(o && s) return ret;
    }
    if(t) op = 1;
    return ret;
}
void work(){
    n = 11;
    for(int j = 0; j <= 9; j++){
        f[n][j][0][j == 4][j == 8][0] = 1;
    }
    for(int i = n - 1; i >= 1; i--){
        //先转移有连续三个的
        for(int j = 0; j <= 9; j++){
            for(int p = 0; p <= 1; p++){
                for(int k = 0, o, s; k <= 9; k++){
                    o = (k == 4);
                    s = (k == 8);
                    for(; o <= 1; o++){
                        for(; s <= 1; s++){
                            f[i][j][j == k][o | (j == 4)][s | (j == 8)][1] += f[i + 1][k][p][o][s][1];
                        }
                    }
                    
                }
            }
        }
        //转移没有连续三个的
        //之前p = 0时
        for(int j = 0; j <= 9; j++){
            for(int k = 0, o, s; k <= 9; k++){
                o = (k == 4);
                s = (k == 8);
                for(; o <= 1; o++){
                    for(; s <= 1; s++){
                        f[i][j][j == k][o | (j == 4)][s | (j == 8)][0] += f[i + 1][k][0][o][s][0];
                    }
                }
            }
        }
        //之前p = 1时
        for(int j = 0; j <= 9; j++){
            for(int k = 0, o, s; k <= 9; k++){
                o = (k == 4);
                s = (k == 8);
                for(; o <= 1; o++){
                    for(; s <= 1; s++){
                        f[i][j][j == k][o | (j == 4)][s | (j == 8)][j == k] += f[i + 1][k][1][o][s][0];
                    }
                }
            }
        }
    }
}
int main(){
    work();
    scanf("%lld%lld", &l, &r);
    printf("%lld\n", R + solve(r, R) - solve(l, L));
    return 0;
}
2024/8/16 23:19
加载中...