【UESTC】【windy数】

2024-08-31 16:58
文章标签 uestc windy

本文主要是介绍【UESTC】【windy数】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

windy数

Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others)
 

windy定义了一种windy数。

不含前导零且相邻两个数字之差至少为 2 的正整数被称为windy数。

windy想知道,在 A B 之间,包括 A B ,总共有多少个windy数?

Input

包含两个整数, A   B

满足  1AB2000000000  .

Output

Sample input and output

Sample Input Sample Output
1 10
9



#include <iostream>
#include <cstring>
#include <cmath>
#include <queue>
#include <stack>
#include <list>
#include <map>
#include <set>
#include <string>
#include <cstdlib>
#include <cstdio>
#include <algorithm>
using namespace std;typedef long long ll;
ll dp[70][10];
ll bits[70];
int cur;
ll dfs(ll pos,int pre,bool flag,bool zeros)
{if(pos <= 0){return 1;}if(!flag && ~dp[pos][pre]) return dp[pos][pre];ll end = flag?bits[pos] : 9;ll ret = 0;for(int i=0;i<=end;i++){if(abs(pre - i) >= 2)  {int tmp  =  i;if(zeros && tmp == 0) tmp = 100;ret += dfs(pos-1,tmp,flag && i == end,zeros && i == 0);}}return flag ? ret : dp[pos][pre] = ret;
}ll solve(ll x)
{cur = 0;ll tt = x;while(tt > 0){bits[++cur] = tt % 10;tt /= 10;}return dfs(cur,100,true,true);}
int main()
{ll a,b;while(scanf("%lld%lld",&a,&b) != EOF){memset(dp,-1,sizeof(dp));printf("%lld\n",solve(b)-1-(solve(a-1) -1));}return 0;
}


这篇关于【UESTC】【windy数】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1124473

相关文章

【BZOJ】1026: [SCOI2009]windy数 数位DP

传送门:【BZOJ】1026: [SCOI2009]windy数 题目分析:数位DP水题。 代码如下: #include <stdio.h>#include <cstring>#include <algorithm>#define rep( i , a , b ) for ( int i = a ; i < b ; ++ i )#define For( i ,

UESTC 1712 Easy Problem With Numbers 除法对和数取模,分解,线段树

附上神牛原版思路: 如果这个题只有乘法,那么你肯定会做吧?线段树更新区间查找区间。 那么有除法呢?当一个数x和m互质的时候,除以x可以改为乘以x的逆元。(至于互质的数求逆元用扩展欧几里德,这个网上可以随便找到) 但是这题并不能保证除的数与m互质吧?什么时候x与m不互质呢?就是x与m含有公因子吧? 那么我们一开始就把m分解,分解出来m有p1,p2,p3,p4...pn等一

bzoj1026--SCOL2009--windy数(数位dp练习1)

windy数 Time Limit:1000MS     Memory Limit:165888KB     64bit IO Format:%lld & %llu Submit  Status Description windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多

UESTC 360(1425) another LCIS

这道题是CD老OJ上面的一道题,现在在新OJ上的题号是360,开始在VJ上做的提交一直RE(囧)。后来才知道OJ移位了。 这道题是一个简单的成段更新+区间合并的线段树的题,1A还让我小激动了一下 这道题的大概意思是有两种操作,一种是成段地增加一个值,另外一种是询问从l到r这段区间内的最长递增子序列 首先先分析一下,如果某一段的值成段地增加一个量,那么该区间内的数的相对大小是不变的,因此递增子

uestc 1307 windy数 --- 数位DP

到底是什么oj啊 根本交不了啊 谁帮我交下这题? #include <iostream>#include <cstring>#include <string>#include <cstdio>#include <cmath>#include <algorithm>#include <vector>#include <queue>#include <map>#defi

uestc 1307 windy数

Description windy定义了一种windy数。 不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数? Input 包含两个整数,A B。 满足 1 <= A <= B <= 2000000000 。 Output 包含一个整数:闭区间[A,B]上windy数的个数。 Sa

1026: [SCOI2009]windy数(数位dp)

1026: [SCOI2009]windy数 Time Limit: 1 Sec Memory Limit: 162 MB Submit: 12141 Solved: 5770 [Submit][Status][Discuss] Description   windy定义了一种windy数。不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道, 在A和B之间,包括A和

UESTC 618 无平方因子数 (容斥 + 莫比乌斯反演)

无平方因子数 Time Limit: 4000/2000MS (Java/Others)    Memory Limit: 65535/65535KB (Java/Others) Submit  Status 无平方因子数即对于任意一个素数p,p2都不会整除那个数,如1 , 5=5 , 15=3×5都是无平方因子数,而20=22×5不是。现在给定一个n (1≤n<1012)

【SCOI2009】windy数

Description windy定义了一种windy数。 不含前导零且相邻两个数字之差至少为2的正整数被称为windy数。 windy想知道,在A和B之间,包括A和B,总共有多少个windy数? Input 两个整数,A B。 Output 一个整数,表示A~B中有多少个windy数。 Sample Input 1 10 Sample Output 9 Data Constr

poj 3686 The Windy's

一开始把图建错了。结果纠结到现在。本题需要拆点,把每台机器当成n台使用。由于每台机器之前加工的玩具无法确定,但是我们可以反过来想。假设当前这个玩具倒数第K加工,那么他和后面加工的玩具总共延误K*MAP[I][J],我们就可以根据这个来建图。然后套KM算法去做。#include<stdio.h>#include<string.h>#include<iostream>using names