当前位置:网站首页>Cf1036c class numbers solution
Cf1036c class numbers solution
2022-07-06 07:29:00 【q779】
CF1036C Classy Numbers Answer key
Topic link :CF1036C Classy Numbers
The question : Define a number as “ Good number ”, If and only if its decimal representation does not exceed 3 3 3 A digital 1 ∼ 9 1 \sim 9 1∼9
for instance : 4 , 200000 , 10203 4,200000,10203 4,200000,10203 yes “ Good number ”, However 4231 , 102306 , 7277420000 4231,102306,7277420000 4231,102306,7277420000 No
Given [ l , r ] [l,r] [l,r], Ask how many x x x bring l ≤ x ≤ r l \le x \le r l≤x≤r, And x x x yes “ Good number ”
Altogether T ( 1 ≤ T ≤ 1 0 4 ) T(1 \le T \le 10^{4}) T(1≤T≤104) Group data , For each inquiry , Output an integer on a line to represent the answer
1 ≤ l i ≤ r i ≤ 1 0 18 1 \le l_i \le r_i \le 10^{18} 1≤li≤ri≤1018
General figures dp It can be used to solve ∑ i = l r f ( i ) \sum _{i=l}^{r} f(i) ∑i=lrf(i) The problem of ,
among f ( i ) f(i) f(i) As with the i i i A function or determinant related to the digits of
This question is slightly distorted , Then we will naturally record the occurrence of figures
set up f i , j f_{i,j} fi,j It means full i i i digit , Yes j j j A non 0 0 0 position
Using memory search , See the code for details.
#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 Indicates the current number of digits ,st Represents the current j,limit Indicates whether there is a high limit
int dfs(int u,int st,bool limit)
{
if(!u)return 1;
if(!limit&&f[u][st]!=INF)
return f[u][st]; // Memorize
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; // Just record what has no upper limit
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;
}
reference
[1] https://www.luogu.com.cn/blog/rated/solution-cf1036c
Reprint please explain the source
边栏推荐
- Three no resumes in the software testing industry. What does the enterprise use to recruit you? Shichendahai's resume
- Typescript void base type
- Markdown 中设置图片图注
- SSM学习
- 软件测试界的三无简历,企业拿什么来招聘你,石沉大海的简历
- js对象获取属性的方法(.和[]方式)
- Jerry needs to modify the profile definition of GATT [chapter]
- How can word delete English only and keep Chinese or delete Chinese and keep English
- 杰理之AD 系列 MIDI 功能说明【篇】
- How MySQL merges data
猜你喜欢
navicat如何导入MySQL脚本
When the Jericho development board is powered on, you can open the NRF app with your mobile phone [article]
How to delete all the words before or after a symbol in word
Summary of Digital IC design written examination questions (I)
杰理之如若需要大包发送,需要手机端修改 MTU【篇】
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
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
Go learning --- use reflection to judge whether the value is valid
TypeScript接口与泛型的使用
mysql如何合并数据
随机推荐
Go learning --- use reflection to judge whether the value is valid
Scala语言学习-08-抽象类
Mise en œuvre du langage leecode - C - 15. Somme des trois chiffres - - - - - idées à améliorer
word中如何删除某符号前面或后面所有的文字
Relevant introduction of clip image
leecode-C語言實現-15. 三數之和------思路待改進版
[MySQL learning notes 30] lock (non tutorial)
ORACLE列转行--某字段按指定分隔符转多行
Rust language - receive command line parameter instances
[JDBC] quick start tutorial
SSM learning
Introduction to the basics of network security
Bloom taxonomy
Typescript variable scope
Jerry's general penetration test - do data transmission with app Communication [article]
How can word delete English only and keep Chinese or delete Chinese and keep English
杰理之BLE【篇】
Do you really think binary search is easy
NiO programming introduction
C # display the list control, select the file to obtain the file path and filter the file extension, and RichTextBox displays the data