牛客练习赛35

牛客练习赛35

题目描述

一位客人来到了此花亭，给了女服务员柚一个数学问题：我们有两个函数，F(X)函数可以让X变成（X*X*X+X*X）mod 233。G(X)函数可以让X变成（X*X*X-X*X）mod 233，我们可以任意的对A使用F(X),和G(X)，问最少需要多少次使用这两个函数让A变成B。

输入描述:

第一行输入一个T，表示T组案例（T<100000），然后输入两个整数A,B，表示我们需要把A变成B。（0<=A<=2000000000，0<=B<=2000000000）

输出描述:

输出一个整数表示从A到B最少需要多少次操作，如果不能请输出-1.

示例1

输入

复制

1
2 186

输出

复制

2

说明

我们首先使用F(X)，将2变成(2*2*2+2*2)mod 233=12。然后我们再将12通过G(X)，变成(12*12*12-12*12)mod 233=186

方法一：floyd

思路：

设dp[i][j]:=从数i到达数j的最少要多少次操作。

特判：

if(a==b)//输出0

else if(b>=233)//输出-1

若此时a>=233，那么把a通过P函数和G函数变形一次就小于233了，跳数+1

（比赛的时候，我迷之认为a>=233的话，按a%233算就好了……脑子有坑！）

特判完后，dp[i][j]都是小于233的，用floyd求出每个数到每个数的最小操作次数，然后，输出即可！

代码如下：

#include<iostream>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<sstream>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1const int N=5005,mod=233;
int vis[300];
const ll INF=999999999999999999;
ll a,b,ans;
ll dp[300][300];
ll P(ll x){x%=mod;return ((x*x%mod*x)%mod+x*x%mod)%mod;
}ll G(ll x){x%=mod;return ((x*x%mod*x)%mod-x*x%mod+mod)%mod;
}void floyd(){for(int i=0;i<233;i++){//初始化，每两个点都是不可达，若i==j，则为0for(int j=0;j<233;j++){if(i==j)dp[i][j]=0;dp[i][j]=INF;}}for(int i=0;i<233;i++){//初始化，把数0到232，一步可达的情况都找出int x=P(i);int y=G(i);dp[i][x]=1;dp[i][y]=1;}for(int k=0;k<233;k++){//由已知推未知for(int i=0;i<233;i++){for(int j=0;j<233;j++){dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);}}}
}int main(){int t;floyd();scanf("%d",&t);while(t--){scanf("%lld%lld",&a,&b);if(a==b){printf("0n");continue;}if(b>=mod){printf("-1n");continue;}if(a>=233){ll c=P(a);ll d=G(a);if(c==b||d==b){printf("1n");continue;}//特判相等的情况if(dp[c][b]==INF&&dp[d][b]==INF){printf("-1n");continue;}//a转移到状态c和d，c和d没有一个可以到b的，输出-1printf("%lldn",min(dp[c][b],dp[d][b])+1);//求最小的操作数}else{if(dp[a][b]!=INF)printf("%lldn",dp[a][b]);else printf("-1n");}}
}

方法二：bfs

思路：

（太久没敲bfs都忘了qwq）

先列出来一坨概念，看完概念就会敲了！

bfs总是搜索距离初始状态最近的状态。也就是说，它是按照开始状态->只需1次就可以到达的所有状态->只需2次就可以到达的所有状态->……这样的顺序搜索的，so，bfs总是能最先找到符合的情况，适合这道题，求最小的操作次数！

代码如下：

#include<iostream>
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#include<stack>
#include<sstream>
using namespace std;
#define ll long long
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1const int N=5005,mod=233;
int vis[300];
const ll INF=999999999999999999;
ll a,b;
struct A{ll now,num;
};
ll P(ll x){return ((x*x%mod*x)%mod+x*x%mod)%mod;
}ll G(ll x){return ((x*x%mod*x)%mod-x*x%mod+mod)%mod;
}int main(){int t;scanf("%d",&t);while(t--){memset(vis,0,sizeof(vis));scanf("%lld%lld",&a,&b);if(a==b){printf("0n");continue;}if(b>=mod){printf("-1n");continue;}queue<A>qqq;if(a>=233){ll c=P(a);ll d=G(a);vis[c]=1;vis[d]=1;qqq.push(A{c,1});qqq.push(A{d,1});}else{vis[a]=1;qqq.push(A{a,0});}ll ans=INF;//把出现过的状态都标记一下，只入队没出现过的状态while(!pty()){//队列不为空A tmp=qqq.front();qqq.pop();w==b){ans=tmp.num;break;}else {ll t1=w),t2=w);if(!vis[t1])qqq.push(A{t1,tmp.num+1});if(!vis[t2])qqq.push(A{t2,tmp.num+1});vis[t1]=1;vis[t2]=1;}}if(ans==INF)printf("-1n");else printf("%lldn",ans);}
}

小结：牛客练习赛还是只签了到，其实这题也很简单啊，我还是基础知识太不牢固了！！！qwq