Codeforces Round 901 (Div. 1) B. Jellyfish and Math(思维题/bfs)

题目

t(t<=1e5)组样例，每次给出a,b,c,d,m(0<=a,b,c,d,m<2的30次方)

初始时，(x,y)=(a,b)，每次操作，你可以执行以下四种操作之一

①x=x&y，&为与

②x=x|y，|为或

③y=x^y，^为异或

④y=y^m，^为异或

求将(x,y)=(c,d)的最小操作数，如果无法实现，输出-1

思路来源

乱搞AC & tanao学弟

题解

按位考虑每一位时，有如下转移图，

注意到，将m也考虑进去，会构成一个三元组，只有(0,0,0)到(1,1,1)八种可能

30位里只有这8种可能，由于每次操作相同的可能的转移是一样的，

所以，如果相同的(x>>i&1,y>>i&1,w>>&1)对应的(c>>i&1,d>>i&1)不同时，直接无解

然后，可以只留8位，将8位标号id=0-7

每个标号id都有出现和没出现两种情况，一共2的8次方，256种情况

所以，可以对于第i(0<=i<256)情况预处理，

初始的(a,b)和i是对应的，转化的(c,d)也都在[0,256)之间

最多有256种情况*256*256种(c,d)值，每次转移有四种情况

预处理之后，对于1e5组询问，O(1)回答即可

代码中用的是数组记忆化，和预处理的效果是等价的

复杂度O(256*256*256*4+1e5)

代码

#include<bits/stdc++.h>
// #include<iostream>
// #include<vector>
// #include<queue>
// #include<map>
using namespace std;
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;
typedef double db;
typedef pair<int,int> P;
#define fi first
#define se second
#define dbg(x) cerr<<(#x)<<":"<<x<<" ";
#define dbg2(x) cerr<<(#x)<<":"<<x<<endl;
#define SZ(a) (int)(a.size())
#define sci(a) scanf("%d",&(a))
#define pb push_back
#define pt(a) printf("%d",a);
#define pte(a) printf("%d\n",a)
#define ptlle(a) printf("%lld\n",a)
#define debug(...) fprintf(stderr, __VA_ARGS__)
//std::mt19937_64 gen(std::chrono::system_clock::now().time_since_epoch().count());
//ll get(ll l, ll r) { std::uniform_int_distribution<ll> dist(l, r); return dist(gen); }
const int N=1e5+10,M=256,INF=0x3f3f3f3f;
int t,a,b,c,d,m,dp[M][M*M];
int f(int x,int y,int z){return x*4+2*y+z;
}
int g(int x,int y){return x*256+y;
}
int sol(){map<int,array<int,2>>p;rep(i,0,30){int u=a>>i&1,v=b>>i&1,w=m>>i&1,x=c>>i&1,y=d>>i&1,z=f(u,v,w);if(p.count(z)){if(p[z][0]!=x || p[z][1]!=y)return -1;}else{p[z]={x,y};}}int h=0,na=0,nb=0,nc=0,nd=0,nm=0;rep(i,0,7){if(p.count(i)){int u=i>>2&1,v=i>>1&1,w=i&1;h|=1<<i;nc=nc<<1|p[i][0],nd=nd<<1|p[i][1];//printf("i:%d u:%d v:%d w:%d x:%d y:%d\n",i,u,v,w,p[i][0],p[i][1]);na=na<<1|u,nb=nb<<1|v,nm=nm<<1|w;}}int s=g(na,nb),e=g(nc,nd);if(dp[h][s]==0){return dp[h][e];}//printf("h:%d na:%d nb:%d nc:%d nd:%d\n",h,na,nb,nc,nd);dp[h][s]=0;queue<int>q;q.push(s);while(!q.empty()){int z=q.front();q.pop();int x=z/M,y=z%M;//if(x==nc && y==nd)return dp[z];vector<array<int,2>> nex={{x&y,y},{x|y,y},{x,x^y},{x,y^nm}};for(auto &w:nex){int nz=g(w[0],w[1]);if(dp[h][nz]<0){dp[h][nz]=dp[h][z]+1;q.push(nz);}}}return dp[h][e];
}
int main(){// freopen("qiwang.in","r",stdin);// freopen("qiwang.out","w",stdout);memset(dp,-1,sizeof dp);sci(t);while(t--){sci(a),sci(b),sci(c),sci(d),sci(m);printf("%d\n",sol());}return 0;
}