[数位dp] spoj 10738 Ra-One Numbers

时间:2022-09-23 22:37:14

题意:给定x、y。为[x,y]之间有多少个数的偶数位和减去奇数位和等于一。

个位是第一位。

样例: 10=1-0=1 所以10是这种数

思路:数位dp[i][sum][ok] i位和为sum 是否含有前导0.

然后就是由于有负数 所以依据范围把0设置为100 然后最后和等于101则为所求的数。

代码:

#include"cstdlib"
#include"cstdio"
#include"cstring"
#include"cmath"
#include"stack"
#include"algorithm"
#include"iostream"
using namespace std;
int dp[12][200][2],num[12];
int fuck[2]={1,-1};
int dfs(int site,int sum,int ok,int f)
{
if(site==0)
{
if(ok==0) return 0;
return sum==101?1:0; //小处理 和为101
}
if(!f&&dp[site][sum][ok]!=-1) return dp[site][sum][ok];
int len=f?num[site]:9;
int ans=0;
for(int i=0;i<=len;i++)
{
if(ok==0)
{
if(i==0) ans+=dfs(site-1,sum,ok||i!=0,f&&i==len);
else ans+=dfs(site-1,sum+i*fuck[site%2],ok||i!=0,f&&i==len);
}
else
{
ans+=dfs(site-1,sum+i*fuck[site%2],ok||i!=0,f&&i==len);
}
}
if(!f) dp[site][sum][ok]=ans;
return ans;
}
int solve(int x)
{
if(x<0) return 0;
int cnt=0;
while(x)
{
num[++cnt]=x%10;
x/=10;
}
return dfs(cnt,100,0,1); //进入的时候 sum=100
}
int main()
{
int t;
scanf("%d",&t);
memset(dp,-1,sizeof(dp));
while(t--)
{
int x,y;
scanf("%d%d",&x,&y);
printf("%d\n",solve(y)-solve(x-1));
}
return 0;
}

[数位dp] spoj 10738 Ra-One Numbers的更多相关文章

  1. 【数位dp】CF 55D Beautiful numbers

    题目 Volodya is an odd boy and his taste is strange as well. It seems to him that a positive integer n ...

  2. 【数位DP】 HDU 4722 Good Numbers

    原题直通车: HDU  4722  Good Numbers 题意: 求区间[a,b]中各位数和mod 10==0的个数. 代码: #include<iostream> #include& ...

  3. SPOJ BALNUM - Balanced Numbers - &lbrack;数位DP&rsqb;&lbrack;状态压缩&rsqb;

    题目链接:http://www.spoj.com/problems/BALNUM/en/ Time limit: 0.123s Source limit: 50000B Memory limit: 1 ...

  4. SPOJ BALNUM Balanced Numbers (数位dp)

    题目:http://www.spoj.com/problems/BALNUM/en/ 题意:找出区间[A, B]内所有奇数字出现次数为偶数,偶数字出现次数为计数的数的个数. 分析: 明显的数位dp题, ...

  5. 【SPOJ 2319】 BIGSEQ - Sequence (数位DP&plus;高精度)

    BIGSEQ - Sequence You are given the sequence of all K-digit binary numbers: 0, 1,..., 2K-1. You need ...

  6. 【SPOJ 1182】 SORTBIT - Sorted bit squence (数位DP)

    SORTBIT - Sorted bit squence no tags Let's consider the 32 bit representation of all integers i from ...

  7. Balanced Numbers (数位dp&plus;三进制)

    SPOJ - BALNUM 题意: Balanced Numbers:数位上的偶数出现奇数次,数位上的奇数出现偶数次(比如2334, 2出现1次,4出现1次,3出现两次,所以2334是 Balance ...

  8. 【BZOJ1662】&lbrack;Usaco2006 Nov&rsqb;Round Numbers 圆环数 数位DP

    [BZOJ1662][Usaco2006 Nov]Round Numbers 圆环数 Description 正如你所知,奶牛们没有手指以至于不能玩"石头剪刀布"来任意地决定例如谁 ...

  9. 找规律&sol;数位DP HDOJ 4722 Good Numbers

    题目传送门 /* 找规律/数位DP:我做的时候差一点做出来了,只是不知道最后的 is_one () http://www.cnblogs.com/crazyapple/p/3315436.html 数 ...

随机推荐

  1. mybatic与spring结合的事务管理

    原文地址:http://czj4451.iteye.com/blog/2037759 mybatis与spring结合后,事务管理更加方便,这里介绍使用transactionnal的方式,有错的的地方 ...

  2. 12个Linux进程管理命令介绍&lpar;转&rpar;

    12个Linux进程管理命令介绍 [日期:2015-06-02] 来源:Linux中国  作者:Linux [字体:大 中 小]   执行中的程序在称作进程.当程序以可执行文件存放在存储中,并且运行的 ...

  3. RPC应用的java实现&lpar;转&rpar;

    一.RPC介绍 什么是RPC?Remote Procedure Call,远程过程调用.也就是说,调用过程代码并不是在调用者本地运行,而是要实现调用者与被调用者二地之间的连接与通信.比较严格的定义是: ...

  4. Entity Framework 自动生成CodeFirst代码

    前言 在前面的文章中我们提到Entity Framework的“Code First”模式也同样可以基于现有数据库进行开发.今天就让我们一起看一下使用Entity Framework Power To ...

  5. NET Core中使用Redis

    NET Core中使用Redis 注:本文提到的代码示例下载地址> https://code.msdn.microsoft.com/How-to-use-Redis-in-ASPNET-0d82 ...

  6. 【C&plus;&plus;】统计代码覆盖率&lpar;二&rpar;

    嗷嗷嗷!!!好激动,我好蠢.不过最后还是解决了.呜呜呜 有些都是东一块西一块查的,如果有侵权欢迎私信我,我注明出处. 一 gcov&CMake 昨天试了下测试代码和被测代码都是c++的情况,直 ...

  7. My blog

    欢迎啦……嘿嘿 http://blog.csdn.net/zuguodexiaoguoabc http://blog.sina.com.cn/u/3914181130

  8. (大数据工程师学习路径)第四步 SQL基础课程----SQL介绍及mysql的安装

    一.数据库和SQL介绍 数据库(Database)是按照数据结构来组织.存储和管理数据的仓库,它的产生距今已有六十多年.随着信息技术和市场的发展,数据库变得无处不在:它在电子商务.银行系统等众多领域都 ...

  9. 【分享】iTOP4412开发板-Bluetooth移植文档

    [分享]iTOP4412开发板-Bluetooth移植文档 最近须要把Bluetooth移植到iTOP-4412 开发平台.查阅了相关资料,经过一段时间的研究.调试,最终成功的将蓝牙功能移植到了开发板 ...

  10. 对Javascript到底了解多少,一测便知道

    笔者在这里附上一段代码,请读者思考一下程序的运行结果: console.log(a); //??? a(); var a=3; function a(){ console.log(10); } con ...