HAM12 - VOI 2012 Khoảng cách Hamming

Tác giả: hieult

Ngôn ngữ: C++

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 0.00001
#define maxn 1030
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
#define fi first
#define se second
//#define g 9.81
double const PI=4*atan(1.0);

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

int n,m,k,x,r[11],f[1<<8][1<<8] = {0}, M[333], kq = oo;
string s;
int a[maxn][255] = {0}, b[255], lech;

int main(){
   // freopen("input.in","r",stdin);
   // freopen("output.out","w",stdout);
    for(int i = 0 ; i < (1<<8); i++){
        for(int j = 0; j < (1<<8); j++){
            x = i ^ j;
            for(int k = 0; k < 8; k++){
                r[k] = (x&1);
                x /= 2;
            }
            for(int k = 0; k < 4; k++){
                if(r[k*2] || r[k*2 + 1]) f[i][j]++;
            }
        }
    }
    
    M['A'] = 0; M['T'] = 1; M['G'] = 2; M['X'] = 3;
    
    scanf("%d %d %d",&n,&m,&k);
    cin >> s;
    for(int i = 0; i < m; i++){
        s.push_back(s[i]);
    }
    
    
    int r = m/4 ;
    if( m%4 != 0) r++;
    int c = (m - 1)%4 + 1;
    
    for(int i = 0; i < n; i++){
        for(int j = 0; j < r - 1; j++){
            for(int k = i + j*4; k < i + j*4 + 4; k++){
                a[i][j] = a[i][j] * 4 + M[s[k]];
               // printf("%d %d\n",i,j,a[i][j]);
            }
        }
        for(int k = i + (r - 1) * 4; k < i + (r - 1) * 4 + c; k++){
            a[i][r-1] = a[i][r-1] * 4 + M[s[k]];
          //  printf("%d %d %d\n",i,r-1,a[i][r-1]);
        }
    }
    
    for(int ik = 0; ik < k; ik++){
        cin >> s;
        memset(b,0,sizeof(b));
        for(int j = 0; j < r - 1; j++){
            for(int k = j*4; k < j*4 + 4; k++){
                b[j] = b[j] * 4 + M[s[k]];
            }          
        }
        for(int k = (r - 1) * 4; k < (r - 1) * 4 + c; k++){
            b[r-1] = b[r-1] * 4 + M[s[k]];
        }
        for(int i = 0; i < n; i++){
            lech = 0;
            for(int j = 0; j < r; j++)
                lech += f[a[i][j]][b[j]];
            kq = min(kq,lech);
            //printf("%d %d %d\n",ik,i,kq);
        }
    }
    printf("%d",kq);
}

Download