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.
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