上海计算机学会2021年4月月赛C++乙组T3平安数

上海计算机学会2021年4月月赛C++乙组T3平安数

平安数

内存限制: 256 Mb时间限制: 1000 ms

题目描述

若一个整数在十进制下不含 13 作为子串，则称它为平安数，例如 123 是平安数，但 2132 不是平安数。给定一个 n，请计算从 1 到 n 有多少个平安数。

输入格式

单个整数：表示 n。

输出格式

单个整数：表示 1 到 n 之间有多少整数的十进制表示不含 13 子串。

数据范围

• 对于 30% 的数据：1≤n≤106；
• 对于 60% 的数据：1≤n≤109；
• 对于 100% 的数据：1≤n≤2^63−1。

样例数据

 输入:
20
输出:
19
输入:
200
输出:
188
说明:
13、113以及130到139都不是平安数

解析：

暴力解可得60分，代码如下：

#include <bits/stdc++.h>
using namespace std;
long long n;
long long ans=0;
int main() {cin>>n;for(long long i=1;i<=n;i++){bool flag=1;//假定i不含有13long long t=i;while (t>=10){if (t%100==13){//如果有13flag=0;break;}t/=10;}if (flag==1){//如果没有13，答案加一ans++;}}cout<<ans;return 0;
}

 正解用到数位dp（感谢上海浦东新区民办远翔实验学校张逸凡老师提供的解题思路）

详见代码：

#include <bits/stdc++.h>
using namespace std;
long long n;
long long ans=0;
int len=0;//n的位数
int f[20];//f[i]保存从各位开始数第i位的数字
//dp[i][0]表示i位数中首位不为1的数字中有多少幸运数
//dp[i][1]表示i位数中首位为1的数字中有多少幸运数
long long dp[20][2];
void init(long long x){//预处理dp数组while(x>0){len++;f[len]=x%10;x/=10;}dp[1][0]=8;dp[1][1]=1;for(int i=2;i<=len;i++){//首位不为1，可以选8种（除0,1）//次位不为1时，作为首位可以选（2-9共8个数字）//作为次位可以选多选个0,即dp[i-1][0]/8*9//再加上次位为1的情况dp[i-1][1]dp[i][0]=8*(dp[i-1][0]/8*9+dp[i-1][1]);//首位为1的情况次位不能为3，但可以为0，即dp[i-1][0]//加上次位为1，即dp[i-1][1]dp[i][1]=dp[i-1][0]+dp[i-1][1];}
}
int main() {cin>>n;init(n);//求1~第高2位所有平安数for(int i=1;i<len;i++){ans+=dp[i][0]+dp[i][1];}//再加上最高位开始逐一位限制的平安数个数for(int pos=len;pos>=1;pos--){//当前位的后两位数为1 3时,不再找if(f[pos+2]==1&&f[pos+1]==3) break;//最高位不能放0，个位没有极限限制for(int k=(0 + pos==len);k<(f[pos]+(pos==1));k++){//当前位的高一位为1且当前位为3时不为平安数if(f[pos+1]==1&&k==3) continue;if(k!=1){ans+=dp[pos][0]/8;}else{ans+=dp[pos][1];}}}cout<<ans;return 0;
}