1 条题解
-
1
算法:数位
不熟悉数位 的同学可以看一下洛谷日报第 84 期
“求出在给定区间 内,符合条件 的数 的个数。条件 一般与数的大小无关,而与数的组成有关。”根据日报中给出的数位 的基本模板,容易想到这是一道数位 。
根据题意,要记录当前某一个数码是否出现过,以及出现次数。
由于只关心出现次数的奇偶性,可以使用压缩的一个二进制数 ( 的缩写)表示,某一位上的 表示出现了奇数次, 表示出现了偶数次。但这里存在一个问题, 既可以表示出现了偶数次,也可以表示没有出现
(0 也是偶数(雾)),为了解决这个问题,可以再开一个变量 ( 的缩写)表示某一个数码是否出现过,同理, 表示出现过, 表示没出现过。由于数字 的特殊性,我们还要开一个变量,标记当前的 是不是前导 。如果是前导 ,那么是不需要统计到出现的 的个数的,否则需要统计。如果上一位是前导 ,并且这一位也是 ,那么还是前导 ,否则是数字中间的 ,需要记录。
##code: (详细见代码)
#include<bits/stdc++.h> #define int long long//懒惰做法 #define F(i,a,b) for(register int i=(a);i<=(b);i++) using namespace std; const int N=1.5e6; int T,l,r,f[50]; int dp[30][N],num; map<pair<int,int>,int> mp;//记录当前状态{sta,apr}是否出现过(用数组也可以) bool check(int sta,int apr) { F(i,0,9){ if(apr&1<<i){//数码 i 出现过 if((i&1) and (sta&1<<i))return false; //i 是 奇数,且出现了奇数次 if(!(i&1) and !(sta&1<<i))return false; //i 是偶数,且出现了偶数次 } } return true; } int dfs(int pos,int sta,int apr,bool lim,bool pre) { //pos:当前dp从高到低第pos位数字 //lim:是不是存在最高位的限制 //pre:判断上一位是不是前导0 if(!pos)return check(sta,apr); if(!lim and !pre and dp[pos][mp[{sta,apr}]]!=-1)return dp[pos][mp[{sta,apr}]]; int s=0; for(int i=0; i<=(lim?f[pos]:9); i++) { bool ok=pre&&(!i); s+=dfs(pos-1,ok?sta:sta^(1<<i),ok?apr:apr|(1<<i),lim and i==f[pos],ok); //不是前导0时,sta中第i位要 ^1 (1变0,0变1),apr中记录数码i出现过 } if(!lim and !pre)mp[{sta,apr}]=++num,dp[pos][num]=s; return s; } int solve(int x) {//板子 int cnt=0; while(x)f[++cnt]=x%10,x/=10; return dfs(cnt,0,0,1,1); } signed main() {//用 signed 可以使define int long long不会爆掉 memset(dp,-1,sizeof(dp));//初始化 -1 代表没搜过 scanf("%lld",&T); while(T--) { scanf("%lld%lld",&l,&r); printf("%lld\n",solve(r)-solve(l-1)); } return 0; }
感谢观看
- 1
信息
- ID
- 2066
- 时间
- 1000ms
- 内存
- 1536MiB
- 难度
- 10
- 标签
- (无)
- 递交数
- 2
- 已通过
- 1
- 上传者