题解(附带免费讲解)
2024-02-12 21:53:35
发布于:湖南
39阅读
0回复
0点赞
首先我们读题,意思是:小z和小r玩一个报数游戏promax原神版:任何一个十进制中含有数字7 的数,它的所有倍数都不能报出来,必须跳过,所以会出现连续跳过很多次的情况。现在让我们找报完一个数后应该报的下一个数。
我们可以看到,T最大是20万,最大的数为100万,所以真的按照游戏一个一个找的话你就输了。
那有什么办法呢?
我们先联想到批量找质数:一般来说是用埃式筛法,就是把合数都筛掉,剩下的就是质数了。
for(int i = 2; i * i <= n; i ++){
if(!vis[i]){//避免重复,如果已经是合数就不筛
for(int j = i * 2; j <= n; j += i){//i的倍数肯定是合数
vis[j] = 1;
}
}
}
如果vis里还有元素为0(除0 1以外),那它的下标就是质数。
那么,这种方法能应用到这道题上吗?
再仔细看看题:含有数字7 的数,它的所有倍数都不能报出来。
所以,我们可以把含有数字7的数的倍数都筛掉,剩下的就是可以报出的数了。
代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 10000005 + 10005;
bool vis[maxn];
bool check(int x){
while(x){
if(x % 10 == 7) return 1;//如果有7,就是要准备去筛的数
x /= 10;
}return 0;
}
void _init(){
for(int i = 1; i <= maxn; i++){
if(check(i) && !vis[i]){//如果没被遍历过而且符合check
for(int j = i; j <= maxn; j += i){//开筛!!!
vis[j] = 1;
}
}
}
}
不会有人真的拿这段代码去提交了吧嘿嘿
然后再补上mian:
int main(){
int t, x;
cin >> t;
_init();//首先筛一下,因为t巨大,不能一个一个便利
while(t--){
cin >> x;
if(vis[x]){//如果被筛掉了,说明这个是其中一个含7的数的倍数
cout << "-1\n";
continue;
}for(int i = x + 1;; i++){//否则就找下一个没被筛掉的数
if(!vis[i]){
cout << i << endl;
break;
}
}
}
return 0;
}
OK来合并起来测试:
成功TLE了
什么???已经这么优化了还超时?????
你先别急
如果一个一个找下一个数的话,万一有两个数间隔很大怎么办?
所以我们还得想办法
定义一个to_next数组吧,其中的下标如果符合条件的话,对应的元素就指向下一个数(完美解决!)
to_next[_] = i;//下标对应的元素是符合条件的下一个数
_ = i;//更新下标
好的,然后再稍微改一下mian函数里的
cin >> x;
if(vis[x]){
cout << "-1\n";
}else cout << to_next[x] << endl;//否则输出下标对应的元素,即x的下一个数
完整版AC代码:
#include <iostream>
#include <cstdio>
using namespace std;
const int maxn = 10000005 + 10005;
bool vis[maxn];
int to_next[maxn];
bool check(int x){
while(x){
if(x % 10 == 7) return 1;//如果有7,就是要准备去筛的数
x /= 10;
}return 0;
}
void _init(){
int _ = 0;
for(int i = 1; i <= maxn; i++){
if(vis[i]){//直接跳过筛过的数
continue;
}
if(check(i)){//符合条件?
for(int j = i; j <= maxn; j += i){//开筛!!!
vis[j] = 1;
}
}else{//否则就是可以报的数
to_next[_] = i;//下标对应的元素是符合条件的下一个数
_ = i;//更新下标
}
}
}
int main(){
int t, x;
cin >> t;
_init();
while(t--){
cin >> x;
if(vis[x]){
cout << "-1\n";//如果被筛掉了,说明这个是其中一个含7的数的倍数
}else cout << to_next[x] << endl;//否则输出下标对应的元素,即x的下一个数
}
return 0;
}
ok成功AC!
看完了点个赞呗~
全部评论 1
注:除了最后的to_next数组其他都是自己想出来的
2024-02-13 来自 湖南
01周前 来自 广东
0啊,真tle了
1周前 来自 广东
0哦
1周前 来自 广东
1
有帮助,赞一个