Codeforces gym 102823D. Bits Reverse 题解
题目大意
给两个数，求使得两个数经过若干次操作后相等的最小次数，每次操作可以把一个数的相邻三位翻转。
题解
只考虑把 \(x\) 变成 \(y\)，逐位考虑两个数的每一位，若不相等，设该位置为 \(i\) ，则去依次看 \(x\) 的 \(i+2,i+4,\cdots\) 位，取第一个和 \(y\) 相等的即为最优取法，然后逐一交换（原题目中的操作可以等价看成隔位交换）。
代码
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
|
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <cstring>
#include <iostream>
#include <cassert>
#include <cmath>
using namespace std;
typedef long long ll;
template <typename _Tp>
void read(_Tp &a, char c = 0, int f = 1) {
for(c = getchar(); !isdigit(c); c = getchar()) if(c == '-') f = -1;
for(a = 0; isdigit(c); a = a * 10 + c - '0', c = getchar()); a *= f;
}
template <typename _Tp>
void write(_Tp a) {
if(a < 0) putchar('-'), a = -a;
if(a > 9) write(a / 10); putchar(a % 10 + '0');
}
template <typename _Tp>
void write2(_Tp a) {
for(int i = 0; i < 64; i++) {
ll o = a & (1ll << (63 - i));
write(o ? 1 : 0);
}
}
int main() {
int T, tct = 0;
read(T);
while(T--) {
ll x, y;
int ans = 0;
read(x); read(y);
#ifdef DEBUG
write2(x), putchar('\n');
write2(y), putchar('\n');
#endif
bool suc = 0;
for(int i = 0; i < 63; i++) {
int o1 = (x >> i) & 1, o2 = (y >> i) & 1;
if(o1 == o2) continue;
suc = 0;
int cnt = 0;
for(int j = i + 2; j < 63; j += 2) {
int o3 = (x >> j) & 1;
cnt++;
if(o3 == o1) {
continue;
}
suc = 1;
x ^= (1ll << j);
x ^= (1ll << i);
ans += cnt;
break;
}
if(!suc) {
break;
}
}
#ifdef DEBUG
write2(x), putchar('\n');
write2(y), putchar('\n');
#endif
if(!suc) {
ans = -1;
} else {
assert(x == y);
}
printf("Case "), write(++tct), printf(": "), write(ans), putchar('\n');
}
return 0;
}
|