AGC031 C - Differ by 1 Bit

タイトルリンク
ブログ参照

aとbのバイナリが異なるビット数が奇数の場合に解がある

隣接する2つの数のバイナリは1ビットのみ異なり、aとbのバイナリは奇数ビットが

異なることが分かる.

aとbのバイナリが奇数ビットで異なる場合、異なるビットxを選択し、このビットを除いて偶数ビットが異なり、a'とb'になり、a'をmidに変更し、a'とmid、midとb'に奇数ビットが異なる.再帰構造(a',mid),(mid,b')は,x番目を補完し,前半シーケンスのx番目はaと同じ,後半はbと同じである.

#include "bits/stdc++.h"

using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 100;
const int inf = 0x3f3f3f3f;

const int SZ = 1 << 20;  //  io
struct fastio {
    char inbuf[SZ];
    char outbuf[SZ];
    fastio() {
        setvbuf(stdin, inbuf, _IOFBF, SZ);
        setvbuf(stdout, outbuf, _IOFBF, SZ);
    }
} io;

void read(int &x) {
    x = 0;
    char ch, c = getchar();
    while (c < '0' || c > '9') ch = c, c = getchar();
    while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    if (ch == '-') x = -x;
}

int vis[30];

int n;
void dfs(int k, int a, int b) {
    if (k == 1) {
        printf("%d %d ", a, b);
        return;
    }
    for (int i = 0; i < n; i++) {
        if (((a >> i) & 1) ^ ((b >> i) & 1)) {
            vis[i] = 1;
            int mid = a;
            for (int j = 0; j < n; j++) {
                if (!vis[j]) {
                    mid = mid ^ (1 << j);
                    break;
                }
            }
            dfs(k - 1, a, mid);
            dfs(k - 1, mid ^ (1 << i), b);
            vis[i] = 0;
            break;
        }
    }

}

int main() {
    //freopen("in.txt", "r", stdin);
    int a, b;
    cin >> n >> a >> b;
    if (__builtin_popcount(a ^ b) % 2 == 0) {
        printf("NO
");
    } else {
        printf("YES
");
        dfs(n, a, b);
    }
    return 0;
}

転載先:https://www.cnblogs.com/albert-biu/p/10987033.html