和山東省選的儲能表很像，都是帶上限的數位dp，先差分一下，然后詢問兩次即可。這里要注意10^10如果減1就變成10位數了，所以這里是加1。 用f[i][j][a][b][c][d][e]來表示。。。 做到第i位，上一位是j（第0位就用10表示），a表示最后兩位是否一樣，b表示是否已經出現連續三個數相等，c表示是否有4，d表示是否有8，e表示是否小于上限。
#include<cmath>#include<cstdio>#include<vector>#include <queue>#include<cstring>#include<iomanip>#include<stdlib.h>#include<iostream>#include<algorithm>#define ll long long#define inf 1000000000#define mod 1000000007#define N 100000#define fo(i,a,b) for(i=a;i<=b;i++)#define fd(i,a,b) for(i=a;i>=b;i--)using namespace std;ll f[20][15][2][2][2][2][2],l,r;int p[20];ll calc(ll q){ ll num,t,i,j,k,a,b,c,d,e,x,y,z,m,n,res; memset(f,0,sizeof(f)); num = 0; t = q; while (t) {p[++num]=t%10; t/=10;} fo(i,1,num/2) swap(p[i],p[num-i+1]); f[0][10][0][0][0][0][1] = 1; //初始化 fo(i,0,num-1) fo(j,0,10) fo(a,0,1) fo(b,0,1) fo(c,0,1) fo(d,0,1) fo(e,0,1) if (f[i][j][a][b][c][d][e]) fo(k,0,9) { if ((k > p[i+1]) && e) continue; //大于上限 x = (k == j); //最后兩位是否一樣 y = b?b:(a+x)==2; //是否連續三個數相等 z = c?c:(k==4); m = d?d:(k==8); if (z + m == 2) continue; //不能同時存在4和8 n = ((k == p[i+1] && e))?1:0; f[i+1][k][x][y][z][m][n] += f[i][j][a][b][c][d][e]; } res = 0; fo(j,0,9) fo(a,0,1) fo(c,0,1) for (d = 0;(d<=1)&&(d+c<2); d++) res += f[num][j][a][1][c][d][0]; return res;}int main(){ scanf("%lld%lld",&l,&r);新聞熱點
疑難解答
