Hướng dẫn giải của VOI 11 Bài 2 - Hình chữ nhật bốn màu
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận