【NOIP2021】报数题解
2021/11/25 23:15:46
本文主要是介绍【NOIP2021】报数题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
本蒟蒻的第一篇题解
此题作为今年NOIP唯一一道略简单 普及— 难度的题,做法与某种强大的素数筛法(埃氏筛法)雷同,具体做法如下:
我们先来看题目:
如果下一个报的数是 7 的倍数,或十进制表示中含有数字 7,就必须跳过这个数。任何一个十进制中含有数字 7 的数,它的所有倍数都不能报出来。
我们可以发现,这和埃氏筛法的思想很像,其实就是模拟,我们可以用一个vis数组来记录一个数是否应该被跳过。
看代码:
void init () { for (int i = 1; i <= 10000000; i++) { if (!vis[i] && (seven(i) || i == 7)) { for (int j = 1; i * j <= inf; j++) { vis[i * j] = true; } } } }
其中的seven函数是用来判断这个数中是否包含7的
bool seven (int x) { while (x) { if (x % 10 == 7) return true; x /= 10; } return false; }
这样我们就预处理好了10^7以内的数是否应该被跳过
于是乎,我就交了一发这样的代码:
#include <iostream> using namespace std; int t, x; bool vis[10000010]; const int inf = 10000010; bool seven (int x) { while (x) { if (x % 10 == 7) { return true; } x /= 10; } return false; } void init () { for (int i = 1; i <= 10000000; i++) { if (!vis[i] && (seven(i) || i == 7)) { for (int j = 1; i * j <= inf; j++) { vis[i * j] = true; } } } } int main () { init(); scanf("%d", &t); while (t--) { scanf("%d", &x); if (vis[x]) printf("-1\n"); else { for (int i = x + 1; i; i++) { if (!vis[i]) { printf("%d\n", i); break; } } } } return 0; }
你以为这样就结束了吗?
非也,非也。
我荣幸地拿到了70分,T了三个点。
经过我详细的计算粗略的猜测,我觉得可能会多次询问同一个数,我就开始改进while循环中的代码。我想到了老师说过的记忆化搜索(用空间换时间玄学大法),就用f数组来记录已经询问过的数。
没想到真的就这样卡过去了。。。
附上AC代码
#include <iostream> using namespace std; int t, x; bool vis[10000010]; int f[10000010]; const int inf = 10000010; bool seven (int x) { while (x) { if (x % 10 == 7) return true; x /= 10; } return false; } void init () { for (int i = 1; i <= 10000000; i++) { if (!vis[i] && (seven(i) || i == 7)) { for (int j = 1; i * j <= inf; j++) { vis[i * j] = true; } } } } int main () { init(); scanf("%d", &t); while (t--) { scanf("%d", &x); if (f[x] != 0) { printf("%d\n", f[x]); continue; } if (vis[x]) printf("-1\n"); else { for (int i = x + 1; i; i++) { if (!vis[i]) { printf("%d\n", i); f[x] = i; break; } } } } return 0; }
这篇关于【NOIP2021】报数题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-10-06小米11i印度快充版ROM合集:极致体验,超越期待
- 2024-10-06【ROM下载】小米11i 5G 印度版系统, 疾速跃迁,定义新速度
- 2024-10-06【ROM下载】小米 11 青春活力版,青春无极限,活力全开
- 2024-10-05小米13T Pro系统合集:性能与摄影的极致融合,值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南:打造简单易懂的API接口
- 2024-10-01初学者指南:了解和使用Server Action
- 2024-10-01Server Component入门指南:搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求