Editorial for Đếm các hình chữ nhật
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 ladpro98
#include <cstdio> #include <iostream> #include <cstring> #define FOR(i, a, b) for(int i = (a); i < (b); ++i) #define REP(i, a, b) for(int i = (a); i <=(b); ++i) #define REPD(i, a, b) for(int i = (a); i >= (b); --i) #define RESET(a, v) memset(a, (v), sizeof(a)) #define long long long const int N = 404; using namespace std; int a[N][N]; char s[N]; int n, m; int h[N], L[N], R[N]; long memo[5][5][5]; long cal(int c1, int c2, int c3) { long &ret = memo[c1][c2][c3]; if (ret >= 0) return ret; ret = 0; REP(j, 1, n) h[j] = 0; REP(i, 1, m) { REP(j, 1, n) if (a[i][j] == c1 || a[i][j] == c2 || a[i][j] == c3) ++h[j]; else h[j] = 0; REP(j, 1, n) for(L[j] = j - 1; L[j] > 0 && h[L[j]] >= h[j]; L[j] = L[L[j]]); REPD(j, n, 1) for(R[j] = j + 1; R[j] <= n && h[R[j]] > h[j]; R[j] = R[R[j]]); REP(j, 1, n) if (h[j]) ret += (long)(j - L[j]) * (R[j] - j) * h[j]; } return ret; } int main() { #ifdef _LAD_ freopen("CRECT.inp", "r", stdin); #endif // _LAD_ scanf("%d %d\n", &m, &n); REP(i, 1, m) { scanf("%s\n", s + 1); REP(j, 1, n) a[i][j] = s[j] - 'A'; } RESET(memo, -1); long ans = 0; FOR(i, 0, 5) FOR(j, 0, i) FOR(k, 0, j) { ans += cal(i, i, i) + cal(j, j, j) + cal(k, k, k) - cal(i, j, j) - cal(i, k, k) - cal(j, k, k) + cal(i, j, k); } cout << ans << endl; return 0; }
Code mẫu của RR
//Wishing myself a happy lunar new year with a lot of accept solutions //Written by Nguyen Thanh Trung {$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=411; var f1,f2:text; a:array[0..MAXN,1..MAXN] of char; h,stack,l,r:array[0..MAXN] of longint; count:array['A'..'E','A'..'E','A'..'E'] of int64; ok:array[0..MAXN] of boolean; d:array['A'..'E'] of longint; m,n,kq:longint; procedure openF; inline; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; inline; begin close(f1); close(f2); end; procedure inp; inline; var i,j:longint; begin readln(f1,m,n); for i:=1 to m do begin for j:=1 to n do read(f1,a[i,j]); readln(f1); end; end; procedure left; inline; var i,top:longint; begin top:=0; stack[0]:=0; for i:=1 to n do begin while (top>0) and (h[i]<=h[stack[top]]) do dec(top); l[i]:=stack[top]+1; inc(top); stack[top]:=i; end; end; procedure right; inline; var i,top:longint; begin top:=0; stack[0]:=n+1; for i:=n downto 1 do begin while (top>0) and (h[i]<=h[stack[top]]) do dec(top); r[i]:=stack[top]-1; inc(top); stack[top]:=i; end; end; procedure refine; inline; var i,top:longint; begin top:=0; stack[0]:=0; for i:=1 to n do begin while (top>0) and (h[i]<h[stack[top]]) do dec(top); if h[i]=h[stack[top]] then ok[i]:=false; inc(top); stack[top]:=i; end; end; procedure done(var kq:int64); inline; var i,j,k,u,v:longint; begin kq:=0; fillchar(h,sizeof(h),0); for i:=1 to m do begin for j:=1 to n do if d[a[i,j]]=1 then inc(h[j]) else h[j]:=0; fillchar(ok,sizeof(ok),true); left; right; refine; for j:=1 to n do begin if not ok[j] then continue; u:=l[j]; v:=r[j]; k:=max(h[u-1],h[v+1]); inc(kq,(v-u+1)*(v-u+2)*(h[j]-k) div 2); end; end; end; function cal(c1,c2,c3:char):int64; inline; var kq:int64; begin fillchar(d,sizeof(d),0); d[c1]:=1; d[c2]:=1; d[c3]:=1; done(kq); cal:=kq; end; procedure solve; var kq:int64; ch1,ch2,ch3:char; begin kq:=0; for ch1:='A' to 'E' do for ch2:='A' to 'E' do if ch2>=ch1 then for ch3:='A' to 'E' do if ((ch1=ch2) and (ch3>=ch2)) or ((ch2>ch1) and (ch3>ch2)) then count[ch1,ch2,ch3]:=cal(ch1,ch2,ch3); for ch1:='A' to 'E' do for ch2:='A' to 'E' do if ch2>ch1 then for ch3:='A' to 'E' do if ch3>ch2 then kq:=kq+count[ch1,ch2,ch3] -count[ch1,ch1,ch2]-count[ch1,ch1,ch3]-count[ch2,ch2,ch3] +count[ch1,ch1,ch1]+count[ch2,ch2,ch2]+count[ch3,ch3,ch3]; writeln(f2,kq); end; begin openF; inp; solve; closeF; end.
Code mẫu của ll931110
program CRECT; const input = ''; output = ''; maxn = 400; k: array[1..5] of char = ('A','B','C','D','E'); var a: array[1..maxn,1..maxn] of char; stack,h: array[0..maxn] of integer; dp: array[0..maxn] of int64; s: array[0..3] of integer; m,n: integer; res: int64; procedure init; var f: text; i,j: integer; begin assign(f, input); reset(f); readln(f, m, n); for i := 1 to m do begin for j := 1 to n do read(f, a[i,j]); readln(f); end; close(f); end; procedure precalc; begin res := 0; s[0] := 0; stack[0] := 0; dp[0] := 0; end; function calc(x,y,z: integer): int64; var i,j,top,tmp: integer; t: int64; begin fillchar(h, sizeof(h), 0); h[0] := -1; t := 0; for i := 1 to m do begin for j := 1 to n do if ((a[i,j] = k[x]) or (a[i,j] = k[y]) or (a[i,j] = k[z])) then inc(h[j]) else h[j] := 0; top := 0; for j := 1 to n do begin while h[j] <= h[stack[top]] do dec(top); tmp := stack[top]; dp[j] := (j - tmp) * h[j] + dp[tmp]; t := t + dp[j]; inc(top); stack[top] := j; end; end; calc := t; end; procedure update; var t: int64; begin t := calc(s[1],s[2],s[3]); t := t - calc(s[1],s[1],s[2]) - calc(s[2],s[2],s[3]) - calc(s[3],s[3],s[1]); t := t + calc(s[1],s[1],s[1]) + calc(s[2],s[2],s[2]) + calc(s[3],s[3],s[3]); res := res + t; end; procedure attempt(i: integer); var j: integer; begin for j := s[i - 1] + 1 to 5 do begin s[i] := j; if i < 3 then attempt(i + 1) else update; end; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, res); close(f); end; begin init; precalc; attempt(1); printresult; end.
Comments