牛客网练习赛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

题目如上所示：这道题是提到最短路的转化，发现自己只要是有数据结构的题，就有点蒙，题目并不是太明显知道可有使用板子，但是看后就是一道最短路的板子题，可能是他隐藏的比较深把，也可以使用队列来实现；

代码：最短路：

int t; 
int dist[maxn][maxn];
int main(){ios::sync_with_stdio(false);for(int i =0; i < 233; i++){for(int j = 0; j < 233; j++){dist[i][j] = INF;}}for (int i=0;i<233;i++){dist[i][(i*i*i+i*i)%233]=1;dist[i][(i*i*i-i*i)%233]=1;}for(int k = 0; k < 233; k++){for(int i= 0; i < 233; i++){for(int j = 0; j < 233; j++){dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}cin >> t;ll a,b;while(t--){cin >> a >> b;if(a == b){cout << 0 << endl;continue;}if(b >= 233){cout << -1 << endl;continue;}if(dist[a % 233][b] == INF){cout  << -1 << endl;continue;}if(dist[a % 233][b] < INF){cout << dist[a%233][b] << endl;}}return 0;
}

代码：queue

int t;
ll d[maxn];
ll g(ll x){x = x % 233;return (((x*x)%233*((x+1)%233))%233);
}
ll f(ll x){x = x % 233;return (((x*x)%233*((x-1+233)%233))%233);
}
int main(){ios::sync_with_stdio(false);cin >> t;ll a,b;while(t--){cin >> a >> b;if(a == b){cout << 0 << endl;continue;}if(b >= 233){cout << -1 << endl;continue;}queue<ll>qq;memset(d,0,sizeof(d));d[f(a)] = 1;d[g(a)] = 1;qq.push(f(a));qq.push(g(a));while(!qq.empty()){ll tt = qq.front();qq.pop();if(d[f(tt)]==0){d[f(tt)] = d[tt] + 1;qq.push(f(tt));}if(d[g(tt)] == 0){d[g(tt)] = d[tt] + 1;qq.push(g(tt));}}if(d[b] == 0){cout << -1 << endl;}else{cout << d[b] << endl;}}return 0;
}