Editorial for VOI 12 Bài 1 - Khoảng cách Hamming


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

int n,m,k,ans;
char a[1010],b[1010];

int hamming(int x)
{
    int res=0;
    for (int i=0;i<m && res<ans;i++,x++)
    {
        if (x==n) x=0;
        res+=(a[x]!=b[i]);
    }
    return res;
}

int main()
{
    cin >> n >> m >> k;
    ans=m;
    scanf("%s",&a);
    while (k--) 
    {
        scanf("%s",&b);
        for (int i=0;i<n;i++) ans=min(ans,hamming(i));
    }
    cout << ans << endl;
}

Code mẫu của happyboy99x

#include<cstdio>
#include<cstring>

int m, n, k;
char t[1001], s[2001];

int main() {
    scanf("%d%d%d%s", &n, &m, &k, s);
    for(int i = 0; i < n; ++i) s[n+i] = s[i]; s[n+n] = '\0';
    int res = m;
    while(k--) {
        scanf("%s", t);
        for(int i = 0; i < n; ++i) {
            int tmp = 0;
            for(int p1 = i, p2 = 0; p2 < m && tmp < res; tmp += s[p1++] != t[p2++]);
            res = tmp;
        }
    }
    printf("%d\n", res);
    return 0;
}

Code mẫu của ladpro98

program ham12;
uses    math;
const   fi='';
var     inp:text;
        s,c:ansistring;
        n,k,m,res,i:longint;

procedure play;
var     i,j,temp:longint;
begin
        for i:=1 to n do
        begin
                temp:=0;
                for j:=i to i+m-1 do
                if s[j]<>c[j-i+1] then
                begin
                        inc(temp);
                        if temp>=res then break;
                end;
                res:=min(res,temp);
        end;
end;

begin

        assign(inp,fi);
        reset(inp);
        readln(inp,n,m,k);
        readln(inp,s);
        s:=s+s;
        res:=123456789;
        for i:=1 to k do
        begin
                readln(inp,c);
                play;
        end;
        close(inp);
        write(res);
end.

Code mẫu của RR

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <iomanip>
#include <bitset>
#include <complex>

#define FOR(i,a,b) for(int i = a; i <= b; ++i)
#define FORD(i,a,b) for(int i = a; i >= b; --i)
#define REP(i,a) for(int i = 0; i < a; ++i)
#define MP make_pair
#define PB push_back

using namespace std;

char a[1011], b[1011];
int n, m, k;

int main() {
    scanf("%d%d%d\n", &n, &m, &k);
    gets(a);
    int res = 1000111;
    while (k--) {
        gets(b);
        int la = strlen(a), lb = strlen(b), ii, cnt;
        for(int i = 0; i < la; ++i) {
            ii = i; cnt = 0;
            for(int j = 0; j < lb; ++j) {
                if (b[j] != a[ii]) ++cnt;
                ++ii; if (ii == la) ii = 0;
            }
            if (cnt < res) res = cnt;
        }
    }
    printf("%d\n", res);
    return 0;
}

Code mẫu của hieult

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.