HDU2089 不要62 【数位DP】之另一种方法
上一种方法可以参见上一个这道题的题解。这题这份代码所采用的方法是我上一篇博文所介绍的。
注意的是，计数的时候因为不好统计，使用了逆向计数，即算出所有不吉利数的个数$cnt$，再用$x-cnt$即可。
# include <stdio.h>
# include <string.h>
using namespace std;
int dp[25][3];
int T;
//dp[i][0]:长度<=i的含62和4的数的个数
//dp[i][1]:长度为i,且最高位含有2的不含62和4的数的个数
//dp[i][2]:长度<=i的不含62和4的数个数
inline void getdp() {
memset(dp,0,sizeof(dp));
dp[0][2]=1;
for (int i=1;i<=10;++i) {
dp[i][0]=dp[i-1][0]*10+dp[i-1][2]+dp[i-1][1];
dp[i][1]=dp[i-1][2];
dp[i][2]=dp[i-1][2]*9-dp[i-1][1];
}
}
int d[25],dn;
inline void getd(int x) {
dn=0;memset(d,0,sizeof(d));
while(x) d[++dn]=x%10,x/=10;
}
int calc(int x) {
dn=0;memset(d,0,sizeof(d));int sum=x;
while(x) {
d[++dn]=x%10;
x/=10;
}
int cnt=0; bool flag=0;
for (int i=dn;i>=1;--i) {
cnt+=dp[i-1][0]*d[i];
if(flag) cnt+=dp[i-1][2]*d[i];
else {
if(d[i]>4) cnt+=dp[i-1][2];
if(d[i+1]==6&&d[i]>2) cnt+=dp[i][1];
if(d[i]>6) cnt+=dp[i-1][1];
if(d[i]==4||(d[i]==2&&d[i+1]==6)) flag=1;
}
}
if(flag) cnt++;
return sum-cnt;
}
int main() {
int x,y;
getdp();
while(~scanf("%d%d",&x,&y) && (x+y)) printf("%d\n",calc(y)-calc(x-1));
return 0;
}
2023年4月18日 18:38
10th Board Model Paper 2023 Aspirants who had Registered for the Board 10th Class Exam can Download the Previous Paper When Board Announces the Dates to Download the Question Paper. 10thmodelquestionspapers.in Board Question Papers will be Provided Very Soon Through Online Mode and all the Applicants Should Visit the Official Page Regularly for More Information Regarding Previous Paper, Examination Date. Check the Below Provided Details for More Information About the Board Model Paper.
2023年7月27日 22:12
La hora militar, también conocida como hora de 24 horas, es una forma de decir la hora utilizada por las fuerzas armadas y otras organizaciones. Es diferente del reloj normal de 12 horas que usa la mayoría de la gente. hora militar En horario militar, el día se divide en 24 horas, a partir de la medianoche (00:00) y hasta la medianoche siguiente. Cada hora está representada por un número de dos dígitos del 00 al 23.
2023年9月05日 15:02
Uttar Pradesh State Primary School Students who are Eagerly Searching for the UPMSP 1st Revised Syllabus 2024 can Stay on this webpage.Complete Subject wise SCERT UP Syllabus 2024 Pdf Format are Attached in the Following Sections for Free of Cost, Therefore, All the Students who are Going to Appear for the Examination can make use of the Information Provided here and Accordingly practice UP Board 1st Class Syllabus 2024 Complete Uttar Pradesh Syllabus 2024 given in order to give their best in the Examination.Uttar Pradesh Primary School Parents can use the Syllabus to Understand the Concepts and Prepare their Children for the Exam, Accordingly, The UP Board Syllabus 2024 All Subject Chapter Wise Students Prepare for the Upcoming Exam.