AcWing 1363. 汉明码 (java)
原题链接
中等
作者:
x_x_5
,
2024-04-19 14:15:32
,
所有人可见
,
阅读 2
import java.util.*;
class Main {
static int n, m, d, M;
static int[] ans;
public static boolean check(int x) {
int c = 0;
while (x > 0) {
x -= x & (-x);
c ++;
}
return c >= d;
}
public static int get(int x, int d) {
for (int i = x; i < M; ++ i) {
boolean flag = true;
for (int j = 0; j < d; ++ j) {
if (!check(i ^ ans[j])) {
flag = false;
break;
}
}
if (flag) return i;
}
return -1;
}
public static boolean dfs(int x, int d) {
if (d == n) return true;
while (true) {
int t = get(x, d);
if (t == -1) break;
ans[d] = t;
if (dfs(t + 1, d + 1)) return true;
}
return false;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
n = sc.nextInt();
m = sc.nextInt();
d = sc.nextInt();
M = 1 << m;
ans = new int[n];
dfs(1, 1);
for (int i = 0; i < n; ++ i) {
if (i > 0 && i % 10 == 0) System.out.println();
System.out.print(ans[i] + " ");
}
}
}