【[NOIP2021] 报数】题解
前言
于是我就愉快的 AC 了 。
希望审核能给我过了这篇题解 。
题目
题目传送门
正文
题目大意是数位中含有 7 的数不能报出 ， 并且它的倍数也不能报出 。 （ 7 也是数位中含有 7 的数 ）
所以我们要枚举出不能报出的数：
void init()
{
for(int i=1;i<=maxn;i++)
{
if(retire[i]) continue;
if(i%10==7||i/10%10==7||i/100%10==7||i/1000%10==7||i/10000%10==7||i/100000%10==7||i/1000000%10==7||i/10000000%10==7)
{
retire[i]=1;
for(int j=i+i;j<=maxn;j+=i)
{
retire[j]=1;
}
}
}
}预处理没了，接下来就好做了。
判断这个数是不是能报出的，如果不能，输出 -1 。 如果能 ， 就往后找可输出的数，然后输出。
但是 ， 如果给你一组数据 ：
100000
699999
699999
699999
699999
699999
…
699999
//有 100000 个 6999999那么肯定超时，所以我们要用到记忆化数组 。
long long find_sum[10010005];它可以将当前数要输出的数记忆下来 ， 等到又输入同样的数时 ， 直接输出 。
AC code：（有大量注释帮助理解）
#include<cstdio>
using namespace std;
inline long long read()//快读
{
long long s=0,f=1;
char a = getchar();
while(a<'0'||a>'9')
{
if(a=='-')
{
f=-1;
a=getchar();
}
}
while(a <= '9' && a >= '0') s = s * 10 + a - '0', a = getchar();
return s * f;
}
const long long maxn=1e7+1e4;//有些情况需报出比题目数据大的数，这些数也要处理
long long n,retire[maxn+5],AFO;
long long find_sum[maxn+5];//记忆化
void init()//枚举不可报出的数
{
for(int i=1;i<=maxn;i++)
{
if(retire[i]) continue;//已经处理过了，跳过
if(i%10==7||i/10%10==7||i/100%10==7||i/1000%10==7||i/10000%10==7||i/100000%10==7||i/1000000%10==7||i/10000000%10==7)//判断数中有没有7
{
retire[i]=1;//处理当前数
for(int j=i+i;j<=maxn;j+=i)
{
retire[j]=1;//将它的倍数也处理了
}
}
}
}
int main()
{
init();
n=read();
while(n--)
{
AFO=read();
if(retire[AFO]) printf("-1\n");//如果它不可报出
else
{
if(find_sum[AFO])//如果它报出过，直接输出应报出的数
{
printf("%d\n",find_sum[AFO]);
}
else
{
int JC=AFO+1;//不能报出当前数
while(retire[JC])//查找下一个可报出的数
{
JC++;
}
find_sum[AFO]=JC;//记忆化
printf("%d\n",find_sum[AFO]);
}
}
}
}