Editorial for VOI 11 Bài 2 - Hình chữ nhật bốn màu


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 flashmt

#include<iostream>
#include<algorithm>
#define fr(a,b,c) for (a=b;a<=c;a++)
using namespace std;
struct rec
{
  short x,y,z;
};
int n,m,re;
char f[410][410][16];
rec a[100010];

bool cmp(rec i,rec j)
{
    return ((i.x<j.x) || (i.x==j.x && i.y<j.y));
}

int main()
{
    int i,j,t;
    short u;
    cin >> n;
    fr(i,0,n-1) scanf("%hd%hd%hd",&a[i].x,&a[i].y,&a[i].z);
    sort(a,a+n,cmp);
    t=0;
    fr(i,1,n-1)
    {
       if (a[i].x==a[i-1].x)
       {
         fr(j,t,i-1)
         {
            u=(1<<(a[i].z-1))^(1<<(a[j].z-1));
            if (u)
            {
               re+=f[a[j].y+200][a[i].y+200][15-u];
               f[a[j].y+200][a[i].y+200][u]++;
            }
         }
       }
       else t=i;
    }
    cout << re << endl;
    return 0;
}

Code mẫu của happyboy99x

#include<bits/stdc++.h>
using namespace std;

#define TR(v,i) for(__typeof((v).begin())i=(v).begin();i!=(v).end();++i)
const int ABS = 200, N = 1e5;
int color[2*ABS+1][2*ABS+1], val[2*N], nval, n, x[N], y[N], c[N];
long long cnt[16];

void enter() {
    cin >> n;
    for(int i = 0; i < n; ++i) {
        cin >> x[i] >> y[i] >> c[i];
        val[i<<1] = x[i];
        val[(i<<1)+1] = y[i];
        --c[i];
    }
}

int get(int x) {
    return lower_bound(val, val+nval, x) - val;
}

void compress() {
    memset(color, -1, sizeof color);
    sort(val, val+2*n);
    nval = unique(val, val+2*n) - val;
    for(int i = 0; i < n; ++i) {
        x[i] = get(x[i]); y[i] = get(y[i]);
        color[x[i]][y[i]] = c[i];
    }
}

void solve() {
    long long res = 0;
    for(int lower = 0; lower < nval; ++lower)
        for(int upper = lower+1; upper < nval; ++upper) {
            memset(cnt, 0, sizeof cnt);
            for(int i = 0; i < nval; ++i)
                if(color[lower][i] != -1 && color[upper][i] != -1) {
                    int mask = 1 << color[lower][i] | 1 << color[upper][i];
                    res += cnt[15 ^ mask];
                    ++cnt[mask];
                }
        }
    cout << res << '\n';
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    compress();
    solve();
    return 0;
}

Code mẫu của ladpro98

program colorec;
uses    math;
const   maxv=200;
        fi='';
var     a:array[-maxv..maxv,-maxv..maxv] of longint;
        check:array[1..25] of longint;
        n,res:longint;

procedure input;
var     inp:text;
        i,x,y,c:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        begin
                readln(inp,x,y,c);
                a[x,y]:=c;
        end;
        close(inp);
end;

procedure process;
var     i,j,k,t:longint;
begin
        for i:=-maxv to maxv do
        for j:=i+1 to maxv do
        begin
                for k:=1 to 3 do for t:=k+1 to 4 do check[k*t]:=0;
                for k:=-maxv to maxv do
                if (a[i,k]<>a[j,k]) and (a[i,k]*a[j,k]>0) then
                begin
                        inc(res,check[24 div (a[i,k]*a[j,k])]);
                        inc(check[a[i,k]*a[j,k]]);
                end;
        end;
end;

begin
        input;
        process;
        write(res);
end.

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); 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);

//Buffer reading
int INP,AM;
#define BUFSIZE (1<<10)
char BUF[BUFSIZE+1], *inp=BUF;
#define GETCHAR(INP) { \
    if(!*inp) { \
        fread(BUF,1,BUFSIZE,stdin); \
        inp=BUF; \
    } \
    INP=*inp++; \
}
#define DIG(a) (((a)>='0')&&((a)<='9'))
#define GN(j) { \
    AM=0;\
    GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\
    if (INP=='-') {AM=1;GETCHAR(INP);} \
    j=INP-'0'; GETCHAR(INP); \
    while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \
    if (AM) j=-j;\
}
//End of buffer reading

int n;
vector<pair<int,int> > list[444];

void input() {
    GN(n);
    int x, y, c;
    FOR(i,1,n) {
        GN(x); GN(y); GN(c);
        x += 201; c--;
        list[x].PB(MP(y,c));
    }
}

int cnt[20];

#define TWO(x) (1<<(x))

int main() {
//    freopen("input.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
    input();

    FOR(x,0,402) sort(list[x].begin(), list[x].end());

    ll res = 0;
    FOR(x1,0,402)
    FOR(x2,x1+1,402)
    if (list[x1].size() && list[x2].size()) {
        memset(cnt, 0, sizeof cnt);
        int j = 0;

        REP(i,list[x1].size()) {
            while (j+1 < list[x2].size() && list[x2][j].F < list[x1][i].F) j++;
            if (list[x2][j].F == list[x1][i].F)
                cnt[TWO(list[x1][i].S) + TWO(list[x2][j].S)]++;
        }

        FOR(a,0,3)
        FOR(b,a+1,3)
            res += cnt[TWO(a) + TWO(b)] * cnt[15 - TWO(a) - TWO(b)];
    }
    cout << res / 2;
    return 0;
}

Code mẫu của hieult

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

int M[403][403],n,x,y,z,KQ=0;

int main()
{
    //freopen("COLOREC.in","r",stdin);
    scanf("%d",&n);
    for(int i = 0;i<=400;i++)
        for(int j = 0;j<=400;j++)
            M[i][j] = 0;
    for(int i = 1;i<=n;i++)
    {
       scanf("%d %d %d",&x,&y,&z);
       M[x+200][y+200] = z;
    }
    for(int i = 0;i<=400;i++)
        for(int j = i+1;j<=400;j++)
        {
             int a =0 ;int b=0;
             for(int k = 0;k<=400;k++)
             {
                 if((M[i][k]==1 &&M[j][k] == 4) ||(M[i][k]==4 &&M[j][k] == 1))
                     a++;
                 if((M[i][k]==2 &&M[j][k] == 3) ||(M[i][k]==3 &&M[j][k] == 2))
                     b++;
             }
             KQ += a*b;
              a =0 ;b=0;
             for(int k = 0;k<=400;k++)
             {
                 if((M[i][k]==1 &&M[j][k] == 3) ||(M[i][k]==3 &&M[j][k] == 1))
                     a++;
                 if((M[i][k]==2 &&M[j][k] == 4) ||(M[i][k]==4 &&M[j][k] == 2))
                     b++;
             }
             KQ +=a*b;
             a =0 ;b=0;
             for(int k = 0;k<=400;k++)
             {
                 if((M[i][k]==1 &&M[j][k] == 2) ||(M[i][k]==2 &&M[j][k] == 1))
                     a++;
                 if((M[i][k]==4 &&M[j][k] == 3) ||(M[i][k]==3 &&M[j][k] == 4))
                     b++;
             }
             KQ += a*b;
        }
    printf("%d",KQ);
    //getch();
}

Code mẫu của ll931110

#include <algorithm>
#include <bitset>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <fstream>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <utility>
#include <vector>
using namespace std;

int a[402][402];
int f[402][402][16];
int n;

int main()
{
//  freopen("COLOREC.INP","r",stdin);
//  freopen("COLOREC.OUT","w",stdout);
    scanf("%d", &n);
    memset(a,0,sizeof(a));
    for (int i = 0; i < n; i++)
    {
        int x,y,c;  scanf("%d %d %d", &x, &y, &c);
        x += 200;  y += 200;  a[x][y] = c;
    }
    memset(f,0,sizeof(f));
    for (int i = 0; i <= 400; i++)
      for (int j = i + 1; j <= 400; j++)
        for (int k = 0; k <= 400; k++)
          if (a[i][k] && a[j][k] && a[i][k] != a[j][k])
          {
                int mask = (1 << (a[i][k] - 1)) + (1 << (a[j][k] - 1));
                f[i][j][mask]++;
            }

    long long ret = 0;
    for (int i = 0; i <= 400; i++)
      for (int j = i + 1; j <= 400; j++)
        for (int t = 0; t < 16; t++) ret += 1LL * f[i][j][t] * f[i][j][15 - t];
    ret /= 2;
    cout << ret << endl;
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<iostream>
#define MAXC   207
#define FOR(i,a,b) for (int i=(a);i<=(b);i=i+1)
#define REP(i,n) for (int i=0;i<(n);i=i+1)
using namespace std;
typedef long long ll;
int a[MAXC<<1][MAXC<<1];
int maxx,minx,maxy,miny;
void init(void) {
    int n;
    scanf("%d",&n);
    maxx=maxy=-1;
    minx=miny=MAXC<<1;
    memset(a,-1,sizeof a);
    REP(i,n) {
        int x,y,c;
        scanf("%d",&x);
        scanf("%d",&y);
        scanf("%d",&c);
        a[x+MAXC][y+MAXC]=c-1;
        minx=min(minx,x+MAXC);
        maxx=max(maxx,x+MAXC);
        miny=min(miny,y+MAXC);
        maxy=max(maxy,y+MAXC);
    }
}
ll countrec(int t,int b) {
    ll c[20];
    memset(c,0,sizeof c);
    FOR(y,miny,maxy) if (a[t][y]>=0 && a[b][y]>=0)
        c[(1<<a[t][y])|(1<<a[b][y])]++;
    ll ret=0LL;
    REP(i,4) FOR(j,i+1,3) ret+=c[(1<<i)|(1<<j)]*c[15^(1<<i)^(1<<j)];
    return (ret>>1);
}
void process(void) {
    ll res=0;
    FOR(t,minx,maxx) FOR(b,minx,t) res+=countrec(t,b);
    cout << res;
}
int main(void) {
    init();
    process();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.