题意

给定两个非负整数\(x\)和\(y\)。

规定一种操作，逆序任意三个相邻的二进制位。

问最少需要多少次操作，能使得\(x = y\)。若不能达到，则输出\(-1\)。

数据范围

\(1 \leq T \leq 10000\)
\(0 \leq x, y \leq 10^{18}\)

思路

我们先观察一下这个逆序操作有什么性质，假设三个相邻的二进制位构成一个三元组\((a, b, c)\)，逆序之后变为了\((c, b, a)\)。

可以发现，中间的二进制数不变，两端的数字交换。因此一个很自然的思路就是将\(x\)和\(y\)分别转换成二进制形式，然后奇偶分别考虑。

另一个性质是，任意奇数位之间都可以交换，任意偶数位之间也可以交换。

另外需要考虑的一点是，最后使得\(x = y\)，我们可以假定\(y\)不变，令\(x\)变向\(y\)。因为\(y\)的一次操作对应\(x\)的一次操作。

第一问，能不能达到\(x = y\)，这个可以通过分别计算\(x\)和\(y\)中奇数位\(1\)的个数是否相等，偶数位\(1\)的个数是否相等来判断。

第二问，最少需要多少步，这个需要思考一个贪心策略。以奇数位为例进行思考（偶数位同理），从低位到高位，将\(x\)与\(y\)每一位进行比对。若第\(j\)个奇数位不同，则往高位寻找第一个满足下列条件奇数位\(k\)，有\(x_k = y_j\)，且\(k > j\)，然后交换\(x\)的第\(j\)个奇数位和第\(k\)个奇数位，这需要\(k - j\)步。

这里给出一个简短的证明，假定\(1 \dots j - 1\)个奇数位\(x\)与\(y\)相同，而第\(j\)个奇数位不同，那么我们必然需要从高位找一个奇数位\(k\)来交换到第\(j\)位，假定用\(k'\)时步数最少，需要\(k' - j\)步。而，按照之前的策略，将\(k\)位交换\(j\)位，然后我们可以再将交换后的\(k\)位（即原来的\(j\)位）与\(k'\)位交换，这样总步数也是\(k' - j\)步。这说明我们的策略不差于最优策略。得证！

这种做法的时间复杂度是\(O(34^2T)\)，时间是允许的，但是考虑一个优化。我们可以先预处理出\(x\)和\(y\)的所有奇数位中\(1\)的位置（偶数位同理），计算\(\sum (x_i - y_i)\)，正确性显然。这样时间复杂度是\(O(34T)\)。

代码

• 不加优化版本

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100;

int a[N], b[N];
int cnt1, cnt2;

int main()
{
    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; i ++) {
        ll num1, num2;
        scanf("%lld%lld", &num1, &num2);
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for(int j = 0; j < 100; j ++) {
            a[j] = num1 % 2;
            num1 /= 2;
        }
        for(int j = 0; j < 100; j ++) {
            b[j] = num2 % 2;
            num2 /= 2;
        }
        int ans = 0;
        cnt1 = cnt2 = 0;
        for(int j = 0; j < 100; j += 2) {
            if(a[j]) cnt1 ++;
            if(b[j]) cnt2 ++;
        }
        if(cnt1 != cnt2) {
            printf("Case %d: -1\n", i);
            continue;
        }
        for(int j = 0; j < 100; j += 2) {
            if(a[j] == b[j]) continue;
            for(int k = j + 2; k < 100; k += 2) {
                if(a[k] == b[j]) {
                    swap(a[k], a[j]);
                    ans += (k - j) / 2;
                    break;
                }
            }
        }
        cnt1 = cnt2 = 0;
        for(int j = 1; j < 100; j += 2) {
            if(a[j]) cnt1 ++;
            if(b[j]) cnt2 ++;
        }
        if(cnt1 != cnt2) {
            printf("Case %d: -1\n", i);
            continue;
        }
        for(int j = 1; j < 100; j += 2) {
            if(a[j] == b[j]) continue;
            for(int k = j + 2; k < 100; k += 2) {
                if(a[k] == b[j]) {
                    swap(a[k], a[j]);
                    ans += (k - j) / 2;
                    break;
                }
            }
        }
        printf("Case %d: %d\n", i, ans);
    }
    return 0;
}

• 优化版本

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 100;

int a[N], b[N];
int cnt1, cnt2;
int loc1[N], loc2[N];

int main()
{
    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; i ++) {
        ll num1, num2;
        scanf("%lld%lld", &num1, &num2);
        memset(a, 0, sizeof(a));
        memset(b, 0, sizeof(b));
        for(int j = 0; j < 100; j ++) {
            a[j] = num1 % 2;
            num1 /= 2;
        }
        for(int j = 0; j < 100; j ++) {
            b[j] = num2 % 2;
            num2 /= 2;
        }
        int ans = 0;
        cnt1 = cnt2 = 0;
        for(int j = 0; j < 100; j += 2) {
            if(a[j]) loc1[cnt1] = j, cnt1 ++;
            if(b[j]) loc2[cnt2] = j, cnt2 ++;
        }
        if(cnt1 != cnt2) {
            printf("Case %d: -1\n", i);
            continue;
        }
        for(int j = 0; j < cnt1; j ++) ans += abs(loc1[j] - loc2[j]) / 2;
        cnt1 = cnt2 = 0;
        for(int j = 1; j < 100; j += 2) {
            if(a[j]) loc1[cnt1] = j, cnt1 ++;
            if(b[j]) loc2[cnt2] = j, cnt2 ++;
        }
        if(cnt1 != cnt2) {
            printf("Case %d: -1\n", i);
            continue;
        }
        for(int j = 0; j < cnt1; j ++) ans += abs(loc1[j] - loc2[j]) / 2;
        printf("Case %d: %d\n", i, ans);
    }
    return 0;
}