不含前导零且相邻两个数字之差至少为 22 的正整数被称为 windy 数。windy 想知道,在 a 和 b 之间,包括 a 和 b ,总共有多少个 windy 数?
输入格式
输入只有一行两个整数,分别表示 a 和 b。
intA[10];intdp[10][100];////// \param pos 当前位置/// \param last 上一个位置的数的值/// \param limit 当前位置的数是否可以任取/// \param lead 当前位置之前全是0/// \returnintdfs(int pos,int last,bool limit,bool lead) {if (pos <=0) return1; // 搜索终点if (!limit and last !=-3anddp[pos][last] !=-1)returndp[pos][last];int ans =0;for (int v =0; v <= (limit ?A[pos] :9); ++v) { // 根据是否limit决定循环上界if (abs(v - last) <2) // 舍弃不合法解continue;if (lead and v ==0)ans +=dfs(pos -1,-3, limit && v ==A[pos],true); // 当前位和前面都是0,后面的数可以任取,last赋为-3else ans +=dfs(pos -1, v, limit && v ==A[pos],false); }if (!limit) dp[pos][last] = ans;return ans;}intsolve(int x) {memset(A,0,sizeof(A));memset(dp,-1,sizeof(dp));int pos =0;while (x) {A[++pos] = x %10; x /=10; }returndfs(pos,-3,true,true);}signedmain() {#ifdefLOCALfreopen("output.txt","w", stdout);freopen("input.txt","r", stdin);#endif ios::sync_with_stdio(false);cin.tie(nullptr);// cin >> t;// while (t--) {// solve();// } cin >> n >> m;print(solve(m) -solve(n -1));}
更一般的模板:
intA[10];intdp[10][15][2][2];////// \param pos 当前位置/// \param last 上一个位置的数的值/// \param limit 当前位置的数是否可以任取/// \param lead 当前位置之前全是0/// \returnintdfs(int pos,int last,bool limit,bool lead) {if (pos <=0) return1; // 搜索终点if (dp[pos][last][limit][lead] !=-1)returndp[pos][last][limit][lead];int ans =0;int _limit = limit ?A[pos] :9; // 根据是否limit决定循环上界for (int v =0; v <= _limit; ++v) {if (abs(v - last) <2andnot lead) // 舍弃不合法解continue; ans +=dfs(pos -1, v, limit && (v ==A[pos]), lead and (v ==0)); }dp[pos][last][limit][lead] = ans;return ans;}intsolve(int x) {memset(A,0,sizeof(A));memset(dp,-1,sizeof(dp));int pos =0, ans =0;while (x) {A[++pos] = x %10; x /=10; }for (int i =0; i <=A[pos]; i++) { ans +=dfs(pos -1, i, i ==A[pos], i ==0); }return ans;}
CF1811E
In Japan, the number 4 reads like death, so Bob decided to build a live sequence. Living sequence a contains all natural numbers that do not contain the digit 4 . a=[1,2,3,5,6,7,8,9,10,11,12,13,15,16,…] .
For example, the number 1235 is part of the sequence a , but the numbers 4321 , 443 are not part of the sequence a .
Bob realized that he does not know how to quickly search for a particular number by the position k in the sequence, so he asks for your help.
For example, if Bob wants to find the number at position k=4 (indexing from 1 ), you need to answer ak=5 .
可以用数位dp+二分解决。
intA[20];intdp[20];////// \param pos 当前位置/// \param last 上一个位置的数的值/// \param limit 当前位置的数是否可以任取/// \param lead 当前位置之前全是0/// \returnintdfs(int pos,int last,bool limit,bool lead) {if (pos <=0) return1; // 搜索终点if (!limit anddp[pos] !=-1)returndp[pos];int ans =0;int _limit = limit ?A[pos] :9; // 根据是否limit决定循环上界for (int v =0; v <= _limit; ++v) {if (v ==4) // 舍弃不合法解continue; ans +=dfs(pos -1, v, limit && (v ==A[pos]), lead and (v ==0)); }if (!limit)dp[pos] = ans;return ans;}intf(int x) {memset(A,0,sizeof(A));memset(dp,-1,sizeof(dp));int pos =0, ans =0;while (x) {A[++pos] = x %10; x /=10; }returndfs(pos,11,true,true);}boolcheck(int mid) {returnf(mid) -f(0) >= n;}voidsolve() { cin >> n;int L =1, R =1e16;while (L < R) {int mid = (L + R) /2;if (check(mid))R = mid;else L = mid +1; }print(L);}