题意： 给你一个范围 \((1<= L,R <=9\times10^{18})\)区间范围内，你要求符合位数上连续奇数有偶数个，连续偶数有奇数个 的数的个数思路： 对于区间上求符合条件数位的个数与我们肯定会想到数位dp。这道题有 连续偶数与奇数（连续个数状态），以及对应的奇偶状态（还有0这种比较特别的） 所以我们可以使用\(dp[pos][val][length]\)来表示第pos位状态，为值value，以及现在连续长度状态。奇偶状态不应该分开讨论么？由于只需要满足连续状态即可所以我们的val即代表当前处于的连续状态是奇还是偶 关于状态转移：首先是pos结束判断 \((pos==-1)\) 讨论 \(x!=0\) 以及 \(x==0\) 的状态。在 \(x!=0\)状态下我们要保证其符合 题目要求 连续奇数为偶,偶数为奇。即 \(x%2 != p%2\) 然后就是在每次枚举位的时候要判断 \(x 是否等于 0\)，然后就是奇偶变化时候判断是否符合可以转换条件...
code:
#include <bits/stdc++.h> #define IOS ios::sync_with_stdio(0); cin.tie(0); #define accept 0 #define mp make_pair using namespace std; typedef long long ll; typedef unsigned long long ull; typedef pair<int, int> pii; const int inf = 0x3f3f3f3f; const int maxn = 1e3+7; const int maxm = 1e6+7; const int mod = 1e9+7; ll dp[20][10][20]; int digit[20]; ll dfs(int pos, int limit, int p, int x){ //递归边界 if (pos==-1){ if (x && x%2!=p%2) return 1; else return 0; } //记忆化 if (!limit && dp[pos][p][x]!=-1) return dp[pos][p][x]; int up = limit ? digit[pos] : 9; long long ans = 0; for (int i=0;i<=up;i++){ //如果考虑的串长度是0，说明前面都是前导零，特殊处理一下 if (x==0){ //下一次长度还是0 if (i==0) ans += dfs(pos-1, limit&&i==up, i, 0); //遇见非零数位，长度置1 else ans += dfs(pos-1, limit&&i==up, i, 1); } //长度不为0的时候 else { //如果数位奇偶性不变，长度加1 if (p%2 == i%2) ans += dfs(pos-1, limit&&i==up, i, x+1); //数位奇偶性发生变化的时候，判断当前结束位置合法性 else if (x%2 != p%2) ans += dfs(pos-1, limit&&i==up, i, 1); } } if (!limit) dp[pos][p][x] = ans; return ans; } ll solve(long long n){ if (n==0) return 0; int cnt = 0; while(n){ digit[cnt++] = n; n /= 10; } memset(dp,-1,sizeof(dp)); return dfs(cnt-1, 1, 0, 0); } int main() { int t,cas=0; scanf("%d",&t); while(t--){ long long l,r; scanf("%lld%lld",&l,&r); printf("Case #%d: %lld\n",++cas, solve(r)-solve(l-1)); } return accept; }转载于:https://www.cnblogs.com/Tianwell/p/11412742.html
相关资源：JAVA上百实例源码以及开源项目