网站的域名是什么意思,seo经验是什么,网站seo优化管理系统,深圳网站设计公司排名题目#xff1a;Windy数
1083. Windy数 - AcWing题库 分析
不能有前导0#xff0c;初始化的时候需要有前导0#xff0c;因为除了最高位数其他位数可以。
windy #xff1a; 2 5 1 类似这样的数 第二位与第一位相差3 2 分类讨论 #xff1a; 1. 位数跟 n 同位数 的…题目Windy数
1083. Windy数 - AcWing题库 分析
不能有前导0初始化的时候需要有前导0因为除了最高位数其他位数可以。
windy 2 5 1 类似这样的数 第二位与第一位相差3 2 分类讨论 1. 位数跟 n 同位数 的 二叉树 左子树情况 右子树情况看是否能进入就是abs(x-last) 2才能进不能就break) 2. 位数 n 数字的位数的 遍历一遍位数 最高位1-9 代码
#includebits/stdc.h
using namespace std;const int N 15;
int f[N][N];void init() {// 只有一位 最高位自身1个for(int i 0; i 9; i ) f[1][i] 1;// 位数枚举 2e9 十位数字for(int i 2; i 10; i ) { // 位数for(int j 0; j 9; j ) { //最高位, 初始化需要前导0for(int k 0; k 9; k ) {if(abs(j-k)2) f[i][j] f[i-1][k];}} }}int dp(int n) {// 特判n 0if(n 0) return 0; // 当n 0时第二个循环会死循环int res 0, last -1;vectorint nums;while(n) nums.push_back(n%10), n/10;// nums.size() 位数的for(int i nums.size()-1; i 0; i --) {int x nums[i];// 最高位 从1(不能前导0) 开始枚举(inums.size()-1);// 左子树for(int j (inums.size()-1); j x; j ) {if(abs(j-last)2) res f[i1][j];}// 右子树if(abs(x-last)2) break; last x;// 特殊情况 全枚举本身if(!i) res ; }// nums.size() 位数的 0 - nums.size()-2 但是向右偏移位数来算原本是下标for(int i 1; i nums.size()-1; i ) {for(int j 1; j 9; j ) { // 不能有前导0res f[i][j];}}return res;
}int main() {init();int l, r;cin l r;cout dp(r) - dp(l-1) endl;return 0;
}
