题目分析
题目要求统计区间 内“无聊数”的个数。
一个正整数被称为无聊数，当且仅当：
- 奇数位上的数字都是奇数。
- 偶数位上的数字都是偶数。
思路
数位 DP。
用记忆化搜索实现数位 DP，为了更好了解下方的代码，设置以下变量：
pos：目前处理到数字的第几位。f1：目前是否受到原数字上界的限制。f2：目前是否还在处理前导零。sum：记录实际数字的起始位置，用来计算位数的奇偶性。
但是记住有前导零！
使用四维数组 记录已计算状态，避免重复搜索。
注意只有在 !f1 and !f2 时才进行记忆化，因为受限制或前导零状态下的结果没有通用性。
AC Code
#include <bits/stdc++.h>
#define int long long
using namespace std;
int dp[22][2][2][22],num[22];
int cnt;
int T;
void get(int n) {
if (n==0) {
num[0]=0;
cnt=1;
return;
}
cnt=0;
int a[22];
while(n){
a[cnt++]=n%10;
n/=10;
}
for(int i=0;i<cnt;i++) num[i]=a[cnt-1-i];
}
int dfs(int pos,bool f1,bool f2,int sum) {
if(pos==cnt) return f2?0:1;//全是前导零说明是 0，不算无聊数
if(!f1 and !f2 and dp[pos][f1][f2][sum]!=-1) return dp[pos][f1][f2][sum]; //记忆化查询
int res=0;
int limit=f1?num[pos]:9;
for (int i=0;i<=limit;i++) {
if(f2 and i==0) res+=dfs(pos+1,f1 and (i==limit),true,sum);
else{
int c=f2?pos:sum;// 确定实际起始位置
int k=pos-c+1;
if(k&1) {
if(i&1)
res+=dfs(pos+1,f1 and (i==limit),false,c);
}
else
if(!(i&1)) res+=dfs(pos+1,f1 and (i==limit),false,c);
}
}
if(!f1 and !f2) dp[pos][f1][f2][sum]=res;// 记忆化存储
return res;
}
int solve(int n) {
if(n<=0) return 0;
get(n);
memset(dp,-1,sizeof dp);
return dfs(0,true,true,0);
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>T;
for(int i=1;i<=T;i++) {
int L,R;
cin>>L>>R;
cout<<"Case #"<<i<<": "<<(solve(R)-solve(L - 1))<<endl;
}
exit(0);
}
暂无评论