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
// #include
// #include
// #include
// #include
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)<<":"<" ";
#define dbg2(x) cerr<<(#x)<<":"<
#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 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<
            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];
        vectorint,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;
}