洛谷 P1461海明码 Hamming Codes
枚举 搜索
1 #include <bits/stdc++.h> 2 using namespace std ; 3 4 const int N = 11 ; 5 int mx,B,n,D ; 6 int bin[N] ; 7 struct base{ 8 bool f[ N ] ; 9 inline void clear() { 10 for(int i=1;i<N;i++) f[ i ] = 0 ; 11 } 12 inline void insert(int x) { 13 int cnt = 0 ; 14 while( x ) { 15 f[ ++cnt ] = x&1 ; 16 x = x>>1 ; 17 } 18 } 19 inline void output() { 20 int ans = 0 ; 21 for(int i=1;i<N;i++) 22 ans+=f[ i ] * bin[ i ] ; 23 printf("%d ",ans) ; 24 } 25 }a[71]; 26 27 inline int diff(base a,base b) 28 { 29 int cnt = 0 ; 30 for(int i=1;i<N;i++) if(a.f[ i ]!=b.f[ i ]) cnt++ ; 31 return cnt ; 32 } 33 34 inline void dfs(int x,int s,int t) 35 { 36 if( x == n+1 ) { 37 for(int i=1;i<=n;i++) { 38 a[ i ].output() ; 39 if(i%10==0) printf(" ") ; 40 } 41 exit(0) ; 42 } 43 bool flag ; 44 base p ; p.clear() ; 45 for(int i=s;i<=t;i++) { 46 flag = false ; 47 p.insert( i ) ; 48 for(int j=1;j<x;j++) 49 if( diff( a[ j ],p )<D ) 50 flag = 1 ; 51 if(flag==false) { 52 a[ x ] = p ; 53 dfs(x+1,i+1,t) ; 54 break ; 55 } 56 } 57 } 58 59 int main() 60 { 61 scanf("%d%d%d",&n,&B,&D) ; 62 bin[ 1 ] = 1 ; 63 for(int i=2;i<N;i++) bin[ i ] = bin[ i-1 ] * 2 ; 64 mx = (1<<B) ; 65 a[ 1 ].insert(0) ; 66 dfs( 2,1,mx ) ; 67 68 return 0 ; 69 }