NOIP 2021 报数 题解

skystars

题目中说，7的倍数以及含有7的数与其倍数都不能报出

我们可以观察一下含有7的数（暂时不需要管其倍数）的特征

前几个满足条件的数依次为7、17、27、37、47、57、67、70、71、72、73、74、75、76、77、78、79、87、97、107、117

观察之后，我们能够发现，从7开始，依次增加10的数中都含有7，于是我们可以把这些数及其倍数标记一下。

70、170、270这种从70开始，依次增加100的数中也都含有7，同样也标记一下。

我们还能发现，从700开始，依次增加1000的数也含有7，我们可以发现一个规律：

从7*(10^n)开始，依次增加10*(10^n)的数中都含有7，依次标记它们还有它们的倍数即可。

同时，我们还能发现，类似70、71、72、73、74、75、76、77、78、79这种，从70*(10^n)+100*(10^n)*m到80*(10^n)-1+100*(10^n)*m的数中都含有7，同样也标记一下。

之后，我们倒着循环，将答案存放在f数组里，之后循环输出即可。

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;
unsigned int q[200005];
int f[10000055]; // 存放答案的数组
bitset<10000055> vis; // 是否为不能报出的数，使用bitset可节省内存并加快速度
char buf[1000000], * p1 = buf, * p2 = buf;
inline char nc() { // 读取一个字符
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int& x) // 快读，不解释
{
    x = 0;
    char s = nc();
    while (s < '0' || s > '9') s = nc();
    while (s >= '0' && s <= '9') { x = (x << 3) + (x << 1) + (s ^ 48); s = nc(); }
}
inline void read(unsigned int& x)
{
    x = 0;
    char s = nc();
    while (s < '0' || s > '9') s = nc();
    while (s >= '0' && s <= '9') { x = (x << 3) + (x << 1) + (s ^ 48); s = nc(); }
}
inline void print(int x) // 快输，也不解释
{
    if (x == -1) {
        fputs("-1", stdout);
        return;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
int main() {
    register int t;
    read(t);
    unsigned int start = 0; // 最大需要循环到的值
    for (unsigned int i = 0; i < t; ++i) {
        read(q[i]);
        start = max(start, q[i]);
    }
    start += 50;
    unsigned int a = 7, b = 10, c = 8, d;
    for (unsigned int i = 0; i < 7; ++i) {
        for (unsigned int j = a; j <= start; j += b) {
            if (vis[j]) continue;
            for (unsigned int k = j; k <= start; k += j) {
                vis[k] = true; // 标记
            }
        }
        if (i >= 1) {
            unsigned int v = 0;
            while (true) {
                if (a + v * b > start) break;
                d = c + v * b;
                if (d > start) d = start;
                for (unsigned int j = a + v * b; j < d; ++j) {
                    if (vis[j]) continue;
                    for (unsigned int k = j; k <= start; k += j) {
                        vis[k] = true; // 标记
                    }
                }
                ++v;
            }
        }
        a *= 10;
        b *= 10;
        c *= 10;
    }
    unsigned int last = 0;
    for (unsigned int i = start; i > 0; i--) { // 将答案存放到f数组里
        if (!vis[i]) {
            f[i] = last;
            last = i;
        }
        else
            f[i] = -1;
    }
    for (unsigned int i = 0; i < t; ++i) {
        print(f[q[i]]); // 输出
        putchar('\n');
    }
}

skystars

注：本代码为本人编写，目前在洛谷上为最优解

skystars

还有一种方法是先把7的倍数标记出来，然后再循环，把含7的数及其倍数标记出来，并且把能够报出的数放到一个数组里面

查找时使用upper_bound二分查找，虽然在洛谷的民间数据里面运行速度较慢些，但是根据我自己生成的加强数据来看，这种方法会稍微快一些，而且占用内存也小得多

[C++] 纯文本查看 复制代码

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <bitset>
using namespace std;
unsigned int db[763410];
bitset<10000004> vis;
char buf[1000000], * p1 = buf, * p2 = buf;
inline char nc() {
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1000000, stdin), p1 == p2) ? EOF : *p1++;
}
inline void read(int& x)
{
    x = 0;
    char s = nc();
    while (s < '0' || s > '9') s = nc();
    while (s >= '0' && s <= '9') { x = (x << 3) + (x << 1) + (s ^ 48); s = nc(); }
}
inline void print(unsigned int x)
{
    //if (x < 0) putchar('-'), x = -x;
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
int main() {
    register int index = 0;
    register int t;
    read(t);
    int start = 10000003;
    if (t <= 10) start = 105; // 根据数据范围提示确定要筛到的位置
    else if (t <= 100) start = 1005;
    else if (t <= 1000) start = 10005;
    else if (t <= 10000) start = 200005;
    for (unsigned int i = 7; i <= start; i += 28) { // 优化
        vis[i] = true;
        vis[i + 7] = true;
        vis[i + 14] = true;
        vis[i + 21] = true;
    }
    for (int i = 1; i <= 6; i++) db[i] = i;
    index = 7;
    for (unsigned int i = 8; i <= start; i++) {
        if (vis[i]) {
            continue;
        }
        register unsigned int t = i;
        bool flag = false;
        while (t) { // 是否含有7
            if (t % 10 == 7) {
                flag = true;
                break;
            }
            t /= 10;
        }
        if (flag) {
            for (int j = i; j <= start; j += i) {
                vis[j] = true;
            }
        }
        else {
            db[index++] = i;
        }
    }
    register int x;
    while (t--) {
        read(x);
        if (vis[x]) {
            puts("-1");
            continue;
        }
        unsigned int r = upper_bound(db, db + index, x) - db;
        print(db[r]);
        putchar('\n');
    }
}