首页 > 其他分享 >HDU2089 不要62

HDU2089 不要62

时间:2022-11-22 22:45:10浏览次数:55  
标签:pre 不要 zero int lim HDU2089 62 && ans

题目

Problem Description
杭州人称那些傻乎乎粘嗒嗒的人为62(音:laoer)。
杭州交通管理局经常会扩充一些的士车牌照,新近出来一个好消息,以后上牌照,不再含有不吉利的数字了,这样一来,就可以消除个别的士司机和乘客的心理障碍,更安全地服务大众。
不吉利的数字为所有含有4或62的号码。例如:
62315 73418 88914
都属于不吉利号码。但是,61152虽然含有6和2,但不是62连号,所以不属于不吉利数字之列。
你的任务是,对于每次给出的一个牌照区间号,推断出交管局今次又要实际上给多少辆新的士车上牌照了。

Input
输入的都是整数对n、m(0<n≤m<1000000),如果遇到都是0的整数对,则输入结束。

Idea

这是一道数位DP的入门题目. 所谓数位DP, 就是考虑每一个数位(digit)的出现方式, 通过记忆化的方式初步降低复杂度, 来达到优化程序的目的.

枚举的方式

最简单的方法如下: for i=[l..r] if(ok(i)) ans++;

但是在高中的时候做排列组合题目的时候我们有另一种方式: 把每一位当作独立的对象, 然后做就行了.

于是我们考虑最高位开始, 比如上限是\(4145\), 那么我们考虑从高到低, 一位一位枚举的时候会发生什么:
(1) 第一位的时候就必须是\([1..4]\)而不应该是别的. 此外, 在\([1..3]\)的时候和\([4]\)的时候后续的状态也是不一样的. 因此我们需要记录当前是否选择了最高位(用bool类型lim表示, 表示存不存在限制).
(2) 另外, 注意到如果第一位选择了0, 那么就打开了前导0选项. (用bool类型zero表示, 表示现在是不是还是处于前导零的选项).

因此我们有伪代码:

DFS(int x(位置), ...(状态) ,bool lim, bool zero ){
	if(x==0) return 0;
	检查记忆化的结果
	up = lim?(数组的第x位代表的数字):9
	ans = 0
	for i=0..up{
	分情况讨论, 并且执行
		ans += 
			dfs(
	位置:			x-1,
	状态:			...(状态转移),
下一位是否受限制:			lim && i==数组的第x位代表的数字,
下一位是否是前导零:		zero && i==0, 
			) 
	}
	计算完存档
}

需要注意, 这个性质是不是存在前缀和的性质. (相减)

因此, 我们来看这个问题.

Code

#include <bits/stdc++.h>
using namespace std;
#define F(i, a, b) for(int i=(a); i<=(b);i++)
#define Fd(i, a, b) for(int i=(a);i>=(b);i--)
#define int long long
int f[15][15][15][15];
int num[15]={0};
int dfs(int x, int pre, int lim, int zero){
	// printf("x=%d pre=%d lim=%d\n", x, pre, lim);
	if(x==0) return 1; 
	if(f[x][pre][lim][zero]!=-1) return f[x][pre][lim][zero];
	int up = lim ? num[x]:9;
	int ans = 0;
	F(i, 0, up){
		if(i==2 && pre == 6) continue;
		if(i==4) continue;
		ans += dfs(x-1, i, lim && (i==up), i==0&&zero);
	}
	// printf("ans = %d\n", ans);
	f[x][pre][lim][zero]=ans;
	return ans ;
}

int solve(int x){
	memset(f,-1,sizeof f);
    int pos=0;
    while(x){
        num[++pos]=x%10;
        x/=10;
    }
    return dfs(pos,-1,1,1);
}
signed main(){
    int le,ri;
    
    while(cin>>le>>ri && le+ri){
        memset(f,-1,sizeof f);
        cout<<solve(ri)-solve(le-1)<<"\n";
    }
    return 0;
}

标签:pre,不要,zero,int,lim,HDU2089,62,&&,ans
From: https://www.cnblogs.com/augpath/p/16915260.html

相关文章

  • 个人学习笔记不要看
    packagemainimport( "fmt")funcmain(){ //构建一个通道 ch1:=make(chanint) //开启一个匿名并发函数 gofunc(){ fmt.Println("startgoroutine") /......
  • Codeforces862A-Mahmoud and Ehab and the MEX
    MahmoudandEhabandtheMEXDr.EvilkidnappedMahmoudandEhabintheevillandbecauseoftheirperformanceintheEvilOlympiadinInformatics(EOI).Hedeci......
  • MBR16200CT-ASEMI插件肖特基二极管MBR16200CT
    编辑-ZMBR16200CT在TO-220AB封装里采用的2个芯片,其尺寸都是102MIL,是一款插件肖特基二极管。MBR16200CT的浪涌电流Ifsm为200A,漏电流(Ir)为0.05mA,其工作时耐温度范围为-65~175......
  • MBR16200CT-ASEMI插件肖特基二极管MBR16200CT
    编辑-ZMBR16200CT在TO-220AB封装里采用的2个芯片,其尺寸都是102MIL,是一款插件肖特基二极管。MBR16200CT的浪涌电流Ifsm为200A,漏电流(Ir)为0.05mA,其工作时耐温度范围为-65~1......
  • MBR16200FCT-ASEMI塑封肖特基二极管MBR16200FCT
    编辑:llMBR16200FCT-ASEMI塑封肖特基二极管MBR16200FCT型号:MBR16200FCT品牌:ASEMI封装:ITO-220AB正向电流:16A反向电压:200V引线数量:3芯片个数:2芯片尺寸:102MIL漏电流:10ua恢复时间......
  • MBR16200FCT-ASEMI塑封肖特基二极管MBR16200FCT
    编辑:llMBR16200FCT-ASEMI塑封肖特基二极管MBR16200FCT型号:MBR16200FCT品牌:ASEMI封装:ITO-220AB正向电流:16A反向电压:200V引线数量:3芯片个数:2芯片尺寸:102MIL漏电流:1......
  • MBR16200CT-ASEMI半塑封肖特基二极管MBR16200CT
    编辑:llMBR16200CT-ASEMI半塑封肖特基二极管MBR16200CT型号:MBR16200CT品牌:ASEMI封装:TO-220AB特性:肖特基二极管正向电流:16A反向耐压:200V恢复时间:5ns引脚数量:3芯片......
  • 1762F(二分)
    题目链接·思路:这题用到了一下二分的应用,嗨,当时确实没有想到。可知k是递增的关系。二分判断就可。AC代码:#include<bits/stdc++.h>#defineintlonglongusingname......
  • Cisco FI 6248UP to Nexus 5Ks connectivity
    https://supportforums.cisco.com/discussion/11765826/cisco-fi-6248up-nexus-5ks-connectivityHelloLuke,YoucanupgradeUCSMto2.1.1aHereissampleconfigfo......
  • ABC262F
    ABC262F*2334卡手的构造题,不是很难想,主要是细节比较多。题意给定一个排列\(p\)。你可以最多执行\(k\)次操作。删除一个数。将\(p\)中末尾的数移到开头。找出......