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.

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

Please read the guidelines before commenting.


There are no comments at the moment.