CF1874B

wosile · 2023-10-02 11:33:37 · 题解

感觉挺有意思的题，写了 2h 多然后没脑子写 C 光荣掉分。

首先这题操作全是位运算所以位之间独立，从而，对于两个不同的位而言，如果他们的初始状态相同，经过的操作也相同，那么结果相同。

也就是说，虽然输入的 a,\,b,\,c,\,d,\,m 有 30 位，但是由于初始状态只和 a,\,b,\,m 有关，一个位的初始状态一共只有 2^3=8 种不同情况。

如果两位对应的 a,\,b,\,m 都相同而 c,\,d 不同，显然无解。

否则，我们可以把 a,\,b,\,m 相同的位全都当成同一位来看，这样 a,\,b,\,c,\,d,\,m 最多只有 8 位了，总状态数就是 (2^8)^2=2^{16}。

也就是对于一位的每一种初始状态 (a=0/1,b=0/1,m=0/1)，我们要求达到一个目标状态 (c=0/1,d=0/1)，或者没有要求。

预处理：跑一遍初始状态为 x=a=(00001111)_2,\,y=b=(00110011)_2,\,m=(01010101)_2 的广搜，也就是 8 位对应的 a,\,b,\,m 分别为 000,001,010,011,100,101,110,111。从 (a,b) 到 (c,d) 的最短路就是对于以上 8 种不同的初始状态，目标状态为 (c,d) 的最少操作次数。

对于每一组输入，对于以上每种初始状态，我们都可以处理出一个限制 (c=0/1,d=0/1)（当然也可能没有限制），把这些限制按预处理的格式拼成一个状态然后查最短路即可。

注意预处理一下没有限制的情况。可以把这个也当成一种目标状态，总状态数就是 (4+1)^8<4\times10^5。

时间复杂度：16\times(4+1)^8+30T。

#include<bits/stdc++.h>
using namespace std;
int dis[100005];
int from[100005],op[100005];
int f1(int x){
    //f1和f2反了 
    x|=(x&(1<<1))>>1;
    x|=(x&(1<<3))>>1;
    x|=(x&(1<<5))>>1;
    x|=(x&(1<<7))>>1;
    x|=(x&(1<<9))>>1;
    x|=(x&(1<<11))>>1;
    x|=(x&(1<<13))>>1;
    x|=(x&(1<<15))>>1;
    return x;
}
int f2(int x){
    x&=((1<<16)-1)^((x&(1<<1))>>1)^(1<<0);
    x&=((1<<16)-1)^((x&(1<<3))>>1)^(1<<2);
    x&=((1<<16)-1)^((x&(1<<5))>>1)^(1<<4);
    x&=((1<<16)-1)^((x&(1<<7))>>1)^(1<<6);
    x&=((1<<16)-1)^((x&(1<<9))>>1)^(1<<8);
    x&=((1<<16)-1)^((x&(1<<11))>>1)^(1<<10);
    x&=((1<<16)-1)^((x&(1<<13))>>1)^(1<<12);
    x&=((1<<16)-1)^((x&(1<<15))>>1)^(1<<14);
    return x;
}
int f3(int x){
    x^=(x&(1<<0))<<1;
    x^=(x&(1<<2))<<1;
    x^=(x&(1<<4))<<1;
    x^=(x&(1<<6))<<1;
    x^=(x&(1<<8))<<1;
    x^=(x&(1<<10))<<1;
    x^=(x&(1<<12))<<1;
    x^=(x&(1<<14))<<1;
    return x;
}
int f4(int x){
    x^=(1<<9);
    x^=(1<<11);
    x^=(1<<13);
    x^=(1<<15); 
    return x;
}
queue<int>q;
int tmp[15];
int ans[1000005];
int p5[10];
void output(int x){
    for(int i=0;i<16;i++)printf("%d",(x>>i)&1);printf("\n");
}
int main(){
    int T;
    p5[0]=1;
    for(int i=1;i<=8;i++)p5[i]=p5[i-1]*5;
    scanf("%d",&T);
    memset(dis,0x3f,sizeof(dis));
    int S=0b1110010011100100;//初始状态 
    dis[S]=0;
    q.push(S);
    //bfs
    while(!q.empty()){
        int f=q.front();
        q.pop();
        int p1=f1(f),p2=f2(f),p3=f3(f),p4=f4(f);
        if(dis[p1]>dis[f]+1){
            dis[p1]=dis[f]+1;
            q.push(p1);
            from[p1]=f;
            op[p1]=1;
        }
        if(dis[p2]>dis[f]+1){
            dis[p2]=dis[f]+1;
            q.push(p2);
            from[p2]=f;
            op[p2]=2;
        }
        if(dis[p3]>dis[f]+1){
            dis[p3]=dis[f]+1;
            q.push(p3);
            from[p3]=f;
            op[p3]=3;
        }
        if(dis[p4]>dis[f]+1){
            dis[p4]=dis[f]+1;
            q.push(p4);
            from[p4]=f;
            op[p4]=4;
        }
    }
    memset(ans,0x3f,sizeof(ans));
    for(int i=0;i<(1<<16);i++){
        for(int j=0;j<8;j++)tmp[j]=i/((1<<j)<<j)%4;
        int x=0;
        for(int j=0;j<8;j++)x+=tmp[j]*p5[j];
        ans[x]=dis[i];
    }
    //处理没有限制的情况 
    for(int i=0;i<p5[8];i++){
        int pos=-1;
        for(int j=0;j<8;j++)if(i/p5[j]%5==4)pos=j;
        if(pos==-1)continue;
        for(int j=1;j<=4;j++)ans[i]=min(ans[i],ans[i-p5[pos]*j]);
    }
    while(T--){
        int a,b,c,d,m;
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&m);
        for(int i=0;i<8;i++)tmp[i]=4;
        int fl=0;
        for(int i=0;i<30;i++){
            //对应初始状态和目标状态 
            int da=((a>>i)&1);
            int db=((b>>i)&1);
            int dc=((c>>i)&1);
            int dd=((d>>i)&1);
            int dm=((m>>i)&1);
            int id=(dm<<2)+(db<<1)+da;
            int val=(dd<<1)+dc;
            if(tmp[id]!=4 && tmp[id]!=val)fl=1;
            tmp[id]=val;
        }
        if(fl==1){
            printf("-1\n");
            continue;
        }
        int x=0;
        for(int j=0;j<8;j++)x+=tmp[j]*p5[j];
        if(ans[x]==0x3f3f3f3f)printf("-1\n");
        else printf("%d\n",ans[x]);
    }
    return 0;
}