题意
给定两个非负整数(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
", 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
", 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
", 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
", 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
", i);
continue;
}
for(int j = 0; j < cnt1; j ++) ans += abs(loc1[j] - loc2[j]) / 2;
printf("Case %d: %d
", i, ans);
}
return 0;
}