USACO-Section 2.1 Hamming Codes (DFS)
N, B와 D를 제시한다. N개의 인코딩(1<=N<=64)을 찾아내고 각 인코딩에는 B비트[이진법](1<=B<=8)이 있어 두 인코딩 사이에 적어도 D단위의'해명거리'(1<=D<=7)가 있다.'해명거리'는 두 개의 인코딩에 대해 그들의 이진 표현법에서 서로 다른 이진 위치의 수를 가리킨다.다음 두 인코딩 0x554와 0x234의 차이점을 보십시오(0x554는 각각 5, 5, 4).
0x554 = 0101 0101 0100
0x234 = 0010 0011 0100
xxx xx
다섯 자리가 다르기 때문에'해명거리'는 5다.
서식
PROGRAM NAME: hamming
INPUT FORMAT:
(file hamming.in)
한 줄, N, B, D 포함.
OUTPUT FORMAT:
(file hamming.out)
N개의 인코딩 (10진법으로 표시), 정렬하려면 열 개의 한 줄을 표시해야 한다.만약 여러 해가 있다면, 프로그램은 이러한 해를 출력해야 한다. 만약 그것을 2진수로 바꾸면, 그 값은 가장 작다.
SAMPLE INPUT
16 7 3
SAMPLE OUTPUT
0 7 25 30 42 45 51 52 75 76
82 85 97 102 120 127
0은 가장 작은 수이기 때문에 0은 반드시 있어야 한다. 그리고 DFS 검색을 하면 된다. 작은 것부터 큰 것까지 일일이 열거하기 때문에 첫 번째로 찾은 것이 바로 제목이 구한 답이다.
/*
ID: your_id_here
PROG: hamming
LANG: C++
*/
#include <cstdio>
#include <cstring>
using namespace std;
int n,b,d,ans[65],num,ready[255],rn,t,tt,tmp,mx;
bool isLegal(int x,int y) {
x^=y,tmp=0;
for(t=0;t<b;++t)
if(x&(1<<t))
++tmp;
return tmp>=d;
}
inline bool choose(int index) {
for(tt=1;tt<num;++tt)// , , ,
if(!isLegal(ans[tt],ready[index]))
return false;
return true;
}
bool dfs(int index) {
if(num==n)//
return true;
do {
while(index<rn&&!choose(index))
++index;
if(index==rn) {// , -1
--num;
return false;
}
ans[num++]=ready[index++];
if(dfs(index))
return true;
}while(index<rn);
--num;// , -1
return false;
}
int main() {
int i;
freopen("hamming.in","r",stdin);
freopen("hamming.out","w",stdout);
while(3==scanf("%d%d%d",&n,&b,&d)) {
ans[0]=rn=0,num=1,mx=1<<b;
for(i=1;i<mx;++i)
if(isLegal(0,i))
ready[rn++]=i;
dfs(0);
for(--num,i=0;i<=num;++i)
printf("%d%c",ans[i],(i+1)%10==0||i==num?'
':' ');
}
return 0;
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
[USACO] 2021 December - BronzeN\le500,000 O(N \log N) O(N^2) O(N2)이라 포기. O(N) O(N) 풀이다. O(N^2) O(N2) 아닌가? O(N) O(N). O(NT) N \le 100,000 O(NT) O(N) O(...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.