<原># vijos P2026 几乎奇偶等和数 [数位dp]【动态规划】

vijos P2026 几乎奇偶等和数 [数位dp]【动态规划】

2017年10月08日 15:24:34 Tabris_ 阅读数:430

个人分类: ===== 各OJ ===== ==== 动态规划 ====


博客爬取于2019-04-18 17:15:22
以下为正文

版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。
https://blog.csdn.net/qq_33184171/article/details/78175188

题目链接: https://vijos.org/p/2026
——————————————————————————————————————
描述

我们称一个整数是奇偶等和数,是说它的数位个数是偶数(比如二位数,四位数,六位数等,且特殊说明 0
是一位数字),且其中所有奇数位数字之和恰好等于所有偶数位数字之和。
我们称一个整数是几乎奇偶等和数,是说在恰好修改其中一位数字后,得到的新数字是一个奇偶等和数。这里说恰好修改一位数字,要求必须发生了实质性修改,也就是说修改后
的数字必须与之前的数字不同(例如将 1234 修改为 1234 就是不合法的,因为修改后的数字和之前是一样的);同时要求不能将最高位修改为 0

现在给定整数 A 和 B ,问有多少几乎奇偶等和数 x 满足 A ≤ x ≤ B 。
格式

输入格式

输入只有一行,是两个整数 A 和 B ,满足 0 ≤ A ≤ B ≤ 10 9 。

输出格式

输出一个正整数,表示有多少几乎奇偶等和数。
样例1

样例输入1

1 33
Copy
样例输出1

21
Copy
样例2

样例输入2

51 78
Copy
样例输出2

25
Copy
限制

对于 30\%30% 的数据, 0 ≤ A ≤ B ≤ 130000 。
对于所有数据, 0 ≤ A ≤ B ≤ 10 9 .
存在额外的 10 % 的数据, − A ≤ 10 7 ;还有另外的额外 10\%10% 的数据, B − A ≤ 5 ×
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>
typedef long long int LL;
using namespace std;
const int N   = 1e7+7;
const int MOD = 998244353;
const double eps = 1e-6;
#define rep(aa,bb,cc) for(int aa=(bb),ee=(cc);aa<=ee;aa++)
#define abs(x)        ((x)>0?(x):-(x))
/*********************************************/

int num[10],len;
int dp[10][120][10][10][10];
//数位 奇位和与偶位和的差 对差的影响的正值 对差的影响的负值 
int dfs(int pos,int sub,int posi,int nop,bool limit,int bt){
    if(pos<0) return bt%2==0 && sub!=0 && (sub*(sub+posi)<=0||sub*(sub-nop)<=0);
    int &d = dp[pos][sub+60][posi][nop][bt];
    if(!limit && d!=-1) return d;

    int endi=9;if(limit) endi=num[pos];

    int res = 0;
    for(int i=0;i<=endi;i++){
        if(bt == 0){
            if(i == 0)   res+=dfs(pos-1,0,0,0,0,0);
            else {
                if(bt&1) res+=dfs(pos-1,sub+i,9-i,i-1,limit&&i==endi,1);
                else     res+=dfs(pos-1,sub-i,i-1,9-i,limit&&i==endi,1);
            }
        }
        else {
            if(bt&1) res += dfs(pos-1,sub+i,max(posi,9-i),max(nop,i),limit&&i==endi,bt+1);
            else     res += dfs(pos-1,sub-i,max(posi,i),max(nop,9-i),limit&&i==endi,bt+1);
        }
    }
    if(!limit) d = res;
    return res;
}
int cal(int x){
    if(x<=0) return 0;
    for(len = 0;x;x/=10) num[len++]=x%10;
    return dfs(len-1,0,0,0,1,0);
}
int x,y;
int main(){
    memset(dp,-1,sizeof(dp));
    while(~scanf("%d%d",&x,&y)){
        printf("%d\n",cal(y)-cal(x-1));
    }
    return 0;
}

 上一篇
<原>#  退役贴 <原># 退役贴
退役贴2017年11月08日 15:31:29 Tabris_ 阅读数:445 博客爬取于2019-04-18 17:15:21以下为正文 版权声明:本文为Tabris原创文章,未经博主允许不得私自转载。https://blog.
2017-11-08
下一篇 
<原>#  Codeforces 794F <原># Codeforces 794F
Codeforces 794F - Leha and security system [线段树-区间更新]【数据结构】2017年09月21日 16:44:50 Tabris_ 阅读数:272 博客爬取于2019-04-17 20:
2017-09-21
  目录