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<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
#define debug cout << "Row " << i << " = ";  fr(x,1,last) cout << st[x] << " "; cout << endl; 
#define debugB cout << "B "; fr(j,1,n+1) cout << b[j] << " "; cout << endl;
#define debugA fr(i,1,n) {fr(j,1,n) cout << (a[i][j]?' ':'o'); cout << endl;}
using namespace std;

int m,n,x,y,A,B,C,D,st[2020],last,b[2020],h[2020],pos[2020];
char a[2002][2002];

int main()
{
   int i,j,re=0;
   cin >> n >> m >> x >> A >> B >> y >> C >> D;
   while (m--)
   {
      x%=n; y%=n;      
      a[x+1][y+1]=1;
      x=x*A+B; y=y*C+D;
   }
   //debugA;
   fr(i,1,n) a[n+1][i]=a[i][n+1]=1;
   fr(i,1,n)
   {
      last=0;
      fr(j,1,n+1)
      {
         b[j]=b[j-1]+a[i+1][j];
         if (!a[i][j]) h[j]++;
         else h[j]=0;
         if (h[j]>h[st[last]]) 
         {
            st[++last]=j; pos[last]=j;   
         }
         else
         {
           while (last && h[j]<h[st[last]])
           {
              int left=pos[last--];
              //cout << i << " " << left << " " << right << endl;
              if (b[j-1]!=b[left-1]) re++;
           }
           if (h[j]>h[st[last]]) st[++last]=j;
         }
         //debug; cout << re << endl;
      }  
      //cout << re << endl;
   }
   cout << re << endl;
   return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <list>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <functional>
#include <numeric>
#include <utility>
#include <sstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <memory.h>
#include <cassert>
#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 FORD(i, a, b) for(int i = (a); i > (b); i--)
#define REPD(i, a, b) for(int i = (a); i >=(b); i--)
#define SZ(a) (int((a).size()))
#define ALL(a) (a).begin(), (a).end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
const int N = 2020;
using namespace std;
int a[N][N], L[N], R[N], h[N], row[N][N], col[N][N];
int n, m, x0, aa, bb, Y0, cc, dd, xx, yy;

bool isPerfect(int x1, int y1, int x2, int y2) {
    if (x1 && row[x1][y1] == row[x1][y2]) return 0;
    if (y1 && col[x1][y1] == col[x2][y1]) return 0;
    if (x2 < n && row[x2 + 1][y1] == row[x2 + 1][y2]) return 0;
    if (y2 < n && col[x1][y2 + 1] == col[x2][y2 + 1]) return 0;
    return 1;
}

int main() {
    cin >> n >> m >> x0 >> aa >> bb >> Y0 >> cc >> dd;
    xx = x0 % n; yy = Y0 % n; a[xx + 1][yy + 1] = 1;
    FOR(i, 1, m) {
        xx = (xx * aa + bb) % n;
        yy = (yy * cc + dd) % n;
        a[xx + 1][yy + 1] = 1;
    }
    REP(i, 1, n) REP(j, 1, n) {
        row[i][j] = row[i][j - 1] + a[i][j];
        col[i][j] = col[i - 1][j] + a[i][j];
    }
    int ans = 0;
    REP(i, 1, n) {
        REP(j, 1, n) if (!a[i][j]) h[j]++; else h[j] = 0;
        REP(j, 1, n)
        for(L[j] = j - 1; L[j] && 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]) ans += isPerfect(i - h[j], L[j], i, R[j] - 1);
    }
    cout << ans;
    return 0;
}

Code mẫu của RR

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <string>
#include <deque>
#include <complex>

#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++)
#define FORD(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++)
#define ll long long
#define F first
#define S second
#define PB push_back
#define MP make_pair
using namespace std;

const double PI = acos(-1.0);

int N, up[2011][2011], match[2011], sum[2011][2011];
bool a[2011][2011];
vector<int> list[2011];

void init() {
    int m, x0, y0, A, B, C, D;
    cin >> N >> m >> x0 >> A >> B >> y0 >> C >> D;
    x0 %= N; y0 %= N;
    REP(i,m) {
        a[x0+1][y0+1] = true;
        up[x0+1][y0+1] = x0+1;
        x0 = (x0 * A + B) % N;
        y0 = (y0 * C + D) % N;
    }

    FOR(i,1,N)
    FOR(j,1,N)
        if (!a[i][j]) up[i][j] = up[i-1][j];

    FOR(i,1,N)
    FOR(j,1,N)
        sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j];

//    puts("a = ");
//    FOR(i,1,N) {
//        FOR(j,1,N) cout << a[i][j] << ' ';
//        cout << endl;
//    }
//    puts("up = ");
//    FOR(i,1,N) {
//        FOR(j,1,N) cout << up[i][j] << ' ';
//        cout << endl;
//    }
}

pair<int,int> get(int j) {
    int Left, Right;
    if (match[j-1] == -1) Left = j;
    else Left = match[j-1];

    if (match[j+1] == -1) Right = j;
    else Right = match[j+1];

    match[Left] = Right;
    match[Right] = Left;

    return MP(Left, Right);
}

int getSum(int i1, int i2, int j1, int j2) {
    return sum[i2][j2] - sum[i1-1][j2] - sum[i2][j1-1] + sum[i1-1][j1-1];
}

bool check(int i1, int i2, int j1, int j2) {
    if (getSum(i1,i2,j1,j2)) return false;
    if (i1 > 1 && !getSum(i1-1,i2,j1,j2)) return false;
    if (i2 < N && !getSum(i1,i2+1,j1,j2)) return false;
    if (j1 > 1 && !getSum(i1,i2,j1-1,j2)) return false;
    if (j2 < N && !getSum(i1,i2,j1,j2+1)) return false;
//    cout << i1 << ' ' << i2 << ' ' << j1 << ' ' << j2 << endl;
    return true;
}

void solve() {
    int res = 0;
    FOR(i,1,N) {
        FOR(ii,1,i+1) list[ii].clear();
        memset(match, -1, sizeof match);

        FOR(j,1,N) list[up[i][j]+1].PB(j);

        FOR(ii,1,i) {
            REP(x,list[ii].size()) {
                int j = list[ii][x];
                pair<int,int> now = get(j);

                if (check(ii,i,now.F,now.S)) res++;
            }
        }
    }
    cout << res;
}

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    init();
    solve();
    return 0;
}

Code mẫu của hieult

#include <cstdio>
#include <iostream>
//#include <conio.h>

using namespace std;

int a[2010][2010], tongh[2010][2010],tongc[2010][2010],n,m,x0,A,b,y0,c,d;
int cao[2010],so[2010],p[2010],vitri[2010][2010],t,trai,phai;
bool thoaman(int y1,int x1,int y2,int x2){
     return (tongh[y1-1][x1-1]!=tongh[y1-1][x2]) && (tongh[y2+1][x1-1]!=tongh[y2+1][x2])
         && (tongc[x1-1][y1-1]!=tongc[x1-1][y2]) && (tongc[x2+1][y1-1]!=tongc[x2+1][y2]);      
}

int main()
{
    //freopen("PERREC.in","r",stdin);
    memset(tongh,0,sizeof(tongh));
    memset(tongc,0,sizeof(tongc));
    scanf("%d %d %d %d %d %d %d %d",&n,&m,&x0,&A,&b,&y0,&c,&d);
    x0 = x0%n; y0 = y0%n;
    for(int i = 0;i<=n+1;i++)
        for(int j = 0;j<=n+1;j++){
             if(i==0 || i==n+1 || j==0 || j==n+1)
                   a[i][j] = 0;
             else a[i][j] = 1;
        }
    for(int i = 0;i<m;i++){
        a[x0+1][y0+1] = 0;
        x0 = (x0*A+b)%n;
        y0 = (y0*c+d)%n;
    }
    for(int i = 0;i<=n+1;i++)
         for(int j = 1;j<=n+1;j++)
         {
               tongh[i][j] = tongh[i][j-1]+(a[i][j]==0);
               tongc[i][j] = tongc[i][j-1]+(a[j][i]==0);
         }
    memset(cao,0,sizeof(cao));
    memset(vitri,0,sizeof(vitri));
    int kq = 0;
    for(int i = 0;i<=n+1;i++)
    {
            memset(so,0,sizeof(so));
            for(int j = 0;j<=n+1;j++){
                 if(a[i][j]) cao[j]++;
                 else cao[j] = 0;
                 vitri[cao[j]][so[cao[j]]++]=j;
            }
            memset(p,-1,sizeof(p));
            for(int h = n+1;h>0;h--)
                for(int x = 0;x<so[h];x++){
                     t = vitri[h][x];
                     trai = (p[t-1]==-1?t:p[t-1]);
                     phai = (p[t+1]==-1?t:p[t+1]);
                     p[trai] = phai;
                     p[phai] = trai;
                     if(thoaman(i-h+1,trai,i,phai)) kq++;
                }
    }
    printf("%d",kq);
  //  getch();
}