Hướng dẫn giải của VM 13 Bài 11 - Thế giới năm 1000003
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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 happyboy99x
#include<cstdio> #include<climits> #include<cstring> #include<algorithm> using namespace std; const int N = 4e5; char s[N+1]; int n, f[10][10], pos[10][2], rpos[10][2]; void enter() { scanf("%s", s); n = strlen(s); for(int i = 1; i < n; ++i) { ++f[s[i-1]-0x30][s[i]-0x30]; ++f[s[i]-0x30][s[i-1]-0x30]; } } void backtrack(const int &p, const int &mask, const int &now, int &res) { if(now >= res) return; if(p == 10) { res = now; memcpy(rpos, pos, sizeof pos); } else for(int v = 0; v < 10; ++v) if(~mask & 1 << v) { pos[v][0] = p / 3; pos[v][1] = p % 3; int add = 0; for(int u = 0; u < 10; ++u) if(mask & 1 << u) add += f[u][v] * (abs(pos[u][0] - pos[v][0]) + abs(pos[u][1] - pos[v][1])); backtrack(p+1, mask | 1 << v, now + add, res); } } int main() { enter(); int res = INT_MAX; backtrack(0, 0, 0, res); printf("%d\n", res); for(int i = 0; i < 10; ++i) fprintf(stderr, "%d %d\n", rpos[i][0] + 1, rpos[i][1] + 1); return 0; }
Code mẫu của ladpro98
program vmkey; uses math; const fi=''; lim=10; var s:ansistring; a,px,py:array[0..10] of longint; check:array[0..10] of boolean; //row[0..9,0..9,0..9] of boolean; f:array[0..10,0..10] of longint; res:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,s); close(inp); res:=high(longint); for i:=2 to length(s) do inc(f[min(ord(s[i]),ord(s[i-1]))-48,max(ord(s[i]),ord(s[i-1]))-48]); end; procedure update; var i,j,m,t:longint; begin m:=1; //row[a[1],a[2],a[3]]:=true; for i:=1 to 3 do for j:=1 to 3 do begin px[a[m]]:=i; py[a[m]]:=j; inc(m); end; px[a[m]]:=4;py[a[m]]:=1; t:=0; for i:=0 to 8 do for j:=i+1 to 9 do begin inc(t,f[i,j]*(abs(px[i]-px[j])+abs(py[i]-py[j]))); if t>=res then exit; end; res:=min(res,t); end; procedure back(i:longint); var j:longint; begin if i>lim then begin update; exit; end; for j:=0 to 9 do if not check[j] then begin check[j]:=true; a[i]:=j; back(i+1); check[j]:=false; end; end; begin input; back(1); write(res); end.
Code mẫu của RR
// Author: RR. Expected score: 100 #include <iostream> #include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> #include <vector> #include <sstream> #include <fstream> #define FOR(i,a,b) for(int i=(a),_b=(b); i <= _b; ++i) #define REP(i,a) for(int i=0,_a=(a); i < _a; ++i) using namespace std; char s[500111]; int cnt[11][11]; int a[11], dist[11][11]; int main() { gets(s); REP(i,strlen(s)-1) { cnt[s[i]-'0'][s[i+1]-'0']++; } REP(i,10) REP(j,10) { int u = i / 3, v = i % 3; int x = j / 3, y = j % 3; dist[i][j] = abs(u - x) + abs(v - y); } REP(i,10) a[i] = i; int res = 1000111000; do { int now = 0; REP(i,10) REP(j,10) now += dist[i][j] * cnt[a[i]][a[j]]; res = min(res, now); } while (next_permutation(a, a+10)); cout << res << endl; return 0; }
Code mẫu của skyvn97
#include<cstring> #include<cstdio> #include<queue> using namespace std; typedef pair<int,int> ii; const ii loc[]={ii(0,0),ii(0,1),ii(0,2),ii(1,0),ii(1,1),ii(1,2),ii(2,0),ii(2,1),ii(2,2),ii(3,0)}; const ii inf[]={ii(0,1),ii(0,2),ii(0,3),ii(0,4),ii(0,5),ii(0,6),ii(0,7),ii(0,8),ii(0,9), ii(1,2),ii(1,3),ii(1,4),ii(1,5),ii(1,6),ii(1,7),ii(1,8),ii(1,9), ii(2,3),ii(2,4),ii(2,5),ii(2,6),ii(2,7),ii(2,8),ii(2,9), ii(3,4),ii(3,5),ii(3,6),ii(3,7),ii(3,8),ii(3,9), ii(4,5),ii(4,6),ii(4,7),ii(4,8),ii(4,9), ii(5,6),ii(5,7),ii(5,8),ii(5,9), ii(6,7),ii(6,8),ii(6,9), ii(7,8),ii(7,9), ii(8,9)}; int x[11]; int f[55]; int log2[2222]; char s[400400]; int best,n; int abs(const int &x) { if (x<0) return (-x); else return (x); } int min(const int &x,const int &y) { if (x<y) return (x); else return (y); } int max(const int &x,const int &y) { if (x>y) return (x); else return (y); } int dis(const int &a,const int &b) { return (abs(loc[x[a]].first-loc[x[b]].first)+abs(loc[x[a]].second-loc[x[b]].second)); } int add(const ii &a) { if (a.first==0) return (a.second-1); if (a.first==1) return (a.second+7); if (a.first==2) return (a.second+14); if (a.first==3) return (a.second+20); if (a.first==4) return (a.second+25); if (a.first==5) return (a.second+29); if (a.first==6) return (a.second+32); if (a.first==7) return (a.second+34); if (a.first==8) return (a.second+35); } void init(void) { int i; scanf("%s",s); n=strlen(s); for (i=0;i<45;i=i+1) f[i]=0; for (i=0;i<n-1;i=i+1) if (s[i]!=s[i+1]) f[add(ii(min(s[i],s[i+1])-48,max(s[i],s[i+1])-48))]++; for (i=0;i<11;i=i+1) log2[1<<i]=i; best=(int)1e9; } void update(void) { int i; int sum=0; for (i=0;i<45;i=i+1) { sum=sum+dis(inf[i].first,inf[i].second)*f[i]; if (sum>=best) return; } if (sum<best) best=sum; } void backtrack(const int &i,const int &s) { int ts=(1<<10)-1-s; while (ts>0) { x[log2[ts&(-ts)]]=i; if (i==9) update(); else backtrack(i+1,s|(ts&(-ts))); ts=ts-(ts&(-ts)); } } void process(void) { backtrack(0,0); printf("%d",best); } int main(void) { init(); process(); return 0; }
Bình luận