Editorial for Slikar
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
const fi=''; fo=''; maxn=512; maxc=1000000000; dx:array[1..4] of longint=(-1,-1,0,0); dy:array[1..4] of longint=(-1,0,-1,0); var n,m:longint; a,re:array[1..maxn,1..maxn] of byte; min,b,tr:array[0..9,1..maxn,1..maxn] of longint; p:array[0..9] of longint; d:array[1..4] of byte; dt:array[1..9,1..maxn div 2,1..maxn div 2,1..4] of byte; procedure rf; var i,j:longint; c:char; begin assign(input,fi); reset(input); readln(n); for i:=1 to n do begin for j:=1 to n do begin read(c); if c='0' then begin a[i,j]:=0; b[0,i,j]:=0; end else begin a[i,j]:=1; b[0,i,j]:=1; end; end; readln; end; re:=a; p[0]:=1; for i:=1 to 9 do p[i]:=p[i-1] shl 1; close(input); end; procedure fill2(deg,x,y,val:longint); var i,j:longint; begin for i:=p[deg]*(x-1)+1 to p[deg]*x do for j:=p[deg]*(y-1)+1 to p[deg]*y do re[i,j]:=val; end; procedure fill(deg,x,y:longint); var i,j,p,q:longint; begin p:=tr[deg,x,y] div 10; q:=tr[deg,x,y] mod 10; fill2(deg-1,2*x+dx[p],2*y+dy[p],0); fill2(deg-1,2*x+dx[q],2*y+dy[q],1); if deg=1 then exit; dt[deg,x,y,p]:=1; dt[deg,x,y,q]:=1; for i:=1 to 4 do if dt[deg,x,y,i]=0 then fill(deg-1,2*x+dx[i],2*y+dy[i]); end; procedure pr; var i,j,k,t,r,q,s,u:longint; kt:boolean; begin for i:=1 to 9 do begin t:=n div p[i]; if t=0 then break; for j:=1 to t do for k:=1 to t do begin min[i,j,k]:=maxc; r:=2*j; q:=2*k; b[i,j,k]:=b[i-1,r-1,q-1]+b[i-1,r-1,q]+b[i-1,r,q-1]+b[i-1,r,q]; end; end; m:=i-1; if n=512 then m:=9; for i:=1 to m do begin t:=n div p[i]; for j:=1 to t do for k:=1 to t do begin kt:=false; for r:=1 to 4 do if kt then break else for q:=1 to 4 do if r<>q then begin fillchar(d,sizeof(d),0); d[r]:=1; d[q]:=1; s:=b[i-1,2*j+dx[r],2*k+dy[r]]+p[i-1]*p[i-1]-b[i-1,2*j+dx[q],2*k+dy[q]]; for u:=1 to 4 do if d[u]=0 then s:=s+min[i-1,2*j+dx[u],2*k+dy[u]]; if s<min[i,j,k] then begin min[i,j,k]:=s; kt:=s=0; tr[i,j,k]:=r*10+q; if kt then break; end; end; end; end; fill(m,1,1); end; procedure wf; var i,j:longint; begin assign(output,fo); rewrite(output); writeln(min[m,1,1]); for i:=1 to n do begin for j:=1 to n do write(re[i,j]); writeln; end; close(output); end; begin rf; pr; wf; end.
Code mẫu của ladpro98
{$H+} program slikar; uses math; const maxn=513; maxP = 10; oo=trunc(1e9); fi=''; b = 1;//black; w = 0;//white; r = 2;//recursive; var f:array[1..maxn,1..maxn,0..maxP,0..2] of longint; //F[i,j,k,t] = Chenh lech min cua hinh vuong goc duoi phai la i,j, canh = 2^k, to theo cach t; check:array[1..maxn,1..maxn,0..maxP,0..2] of boolean; trace:array[1..maxn,1..maxn,0..maxP] of longint; res:array[1..maxn,1..maxn] of longint; a:array[1..maxn] of string; pow:array[0..10] of longint; per:array[0..30,0..4] of longint; n,pn,d:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi);reset(inp); readln(inp,n); for i:=1 to n do readln(inp,a[i]); close(inp); pow[0]:=1; for i:=1 to 10 do pow[i]:=2*pow[i-1]; for i:=0 to 10 do if pow[i] = n then pn:=i; end; procedure GenPer; var i,k,j,t:longint; begin for i:=1 to 3 do for j:=i+1 to 4 do for t:=0 to 1 do begin inc(d); per[d,i]:=2;per[d,j]:=2; for k:=1 to 4 do if (k<>i) and (k<>j) then begin per[d,k]:=t; break; end; for k:=4 downto 1 do if (k<>i) and (k<>j) then begin per[d,k]:=1-t; break; end; end; end; function dp(i,j,k,t:longint):longint; var i1,i2,i3,j1,j2,j3,x,temp:longint; begin if check[i,j,k,t] then exit(f[i,j,k,t]); check[i,j,k,t]:=true; if k=0 then begin if (t=2) or (a[i][j] = chr(t+48)) then f[i,j,k,t]:=0 else f[i,j,k,t]:=1; exit(f[i,j,k,t]); end; i1:=(i+i-pow[k]) shr 1; j1:=(j+j-pow[k]) shr 1; i2:=i1;j2:=j; i3:=i; j3:=j1; if (t<2) then f[i,j,k,t]:=dp(i1,j1,k-1,t)+dp(i2,j2,k-1,t)+dp(i3,j3,k-1,t)+dp(i,j,k-1,t) else begin f[i,j,k,t]:=oo; for x:=1 to d do begin temp:= dp(i1,j1,k-1,per[x,1])+dp(i2,j2,k-1,per[x,2])+ dp(i3,j3,k-1,per[x,3])+dp(i,j,k-1,per[x,4]); if f[i,j,k,t]>temp then begin f[i,j,k,t]:=temp; trace[i,j,k]:=x; end; end; end; exit(f[i,j,k,t]); end; procedure print(i,j,k,t:longint); var p,q,i1,i2,i3,j1,j2,j3:longint; begin if (t<2) then begin for p:=i-pow[k]+1 to i do for q:=j-pow[k]+1 to j do res[p,q]:=t; exit; end; if k=0 then begin res[i,j]:=ord(a[i][j])-48; exit; end; i1:=(i+i-pow[k]) shr 1; j1:=(j+j-pow[k]) shr 1; i2:=i1;j2:=j; i3:=i; j3:=j1; print(i1,j1,k-1,per[trace[i,j,k],1]); print(i2,j2,k-1,per[trace[i,j,k],2]); print(i3,j3,k-1,per[trace[i,j,k],3]); print(i,j,k-1,per[trace[i,j,k],4]); end; procedure process; var i,j:longint; begin writeln(dp(n,n,pn,r)); print(n,n,pn,r); for i:=1 to n do begin for j:=1 to n do write(res[i,j]); writeln; end; end; begin input; GenPer; process; end.
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=512; snode=400000; var f1,f2:text; vt0,vt1,vtx,vty,vt,n:longint; // timeold:longint; kq,a:array[1..MAXN,1..MAXN] of longint; color,diff1,diff0,diff,s0,s1:array[1..snode] of longint; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure inp; var i,j:longint; ch:char; begin readln(f1,n); for i:=1 to n do begin for j:=1 to n do begin read(f1,ch); if ch='0' then a[i,j]:=0 else a[i,j]:=1; end; readln(f1); end; end; procedure build(i,u1,u2,v1,v2:longint); var mu,mv:longint; begin if (u1=u2) then begin if a[u1,v1]=0 then begin s0[i]:=1; s1[i]:=0; diff0[i]:=0; diff1[i]:=1; diff[i]:=0; end else //a[u1,v1]=1 begin s0[i]:=0; s1[i]:=1; diff0[i]:=1; diff1[i]:=0; diff[i]:=0; end; exit; end; mu:=(u1+u2)>>1; mv:=(v1+v2)>>1; build(i<<2-2,u1, mu,v1,mv); build(i<<2-1,u1, mu,mv+1,v2); build(i<<2 ,mu+1,u2,v1,mv); build(i<<2+1,mu+1,u2,mv+1,v2); s0[i]:=s0[i<<2-2]+s0[i<<2-1]+s0[i<<2]+s0[i<<2+1]; s1[i]:=s1[i<<2-2]+s1[i<<2-1]+s1[i<<2]+s1[i<<2+1]; diff0[i]:=s1[i]; diff1[i]:=s0[i]; diff[i]:=maxlongint; for vt0:=i<<2-2 to i<<2+1 do for vt1:=i<<2-2 to i<<2+1 do if vt0<>vt1 then begin vtx:=0; vty:=0; for vt:=i<<2-2 to i<<2+1 do if (vt<>vt0) and (vt<>vt1) then if vtx=0 then vtx:=vt else vty:=vt; diff[i]:=min(diff[i],diff0[vt0]+diff1[vt1]+diff[vtx]+diff[vty]); end; end; var i,j:longint; procedure cal(i,u1,u2,v1,v2,k:longint); var mu,mv:longint; begin if k=0 then exit; if k=1 then begin for i:=u1 to u2 do for j:=v1 to v2 do kq[i,j]:=k; exit; end; if u1=u2 then begin kq[u1,v1]:=a[u1,v1]; exit; end; mu:=(u1+u2)>>1; mv:=(v1+v2)>>1; for vt0:=i<<2-2 to i<<2+1 do for vt1:=i<<2-2 to i<<2+1 do if vt0<>vt1 then begin vtx:=0; vty:=0; for vt:=i<<2-2 to i<<2+1 do if (vt<>vt0) and (vt<>vt1) then if vtx=0 then vtx:=vt else vty:=vt; if diff[i]=diff0[vt0]+diff1[vt1]+diff[vtx]+diff[vty] then begin color[vt0]:=0; color[vt1]:=1; color[vtx]:=2; color[vty]:=2; cal(i<<2-2,u1, mu,v1, mv,color[i<<2-2]); cal(i<<2-1,u1, mu,mv+1,v2,color[i<<2-1]); cal(i<<2 ,mu+1,u2,v1, mv,color[i<<2 ]); cal(i<<2+1,mu+1,u2,mv+1,v2,color[i<<2+1]); exit; end; end; end; procedure ans; begin writeln(f2,diff[1]); for i:=1 to n do begin for j:=1 to n do write(f2,kq[i,j]); writeln(f2); end; end; begin // timeold:=getTickCount; openF; inp; build(1,1,n,1,n); cal(1,1,n,1,n,2); ans; closeF; // writeln(getTickCount-timeold); end.
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <ctime> #include <deque> #include <queue> #include <stack> #include <bitset> #include <cctype> #include <cstdio> #include <string> #include <vector> #include <cassert> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> using namespace std; typedef long long ll; typedef long double ld; //typedef double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(__typeof(n) i = 0; i < (n); ++i) #define Repd(i,n) for(__typeof(n) i = (n)-1; i >= 0; --i) #define For(i,a,b) for(__typeof(b) i = (a); i <= (b); ++i) #define Ford(i,a,b) for(__typeof(a) i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) #define nl puts("") #define sp printf(" ") #define ok puts("ok") //#include <conio.h> template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> void db(T a, int p = -1) { if (p >= 0) cout << fixed << setprecision(p); cout << a << " "; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> struct Triple { T x, y, z; Triple() {} Triple(T _x, T _y, T _z) : x(_x), y(_y), z(_z) {} }; template<class T> Triple<T> euclid(T a, T b) { if (b == 0) return Triple<T>(1, 0, a); Triple<T> r = euclid(b, a % b); return Triple<T>(r.y, r.x - a / b * r.y, r.z); } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } const int bfsz = 1 << 16; char bf[bfsz + 5]; int rsz = 0;int ptr = 0; char gc() { if (rsz <= 0) { ptr = 0; rsz = fread(bf, 1, bfsz, stdin); if (rsz <= 0) return EOF; } --rsz; return bf[ptr++]; } void ga(char &c) { c = EOF; while (!isalpha(c)) c = gc(); } int gs(char s[]) { int l = 0; char c = gc(); while (isspace(c)) c = gc(); while (c != EOF && !isspace(c)) { s[l++] = c; c = gc(); } s[l] = '\0'; return l; } template<class T> bool gi(T &v) { v = 0; char c = gc(); while (c != EOF && c != '-' && !isdigit(c)) c = gc(); if (c == EOF) return false; bool neg = c == '-'; if (neg) c = gc(); while (isdigit(c)) { v = v * 10 + c - '0'; c = gc(); } if (neg) v = -v; return true; } const double PI = 2 * acos(0); const string months[] = {"January", "February", "March", "April", "May", "June", "July", "August", "September", "October", "November", "December"}; const int days[] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}; const int dr[] = {-1, +0, +1, +0}; const int dc[] = {+0, +1, +0, -1}; const int inf = (int)1e9 + 5; const ll linf = (ll)1e16 + 5; const ld eps = ld(1e-9); const ll mod = 100000007; typedef pair<int, int> II; #define maxn 515 int n, m; string s[maxn], res[maxn]; int a[maxn][maxn][11], f[maxn][maxn][11], d[maxn][maxn][11][2]; int cal2(int x){ if(x == 1) return 0; return 1 + cal2(x >> 1); } int B(int x){ return 1 << x; } void Boi(int r, int c, int id, int mau){ For(i, r, r + B(id) - 1) For(j, c, c + B(id) - 1) res[i][j] = mau + '0'; } void paint(int r, int c, int id){ if(id == 0){ res[r][c] = s[r][c]; return; } int i = d[r][c][id][0]; int j = d[r][c][id][1]; int t1 = -1, t2; Rep(k, 4) if(k != i && k!= j){ if(t1 == -1) t1 = k; else t2 = k; } Boi(r + (i >> 1) * B(id - 1), c + (i & 1) * B(id - 1), id - 1, 0); Boi(r + (j >> 1) * B(id - 1), c + (j & 1) * B(id - 1), id - 1, 1); paint(r + (t1 >> 1) * B(id - 1), c + (t1 & 1) * B(id - 1), id - 1); paint(r + (t2 >> 1) * B(id - 1), c + (t2 & 1) * B(id - 1), id - 1); } void go(int r, int c, int id){ if(id == 0) {f[r][c][id] = 0; return;} go(r, c, id - 1); go(r, c + B(id - 1), id - 1); go(r + B(id - 1), c, id - 1); go(r + B(id - 1), c + B(id - 1), id - 1); int &res = f[r][c][id]; res = inf; Rep(i, 4) Rep(j, 4) if(i != j){ int t, t1 = -1, t2; Rep(k, 4) if(k != i && k!= j){ if(t1 == -1) t1 = k; else t2 = k; } t = a[r + (i >> 1) * B(id - 1)][c + (i & 1) * B(id - 1)][id - 1] + B(id + id - 2) - a[r + (j >> 1) * B(id - 1)][c + (j & 1) * B(id - 1)][id - 1] + f[r + (t1 >> 1) * B(id - 1)][c + (t1 & 1) * B(id - 1)][id - 1] + f[r + (t2 >> 1) * B(id - 1)][c + (t2 & 1) * B(id - 1)][id - 1]; if(t < res){ res = t; d[r][c][id][0] = i; d[r][c][id][1] = j; } } // if(r == 0 && c == 0 && id == m) cout << res << endl; } int main(){ // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); cin >> n; Rep(i, n) cin >> s[i]; Rep(i, n) Rep(j, n) a[i][j][0] = s[i][j] - '0'; m = cal2(n); Rep(i, n) res[i].resize(n); For(i, 1, m){ For(r, 0, n - (1 << i)) For(c, 0, n - (1 << i)){ a[r][c][i] = a[r][c][i - 1] + a[r + B(i - 1)][c][i - 1] +a[r][c + B(i - 1)][i - 1] + a[r + B(i - 1)][c + B(i - 1)][i - 1]; } } go(0, 0, m); paint(0, 0, m); printf("%d\n", f[0][0][m]); Rep(i, n) cout << res[i] << endl; }
Code mẫu của ll931110
#include <algorithm> #include <bitset> #include <cmath> #include <cstdio> #include <cstdlib> #include <cstring> #include <deque> #include <fstream> #include <iostream> #include <iterator> #include <map> #include <queue> #include <set> #include <sstream> #include <string> #include <vector> typedef long long ll; using namespace std; int mx[4] = {0,0,1,1}; int my[4] = {0,1,0,1}; int n; int a[520][520],b[520][520],fin[520][520]; int f[520][520][11],p0[520][520][11],p1[520][520][11]; int get(int x1,int y1,int x2,int y2) { return b[x2][y2] - b[x1 - 1][y2] - b[x2][y1 - 1] + b[x1 - 1][y1 - 1]; }; int rec(int x,int y,int k) { if (f[x][y][k] != -1) return f[x][y][k]; if (!k) { f[x][y][k] = 0; return 0; }; int best = 1000000000,len = 1 << (k - 1); for (int i = 0; i < 4; i++) for (int j = 0; j < 4; j++) if (i != j) { int tmp = get(x + len * mx[i],y + len * my[i],x - 1 + len * mx[i] + len,y - 1 + len * my[i] + len); //color with 0 tmp += len * len - get(x + len * mx[j],y + len * my[j],x - 1 + len * mx[j] + len,y - 1 + len * my[j] + len); //color with 1 for (int t = 0; t < 4; t++) if (t != i && t != j) tmp += rec(x + len * mx[t],y + len * my[t],k - 1); if (best > tmp) { best = tmp; p0[x][y][k] = i; p1[x][y][k] = j; }; }; f[x][y][k] = best; return best; }; void track(int x,int y,int k) { if (!k) { fin[x][y] = a[x][y]; return; }; int pos = p1[x][y][k],len = 1 << (k - 1); for (int i = x + len * mx[pos]; i < x + len * mx[pos] + len; i++) for (int j = y + len * my[pos]; j < y + len * my[pos] + len; j++) fin[i][j] = 1; for (int t = 0; t < 4; t++) if (t != p0[x][y][k] && t != p1[x][y][k]) track(x + len * mx[t],y + len * my[t],k - 1); }; int main() { // freopen("slikar.in","r",stdin); // freopen("slikar.ou","w",stdout); scanf("%d", &n); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) { char ch; while (1) { scanf("%c", &ch); if (ch == '0' || ch == '1') break; }; a[i][j] = ch - '0'; }; /* for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) cout << a[i][j]; cout << endl; };*/ memset(b,0,sizeof(b)); for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) b[i][j] = a[i][j]; for (int i = 2; i <= n; i++) for (int j = 1; j <= n; j++) b[i][j] += b[i - 1][j]; for (int i = 1; i <= n; i++) for (int j = 2; j <= n; j++) b[i][j] += b[i][j - 1]; memset(f,-1,sizeof(f)); int tmp = n,k = 0; while (tmp > 1) { tmp /= 2; k++; }; int ret = rec(1,1,k); memset(fin,0,sizeof(fin)); track(1,1,k); printf("%d\n", ret); for (int i = 1; i <= n; i++) { for (int j = 1; j <= n; j++) printf("%d", fin[i][j]); printf("\n"); }; };
Code mẫu của khuc_tuan
// {$APPTYPE CONSOLE} {$mode delphi} uses math, sysutils; const dx : array[1..4] of integer = (0,0,1,1); dy : array[1..4] of integer = (0,1,0,1); type Data = class b, w, r : integer; end; var n, i, j : integer; a, b : array[1..555,1..555] of char; procedure fill(sx, sy, len : integer; c : char); var i, j : integer; begin for i:= sx to sx + len - 1 do for j:= sy to sy + len - 1 do b[i,j] := c; end; function color(sx, sy, len : integer) : Data; var res : Data; kq : array[1..4] of Data; cur, best, btr, bde, tr, de, i, j, z : integer; begin res := Data.Create; for i:=sx to sx + len - 1 do for j:=sy to sy + len - 1 do if a[i,j]='0' then inc(res.b) else inc(res.w); if len = 1 then begin b[sx,sy] := a[sx,sy]; // if b[sx,sy] <> a[sx,sy] then inc(res.r); color := res; exit; end; z := len div 2; for i:=1 to 4 do kq[i] := color( sx + dx[i] * z, sy + dy[i] * z, z); best := 1000000000; for tr := 1 to 4 do for de := 1 to 4 do if de <> tr then begin cur := kq[tr].w + kq[de].b; for i := 1 to 4 do if (i<>de) and (i<>tr) then cur := cur + kq[i].r; if cur < best then begin best := cur; btr := tr; bde := de; end; end; fill( sx + dx[btr] * z, sy + dy[btr] * z, z, '0'); fill( sx + dx[bde] * z, sy + dy[bde] * z, z, '1'); res.r := best; color := res; end; begin readln(n); for i:=1 to n do begin for j:=1 to n do read(a[i,j]); readln; end; writeln(color(1, 1, n).r); for i:=1 to n do begin for j:=1 to n do write(b[i,j]); writeln; end; end.
Comments