【学习笔记】CF1874B Jellyfish and Math

出题人的意图：这是一道基础的稍微带一点码量的搜索题，状态数也很好分析嘛！（简单用一下鸽巢原理）

我的想法：这题状态数怎么分析啊，暴搜怎么过不了啊

下次不要犯这种错误了😅

首先，这道题目是可以拆位的。

理由：对于初始相同的$(a,b,m)=(0/1,0/1,0/1)$，经过相同的操作序列后得到的$(c,d)$一定也是相同的。因此，本质不同的询问只有$5^8$种（也可以用鸽巢原理来理解）

剩下的就是大力搜索了。

其实和 CF1103D Professional layer 的优化思路差不多，但是就是没想到😅

#include
#define ll long long
#define pb push_back
#define fi first
#define se second
#define inf 0x3f3f3f3f
#define db double
using namespace std;
int T,a,b,c,d,m;
int fac5[9],bit[8];
int dis[390625];
int get(int x,int y){
    return x/fac5[y]%5;
}
queue<int>Q;
int solve(int s,int op){
    int t(0);
    for(int i=0;i<8;i++){
        int x=get(s,i);
        if(x==4){
            t+=fac5[i]*4;
            continue;
        }int a=!!(x&2),b=!!(x&1),m=i&1;
        if(op==0)a&=b;
        else if(op==1)a|=b;
        else if(op==2)b^=a;
        else b^=m;
        t+=fac5[i]*(a*2+b);
    }return t;
}
void work(int x,int y){
    if(dis[x]>y){
        dis[x]=y;
        Q.push(x);
    }
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    fac5[0]=1;for(int i=1;i<=8;i++)fac5[i]=fac5[i-1]*5;
    memset(dis,0x3f,sizeof dis);
    for(int i=0;i<fac5[8];i++){
        int ok=1;
        for(int j=0;j<8;j++){
            int x=get(i,j);
            int a=!!(j&4),b=!!(j&2),m=j&1;
            int a2=!!(x&2),b2=x&1;
            if(x!=4&&(a!=a2||b!=b2)){
                ok=0;
                break;
            }
        }if(ok){
            dis[i]=0;
            Q.push(i);
        }
    }
    while(Q.size()){
        int u=Q.front();Q.pop();
        for(int i=0;i<4;i++)work(solve(u,i),dis[u]+1);
    }
    cin>>T;
    while(T--){
        cin>>a>>b>>c>>d>>m;int ok=1;
        for(int i=0;i<8;i++)bit[i]=-1;
        for(int i=0;i<30;i++){
            int a2=a>>i&1,b2=b>>i&1,c2=c>>i&1,d2=d>>i&1,m2=m>>i&1;
            int tmp=(a2<<2)+(b2<<1)+m2,tmp2=(c2<<1)+d2;
            if(bit[tmp]==-1)bit[tmp]=tmp2;
            else if(bit[tmp]!=tmp2){
                ok=0;
                break;
            }
        }
        if(ok==0){
            cout<<-1<<"\n";
            continue;
        }
        int tmp=0;
        for(int i=0;i<8;i++){
            if(bit[i]==-1)tmp+=fac5[i]*4;
            else tmp+=fac5[i]*bit[i];
        }cout<<(dis[tmp]==inf?-1:dis[tmp])<<"\n";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84