题解 P1781【Number】

Drinkkk · 2019-07-09 19:33:08 · 个人记录

\tt Description

给出一个整数 x ，你可以对 x 进行两种操作。

1. 将 x 变成 (4x+3)

2. 将 x 变成 (8x+7)

那么最少通过多少次操作，能够使得 x 是 (10^9+7) 的倍数？

数据保证答案不超过 100000 。

\tt Solution

• 方法 1 ： 暴力 + 贪心

考虑使用 暴力 求解。

通过观察可以发现：

然后我们可以定义一个 3 操作：

然后 1 操作和 2 操作就分别等价于 2 次和 3 次 3 操作。

然后我们就可以先求出来需要多少次 3 操作就可以使 x 变成 (10^9+7) 的倍数，然后将 3 操作转换为 1 操作和 2 操作，并且用 贪心 的思想让 2 操作尽可能地多即可。

时间复杂度 O(\text{答案}) 。

• 方法 2 ：bfs + map + O2

考虑使用 f[i] 来表示当 x 变为 i 所需的最小步数。

考虑到 i 可能会很大，所以要用 map 来存储。

然后因为 map 很慢，所以要开 O2 才能够过掉这道题目。

• 方法 3 ：哈希 + bfs

其实就是用哈希来代替 map 。

因为我的哈希 A 不了，所以就放一下 No11101111000101100 大佬的代码（已获得授权）。

然后这道题目就做完了。

\tt Code

• 方法 1 ：

#include <cstdio>
int main()
{
    long long ans=0,dq=0,x=0;
    scanf("%lld",&x);
    for(long long i=1; ;i++)
    {
        x=(2*x+1)%1000000007;
        if(x==0)
        {
            dq=i;
            break;
        }
    }
    while(dq%3!=0)
    {
        dq-=2;
        ans++;
    }
    printf("%lld",ans+dq/3);
    return 0;
}

• 方法 2 ：

#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <map>
long long dl[1000001] ;
std::map< int , long long > f ;
long long min(long long x,long long y)
{
    return x<y?x:y;
}
void bfs(long long st)
{
    long long tou = 1 , wei = 2 ;
    dl[ 1 ] = st ;
    while( tou != wei )
    {
        long long x  = dl[tou];
        if(x==0)
        {
            printf( "%lld" , f[ x ] - 1 ) ;
            break;
        }
        long long a  = (4*x+3) % 1000000007 , b = (8*x+7) % 1000000007 ;
        if( f[ a ] > f[ x ] + 1 || f[ a ] == 0 )
        {
            f[ a ] = f[ x ] + 1 ;
            dl[wei] = a ;
            wei ++ ;
            if( wei > 1000000 )
            {
                wei = 1 ;
            }
        }
        if( f[ b ] > f[ x ] + 1  || f[ b ] == 0 )
        {
            f[ b ] = f[ x ] + 1 ;
            dl[wei] = b ;
            wei ++ ;
            if( wei > 1000000 )
            {
                wei = 1 ;
            }
        }
        tou ++ ;
        if( tou > 1000000 )
        {
            tou = 1 ;
        }
    }
}
int main()
{
    long long st = 0 ;
    scanf("%lld" , &st ) ;
    f[ st ] = 1 ;
    bfs( st ) ;
    return 0;
}

• 方法 3 ：

#pragma GCC optimize (3)
#include<cstdio>
#include<queue>
using namespace std;typedef long long ll;const ll mod=1000000007,hmod=1e6+7;
struct hnote{ll x;hnote *next;hnote(){next=NULL;}~hnote(){delete next;}}*ha[hmod];
inline bool hash_check(ll x){for(hnote *i=ha[x%hmod];i!=NULL;i=i->next){if(i->x==x){return 1;}}return 0;}
inline void hash_add(ll x){hnote *t=new hnote;t->x=x;t->next=ha[x%hmod];ha[x%hmod]=t;return;}
struct qnote{ll num,st;qnote(ll nu,ll s){num=nu;st=s;}};queue<qnote> q;
inline ll fun(ll x,ll a,ll b){return (a*x%mod+b)%mod;}inline void add(qnote x,ll a,ll b){const ll t=fun(x.num,a,b);if(!hash_check(t)){hash_add(t);q.push(qnote(t,x.st+1));}return;}
int main()
{
//  freopen("Number.in","r",stdin);freopen("Number.out","w",stdout);
    for(ll i=0;i<hmod;i++){ha[i]=NULL;}
    ll n;scanf("%lld",&n);add(qnote(n,-1),1,0);while(!q.empty()){const qnote x=q.front();q.pop();if(x.num==0){printf("%lld",x.st);break;}add(x,4,3);add(x,8,7);}
    return 0;
}