[原创]vijos P2026 几乎奇偶等和数 [数位dp]【动态规划】
2017-10-08 15:24:34 Tabris_ 阅读数:485
博客爬取于2020-06-14 22:39:26
以下为正文
版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/78175188
题目链接:https://vijos.org/p/2026
——————————————————————————————————————
描述
我们称一个整数是奇偶等和数,是说它的数位个数是偶数(比如二位数,四位数,六位数等,且特殊说明 $0$ 是一位数字),且其中所有奇数位数字之和恰好等于所有偶数位数字之和。
我们称一个整数是几乎奇偶等和数,是说在恰好修改其中一位数字后,得到的新数字是一个奇偶等和数。这里说恰好修改一位数字,要求必须发生了实质性修改,也就是说修改后的数字必须与之前的数字不同(例如将$1234$修改为$1234$就是不合法的,因为修改后的数字和之前是一样的);同时要求不能将最高位修改为 $0$。
现在给定整数 $A$ 和 $B$,问有多少几乎奇偶等和数 $x$ 满足 $A\le x\le B$。
格式
输入格式
输入只有一行,是两个整数 $A$ 和 $B$,满足 $0\le A\le B\le 10^9$。
输出格式
输出一个正整数,表示有多少几乎奇偶等和数。
样例1
样例输入1
1 33
Copy
样例输出1
21
Copy
样例2
样例输入2
51 78
Copy
样例输出2
25
Copy
限制
对于 30%30% 的数据,$0\le A\le B\le 130000$。
对于所有数据,$0\le A\le B\le 10^9$.
存在额外的 $10%$的数据,$-A\le 10^7$ ;还有另外的额外 10%10% 的数据,$B-A\le 5\times 10^7$ 。
每一组数据的时限为 $0.3$ 秒。
——————————————————————————————————————
注意的是一定要修改一个数字,然后是奇数位上和偶数位上,不算是奇数数字和偶数数字的和的比较,,,
对于一个数字 判定是否是奇偶等和数 ,只要把奇位和与偶位和的差算出来,然后 逐位判断每个数字的大小关系就行,小的数字变大的,大的数字变小的然后对奇位和与偶位和的差的改变就确定了,到这步就能O(1)判断这个是否合法了.
直接数位dp算下去就行了,然后记忆化一下,
int dp[10][120][10][10][10];
//数位 奇位和与偶位和的差 对差的影响的正值 对差的影响的负值 当前数字的长度
int dfs(int pos,int sub,int posi,int nop,bool limit,int bt)
// 数位 奇位和与偶位和的差 对差的影响的正值 对差的影响的负值 限制 当前数字的长度
附本题代码
——————————————————————————————————————
# include <bits/stdc++.h> |


