当前位置:网站首页>CF1036C Classy Numbers 题解
CF1036C Classy Numbers 题解
2022-07-06 07:23:00 【q779】
CF1036C Classy Numbers 题解
题意:定义一个数字是“好数”,当且仅当它的十进制表示下有不超过 3 3 3个数字 1 ∼ 9 1 \sim 9 1∼9
举个例子: 4 , 200000 , 10203 4,200000,10203 4,200000,10203是“好数”,然而 4231 , 102306 , 7277420000 4231,102306,7277420000 4231,102306,7277420000不是
给定 [ l , r ] [l,r] [l,r],问有多少个 x x x使得 l ≤ x ≤ r l \le x \le r l≤x≤r,且 x x x是“好数”
一共有 T ( 1 ≤ T ≤ 1 0 4 ) T(1 \le T \le 10^{4}) T(1≤T≤104)组数据,对于每次的询问,输出一行一个整数表示答案
1 ≤ l i ≤ r i ≤ 1 0 18 1 \le l_i \le r_i \le 10^{18} 1≤li≤ri≤1018
一般数位dp可以用来解决 ∑ i = l r f ( i ) \sum _{i=l}^{r} f(i) ∑i=lrf(i) 的问题,
其中 f ( i ) f(i) f(i) 为与 i i i 的数位有关的某个函数或判定式
这题稍微变形了一下,那我们就理所当然地记录一下出现数字的情况
设 f i , j f_{i,j} fi,j 表示满 i i i 位数,有 j j j 个非 0 0 0 位
采用记忆化搜索,详见代码
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)()
int num[25],f[25][5];
// u表示当前位数,st表示当前的j,limit表示是否有高位限制
int dfs(int u,int st,bool limit)
{
if(!u)return 1;
if(!limit&&f[u][st]!=INF)
return f[u][st]; // 记忆化
int up=limit?num[u]:9,ans=0;
for(int i=0; i<=up; i++)
{
if(!i)ans+=dfs(u-1,st,limit&&num[u]==i);
else if(st!=3)ans+=dfs(u-1,st+1,limit&&num[u]==i);
}
if(!limit) f[u][st]=ans; // 只需记录无高位限制的
return ans;
}
int solve(int x)
{
int len=0;
while(x>0)
{
num[++len]=x%10;
x/=10;
}
return dfs(len,0,1);
}
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
memset(f,0x3f,sizeof(f));
int Q;cin >> Q;
while(Q--)
{
int l,r;
cin >> l >> r;
cout << solve(r)-solve(l-1) << '\n';
}
return 0;
}
参考文献
[1] https://www.luogu.com.cn/blog/rated/solution-cf1036c
转载请说明出处
边栏推荐
- MVVM of WPF
- 杰理之蓝牙设备想要发送数据给手机,需要手机先打开 notify 通道【篇】
- You deserve this high-value open-source third-party Netease cloud music player
- Memory error during variable parameter overload
- 【mysql学习笔记29】触发器
- Internal and external troubles of "boring ape" bayc
- supervisor 使用文档
- js对象获取属性的方法(.和[]方式)
- Typescript variable scope
- OpenGL ES 学习初识(1)
猜你喜欢
[MySQL learning notes 32] mvcc
word中如何删除某符号前面或后面所有的文字
软件测试界的三无简历,企业拿什么来招聘你,石沉大海的简历
Jerry's ad series MIDI function description [chapter]
[window] when the Microsoft Store is deleted locally, how to reinstall it in three steps
C - Inheritance - polymorphism - virtual function member (lower)
微信公众号无限回调授权系统源码 全网首发
树莓派串口登录与SSH登录方法
SSM learning
Wechat official account infinite callback authorization system source code, launched in the whole network
随机推荐
【JDBC】快速入门教程
【线上问题处理】因代码造成mysql表死锁的问题,如何杀掉对应的进程
js对象获取属性的方法(.和[]方式)
After the hot update of uniapp, "mismatched versions may cause application exceptions" causes and Solutions
Fundamentals of C language 9: Functions
Chrome view page FPS
You deserve this high-value open-source third-party Netease cloud music player
杰理之BLE【篇】
If Jerry's Bluetooth device wants to send data to the mobile phone, the mobile phone needs to open the notify channel first [article]
变量的命名规则十二条
Seriously recommend several machine learning official account
杰理之需要修改 gatt 的 profile 定义【篇】
Supervisor usage document
The ECU of 21 Audi q5l 45tfsi brushes is upgraded to master special adjustment, and the horsepower is safely and stably increased to 305 horsepower
CDN acceleration and cracking anti-theft chain function
The way to learn go (II) basic types, variables and constants
Leetcode59. spiral matrix II (medium)
Leetcode 78: subset
超级浏览器是指纹浏览器吗?怎样选择一款好的超级浏览器?
TypeScript 接口属性