博客网站怎么建设,2022年网络规划设计师,音乐门户网站模板,wordpress视频无法播放题目链接#xff1a;BZOJ - 1026 题目分析 这道题是一道数位DP的基础题#xff0c;对于完全不会数位DP的我来说也是难题.. 对于询问 [a,b] 的区间的答案#xff0c;我们对询问进行差分#xff0c;求 [0,b] - [0,a-1] 的答案。这样就化繁为简了。 具体过程见代码中的注释。 …题目链接BZOJ - 1026 题目分析 这道题是一道数位DP的基础题对于完全不会数位DP的我来说也是难题.. 对于询问 [a,b] 的区间的答案我们对询问进行差分求 [0,b] - [0,a-1] 的答案。这样就化繁为简了。 具体过程见代码中的注释。 代码 #include iostream
#include cstdio
#include cstdlib
#include cstring
#include cmath
#include algorithmusing namespace std;const int MaxBit 13;int A, B;
int f[MaxBit][11], Bit[MaxBit];inline int Abs(int a) {return a 0 ? a : -a;
}//计算小于x的数的答案
int Get(int x) {if (x 0) return 0;int ret 0, l 0;while (x) {Bit[l] x % 10;x / 10;}//统计位数不足l位的答案 for (int i 1; i l - 1; i) {for (int j 1; j 9; j) {ret f[i][j];}}//最高位可以在[1, Bit[l]-1]之间变化 for (int i 1; i Bit[l] - 1; i) ret f[l][i];//固定后面的(l-i)位然后第i位可以在[0, Bit[i]-1]之间变化 for (int i l - 1; i 1; --i) {for (int j 0; j Bit[i] - 1; j) {if (Abs(j - Bit[i 1]) 2) ret f[i][j];}//无法固定第i位 if (Abs(Bit[i 1] - Bit[i]) 2) break;}return ret;
}int main()
{//f[i][j]表示第i位是j的答案数 for (int i 0; i 9; i) f[1][i] 1;for (int i 1; i 10; i) {for (int j 0; j 9; j) {for (int k 0; k 9; k) {if (Abs(k - j) 2) f[i][j] f[i - 1][k];}}}scanf(%d%d, A, B);//对询问进行差分化繁为简 printf(%d\n, Get(B 1) - Get(A));return 0;
}转载于:https://www.cnblogs.com/JoeFan/p/4231594.html
