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);
}