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.
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