查看: 955|回复: 2

[C/C++] NOIP 2021 报数 题解

[复制链接]

1

技术

25

魅力

7

原创

管理员

Rank: 9Rank: 9Rank: 9

积分
11343
人气
297
分享
42

论坛元老优秀版主活跃会员最佳新人灌水之王

发表于 2021-11-26 20:13:56 | 显示全部楼层 |阅读模式
题目中说,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');
    }
}


Just do it.

1

技术

25

魅力

7

原创

管理员

Rank: 9Rank: 9Rank: 9

积分
11343
人气
297
分享
42

论坛元老优秀版主活跃会员最佳新人灌水之王

 楼主| 发表于 2021-11-26 20:14:27 | 显示全部楼层
注:本代码为本人编写,目前在洛谷上为最优解
Just do it.

1

技术

25

魅力

7

原创

管理员

Rank: 9Rank: 9Rank: 9

积分
11343
人气
297
分享
42

论坛元老优秀版主活跃会员最佳新人灌水之王

 楼主| 发表于 2021-11-26 23:48:40 | 显示全部楼层
还有一种方法是先把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');
    }
}

Just do it.
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

快速回复 返回顶部 返回列表