第一次做站外题的题解/jd
为什么要写这一篇题解呢，是因为它卡了我很久，好不容易AC了（我太蒟，大佬勿喷）
我们开始吧！
一.审题
题目描述很清楚了，大家自己看吧
二.代码&讲解
这里我会给大家上几个不同的思路以及它们的代码
思路1.队列
#include<cstdio>
#include<queue>
using namespace std;
queue<int> q;
int k,x;
bool flag;
int main()
{
scanf("%d,%d",&k,&x);
q.push(k);
while(!flag)
{
if(q.front()==x) flag=true;
if(q.front()>x) break;
q.push(q.front()*2+1);
q.push(q.front()*3+1);
q.pop();
}
if(flag) printf("YES");
else printf("NO");
return 0;
}
这里很明显，就是用队列存储\(M\)集合内每一个数
分数：14
思路2.递归
#include<cstdio>
int k,x;
bool check(int y)
{
if(y<=100000)
{
if(y==x) return true;
if(check(2*y+1)) return true;
if(check(3*y+1)) return true;
}
return false;
}
int main()
{
scanf("%d%d",&k,&x);
if(check(x)) printf("YES");
else printf("NO");
return 0;
}
这里直接强行递归，边界为100000 \((x<100000)\)
分数：12
思路3.递归+bool数组
受到这个题解的启发，我抄写了这个代码
#include<cstdio>
int k,x;
bool f[1000000];
void check(int y)
{
if(y<=1000000)
{
f[y]=true;
check(2*y+1);
check(3*y+1);
}
else return;
}
int main()
{
scanf("%d%d",&k,&x);
check(k);
if(f[x]) printf("YES");
else printf("NO");
return 0;
}
表面上思路没问题，但只有9分的好成绩
到这里，我已经卡了2小时了（中间翻来覆去地修改参数嘤嘤嘤）
突然，我灵光一闪：\(x\)可能小于\(k\)啊！
最终代码
#include<cstdio>
#include <cmath>
using namespace std;
int k,x;
bool f[1000000];
void b(int y)
{
if(y<=1000000)
{
f[y]=true;
b(2*y+1);
b(3*y+1);
}
else return;
}
void s(int y)
{
if(y>0)
{
f[y]=true;
double a=(y-1)/2,b=(y-1)/3;
if(a-round(a)<0.000000000000001) s((y-1)/2);
if(b-round(b)<0.000000000000001) s((y-1)/3);
}
else return;
}
int main()
{
scanf("%d,%d",&k,&x);
b(k);
s(k);
if(f[x]) printf("YES");
else printf("NO");
return 0;
}
这里给大家一个判断是否为整数的办法（大家应该能看出来吧）传送门
以下归纳：
函数：
bool check(int n)
{
double a=n;
if(a-round(a)<0.000000000000001) return true;
else return false;
}
这里\(round\)函数是在cmath头文件里的，功能:四舍五入
分数：20！
这个就是这道题的题解啦！感谢阅读！