CodeForces - 1874B Jellyfish and Math

Posted on | In ,

题意

给定5个数字a, b, c, d, m, 通过对a,b进行以下4种操作，问最少几步能够将(a, b) 转化为(c, d)

  • x = x & y
  • x = x | y
  • y = x ^ y
  • y = y ^ m

思路

对于这种位操作求最短路径的题，一个比较通用的方法是bfs。一个最naive的方法就是看我们可以以(a, b)这个二元组出发，每次尝试题目中给出的4组操作，看最终到达(c, d, m)这个三元组需要几步。考虑到数据范围是a, b, c, d, m属于$2^{30}$，总样例数$10^{5}$，我们非常有可能得到TLE。但是即便如此，bfs的方向也是对的，唯一的问题是怎么解决状态数过大的问题。

如果在解题过程中碰到这种状态非常大的题，我们可以考虑是否能够压缩bfs的“状态”。比如对于这题来说$2^{30}$就是一个小提示，因为一般来说题目给的都是10进制的范围，给2进制通常就是提示按位考虑。我们以一位的情况来考虑，令ai, bi, mi为2进制下其第i位的可以发现(ai, bi, mi)一共只有(0|1, 0|1, 0|1) 8种情况。更进一步，我们可以发现：

对于i != j， 若(ai, bi, mi) = (aj, bj, mj)， 那么一定有(ci, di) = (cj, dj)。否则不可能转换成功。根据给出的4种操作进行验证，显然这个推论是正确的。即任意二进制位(ai, bi, mi)出现在(a, b, m)中，即便位置不同，只要这个三元组相同，不论如何操作，最后答案得到的二进制位(ci, di)也一定相同。

这个观察给我们的启发是，尽管数字非常大，但只要(ai, bi, mi)这个三元组相同，那么我们可以将其归为一类进行bfs（显然(ai, bi, mi)一共就8个状态，状态数大大减少了）。我们只要从(ai, bi, mi)出发，看怎么走到(ci, di)就行。这个状态数非常小因为答案的(ci, di)一共就4种状态(0|1, 0|1)，深度非常浅所以问题不大。这里过大状态数的问题基本就解决了。

但我们会发现产生了一个新问题，即三元组的所有情况都应该覆盖到。单单对一个二进制bfs是得不到正确答案的。所以最终状态应该覆盖了所有三元组的八种情况类似(000当前(c, d), 001当前(c, d), 010当前(c, d),…)（总长度为8，有一点状态压缩dp的意思了）。(c, d)这个二元组一共有4种情况(0|1, 0|1)。这里要注意，对于不同的a, b来说，有些三元组是不一定存在的。比如a = 111, b = 111, m = 111。这个例子里三元组只有(a=1, b=1, m=1)，其他的三元组情况都没覆盖到。所以最终答案(ci, di)除了基本的4种情况外，还要加一个(a, b, m)三元组不存在的状态，即(4+1) = 5种状态。考虑到之前总长度为8的元组，同时每个位有5个状态，很容易想到用8位5进制数来表达之前的8长度元组。总状态数为$5^{8}=390625$。完美符合时间要求。我们要做的就是按着状态跑一遍bfs就可以了。在实现过程中注意不存在的状态通过常规的二进制操作是更新不到的，但是不存在也代表着，其他位一样就可以了，这位什么状态无所谓。所以遍历一下其他位一样，这一位不一样的状态即可。具体见代码。

代码

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
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const ll MAX_STATE = 400005;
ll p5[10];
ll dp[MAX_STATE]; // 5^8

ll getMask(ll a, ll b, ll m) {
    return (a<<2) | (b<<1) | m;
}
ll getTargetMask(ll c, ll d) {
    return (c<<1) | d;
}
ll getNextState(ll mask, ll op) {
    int ret = 0;
    for(int a = 0; a <= 1; a++) {
        for(int b = 0; b <= 1; b++) {
            for(int m = 0; m <= 1; m++) {
                ll subMask = mask / p5[getMask(a, b, m)] % 5;
                ll c = (subMask >> 1);
                ll d = (subMask & 1);
                if ( op == 0 ) {
                    c = (c & d);
                } else if ( op == 1 ) {
                    c = (c | d);
                } else if(op == 2) {
                    d = (c^d);
                } else {
                    d = (d^m);
                }
                ret += p5[getMask(a, b, m)] * getTargetMask(c, d);
            }
        }
    }
    return ret;
}

void init() {
    for(ll i = 0; i < MAX_STATE; i++) {
        dp[i] = 1e12;
    }
    p5[0] = 1;
    for(int i = 1; i < 10; i++) {
        p5[i] = p5[i-1] * 5LL;
    }
    ll mask = 0;
    for(int a = 0; a <= 1; a++) {
        for(int b = 0; b <= 1; b++) {
            for(int m = 0; m <= 1; m++) {
                mask += p5[getMask(a, b, m)] * getTargetMask(a, b);
            }
        }
    }
    dp[mask] = 0;
    queue<ll> q;
    q.push(mask);
    while(!q.empty()) {
        ll cur = q.front();
        q.pop();
        for(int op = 0; op < 4; op++) {
            ll nxt = getNextState(cur, op);
            if (dp[nxt] == 1e12) {
                dp[nxt] = dp[cur] + 1;
                q.push(nxt);
            }
        }
    }
    for(int tmask = 0; tmask < p5[8]; tmask++) {
        for(int i = 0; i < 8; i++) {
            ll subMask = (tmask / p5[i])%5;
            if (subMask == 4) {
                for(int x = 1; x <= 4; x++) {
                    dp[tmask] = min(dp[tmask], dp[tmask - x * p5[i]]); //这行是更新不存在状态的核心
                }
            }
        }
    }
}

void solve() {
    ll a, b, c, d, m;
    cin>>a>>b>>c>>d>>m;
    ll mask = p5[8]-1;

    for(int i = 0; i < 30; i++) {
        ll abit = ((a>>i)&1), bbit = ((b>>i)&1), cbit = ((c>>i)&1), dbit = ((d>>i)&1), mbit = ((m>>i)&1);
        ll subMask = (mask / p5[getMask(abit, bbit, mbit)]) % 5;
        if (subMask == 4) {
            mask = mask - 4 * p5[getMask(abit, bbit, mbit)] + p5[getMask(abit, bbit, mbit)] * getTargetMask(cbit, dbit);
        } else if (subMask != getTargetMask(cbit, dbit)) {
            cout<<-1<<endl;
            return;
        }
    }
    cout<<((dp[mask] < 1e12) ? dp[mask] : -1)<<endl;
}

int main(){
#ifndef ONLINE_JUDGE
    freopen("./input.txt","r",stdin);
    freopen("./output.txt","w",stdout);
#endif // ONLINE_JUDGE
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    init();
    int T;
    cin>>T;
    while(T--) {
        solve();
    }
    return 0;
}