题解 P1635 【跳跃】

· · 题解

看到没有c++，我这个蒟蒻就来丰富一下题解区。

分析4x+3和8x+7

发现2（2x+1）+1==4x+3, 2（4x+3）+1==8x+7；

发现可以以2x+1为单位进行跳跃

记录小跳跃次数，如果大于300000，就结束；

当到达目标位置时，看一下小跳跃次数，如果%3==0

跳跃次数/3为答案，如果不是0，有两种情况，余1，余2

发现余2跳一次4x+3就可以到达了，余1少跳1次8x+7，改为两次4x+3即可

所以将/3后的结果加1即可

代码如下

#include<iostream>
#include<cstdio>
using namespace std;
int ans=0;
const int mod=1000000007;
int dep=0;
bool flag=0;
void slove(int x)
{
    if(ans==310000)
    {
        flag=1;
        return;
    }
    ans++;
    int y=(2*(x%mod)+1)%mod;
    //cout<<ans<<" "<<y<<endl;
    if(y==0)
    {
        if(ans%3==0)
            ans/=3;
        else
            ans=ans/3+1;
        if(ans>100000)
            flag=1;
    }
    else
    slove(y);
    return;
}
int main()
{
    int x0;
    cin>>x0;
    slove(x0);
    if(!flag)
    cout<<ans<<endl;
    else
    cout<<-1<<endl;
    return 0;
}