Editorial for Tính toán lượng nước
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> #include<cstdio> #define maxs 10000 #define maxn 110 #define fr(a,b,c) for(a=b;a<=c;a++) #define frr(a,b,c) for(a=b;a>=c;a--) using namespace std; const int dx[]={-1,0,1,0}; int dy[]={0,1,0,-1}; int n,m,a[maxn][maxn],qx[maxs+10],qy[maxs+10],q,d[maxn][maxn]; int p[maxs+10],px[maxs+10],py[maxs+10],l[maxs+10]; long long re; void bfs(int x,int y,int val) { int i,j; d[x][y]=val; qx[1]=x; qy[1]=y; i=q=1; while (i<=q) { x=qx[i]; y=qy[i++]; fr(j,0,3) { int xx=x+dx[j],yy=y+dy[j]; if (!d[xx][yy] && a[xx][yy]<=val) { d[xx][yy]=val; qx[++q]=xx; qy[q]=yy; } } } } int border(int x,int y) { int i; fr(i,0,3) if (d[x+dx[i]][y+dy[i]]) return 1; return 0; } int main() { int i,j,x,y; scanf("%d%d",&m,&n); fr(i,1,m) fr(j,1,n) { scanf("%d",&a[i][j]); p[a[i][j]]++; } fr(i,2,maxs+1) p[i]+=p[i-1]; fr(i,1,m) fr(j,1,n) { px[p[a[i][j]]]=i; py[p[a[i][j]]--]=j; } fr(i,1,m) d[i][0]=d[i][n+1]=-1; fr(i,1,n) d[0][i]=d[m+1][i]=-1; fr(i,1,m*n) { x=px[i]; y=py[i]; if (!d[x][y] && border(x,y)) bfs(x,y,a[x][y]); } fr(i,2,m-1) fr(j,2,n-1) re+=max(0,d[i][j]-a[i][j]); cout << re << endl; return 0; }
Code mẫu của happyboy99x
#include<iostream> #include<algorithm> #include<cstring> #include<queue> using namespace std; const int N = 100, d[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}}, INF = 1e9; int h[N][N], f[N][N], m, n; pair<int, pair<int, int> > a[N*N]; void enter() { cin >> m >> n; for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) cin >> h[i][j], a[i*n+j] = make_pair(h[i][j], make_pair(i, j)); } void solve() { memset(f, -1, sizeof f); sort(a, a+m*n); for(int i = 0; i < m*n; ++i) { int x = a[i].second.first, y = a[i].second.second; queue<pair<int, int> > q; if(x==0 || x==m-1 || y==0 || y==n-1 || f[x-1][y]!=-1 || f[x+1][y]!=-1 || f[x][y-1]!=-1 || f[x][y+1]!=-1) f[x][y] = h[x][y], q.push(make_pair(x, y)); while(!q.empty()) { int x = q.front().first, y = q.front().second; q.pop(); for(int k = 0; k < 4; ++k) { int u = x + d[k][0], v = y + d[k][1]; if(u >= 0 && u < m && v >= 0 && v < n && h[u][v] <= f[x][y] && f[u][v] == -1) f[u][v] = f[x][y], q.push(make_pair(u, v)); } } } } void print() { int res = 0; for(int i = 0; i < m; ++i) for(int j = 0; j < n; ++j) res += f[i][j] - h[i][j]; cout << res << endl; } int main() { ios::sync_with_stdio(false); enter(); solve(); print(); return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> #define ii pair<int, int> #define iii pair<int, ii> #define X first #define Y second const int N = 1010; const int dx[] = {-1, 0, 1, 0}; const int dy[] = {0, 1, 0, -1}; const int oo = 1000000009; using namespace std; int d[N][N], a[N][N]; int m, n; int main() { scanf("%d %d", &m, &n); for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) scanf("%d", &a[i][j]), d[i][j] = oo; priority_queue<iii, vector<iii>, greater<iii> > Q; for(int i = 1; i <= m; i++) { d[i][1] = a[i][1]; d[i][n] = a[i][n]; Q.push(iii(a[i][1], ii(i, 1))); Q.push(iii(a[i][n], ii(i, n))); } for(int i = 2; i < n; i++) { d[1][i] = a[1][i]; d[m][i] = a[m][i]; Q.push(iii(a[1][i], ii(1, i))); Q.push(iii(a[m][i], ii(m, i))); } while (!Q.empty()) { ii u = Q.top().Y; int du = Q.top().X; Q.pop(); if (du != d[u.X][u.Y]) continue; for(int i = 0; i < 4; i++) { ii v (u.X + dx[i], u.Y + dy[i]); if (v.X < 1 || v.Y < 1 || v.X > m || v.Y > n) continue; if (d[v.X][v.Y] > max(d[u.X][u.Y], a[v.X][v.Y])) { d[v.X][v.Y] = max(d[u.X][u.Y], a[v.X][v.Y]); Q.push(iii(d[v.X][v.Y], v)); } } } long long res = 0; for(int i = 1; i <= m; i++) for(int j = 1; j <= n; j++) if (d[i][j] > a[i][j]) res += d[i][j] - a[i][j]; printf("%lld", res); return 0; }
Code mẫu của RR
#include <sstream> #include <iomanip> #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 FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ 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 const long double PI = acos((long double) -1.0); const int MN = 1011; const int MN2 = MN * MN; int id[MN][MN], h[MN][MN], m, n; int lab[MN2], height[MN2]; bool out[MN2]; vector< pair<int,int> > ls[MN2]; int getRoot(int u) { if (lab[u] < 0) return u; return lab[u] = getRoot(lab[u]); } void merge(int u, int v) { lab[u] = lab[u] + lab[v]; lab[v] = u; height[u] = max(height[u], height[v]); out[u] = out[u] | out[v]; } const int di[] = {-1,1,0,0}; const int dj[] = {0,0,-1,1}; int main() { scanf("%d%d", &m, &n); int now = 0; FOR(i,2,m+1) FOR(j,2,n+1) scanf("%d", &h[i][j]); m += 2; n += 2; FOR(i,1,m) FOR(j,1,n) { id[i][j] = ++now; lab[now] = -1; height[now] = h[i][j]; if (h[i][j] == 0) out[now] = true; else out[now] = false; ls[h[i][j]].PB(MP(i,j)); } long long res = 0; FOR(t,1,1000000) REP(tt,ls[t].size()) { int u = ls[t][tt].F, v = ls[t][tt].S, uu, vv; REP(dir,4) { uu = u + di[dir], vv = v + dj[dir]; if (uu < 1 || uu > m || vv < 1 || vv > n) continue; int id2 = getRoot(id[uu][vv]); int id1 = getRoot(id[u][v]); if (height[id1] >= height[id2] && id2 != id1) { if (!out[id2]) { res += -lab[id2] * (height[id1] - height[id2]); } merge(id2, id1); } } } cout << res << endl; return 0; }
Code mẫu của skyvn97
#include<stdio.h> #define MAX 111 int m,n; int a[MAX][MAX]; int c[MAX][MAX]; int hm,s; int dx[4]={0,1,0,-1}; int dy[4]={1,0,-1,0}; void init(void) { int i,j; scanf("%d",&m); scanf("%d",&n); hm=-1; for (i=1;i<=m;i=i+1) for (j=1;j<=n;j=j+1) { scanf("%d",&a[i][j]); if (hm<a[i][j]) hm=a[i][j]; } for (i=0;i<=m+1;i=i+1) { c[i][0]=2; c[i][n+1]=2; } for (i=0;i<=n+1;i=i+1) { c[0][i]=2; c[m+1][i]=2; } s=0; } void dfs(int x,int y) { if (c[x][y]>0) return; int i,j; c[x][y]=1; for (i=0;i<=3;i=i+1) if (c[x+dx[i]][y+dy[i]]==0) dfs(x+dx[i],y+dy[i]); } void process(void) { int i,j,k; for (i=1;i<=hm;i=i+1) { for (j=1;j<=m;j=j+1) for (k=1;k<=n;k=k+1) { if (a[j][k]<i) c[j][k]=0; else c[j][k]=1; } for (j=1;j<=m;j=j+1) { if (c[j][1]==0) dfs(j,1); if (c[j][n]==0) dfs(j,n); } for (j=1;j<=n;j=j+1) { if (c[1][j]==0) dfs(1,j); if (c[m][j]==0) dfs(m,j); } for (j=2;j<m;j=j+1) for (k=2;k<n;k=k+1) if (c[j][k]==0) s=s+1; } printf("%d",s); } int main(void) { init(); process(); }
Code mẫu của khuc_tuan
program rain2; (*****************************************************) const dx:array[1..4] of shortint=(-1,1,0,0); dy:array[1..4] of shortint=(0,0,-1,1); (*****************************************************) type byte = longint ; integer = longint ; ptype2=^_type2; _type2= record i,j:byte; next:ptype2; end; ptype1=^_type1; _type1= record h:integer; list:ptype2; end; arr1=array[1..100,1..100] of integer; arr2=array[1..10000] of _type1; arr3=array[0..101,0..101] of byte; (*****************************************************) var m,n:integer; a:arr1; b:arr3; queue:record a:array[1..30000] of byte; l,r:integer; end; list:^arr2; nl:integer; sum,count:longint; { _t:longint; time:longint absolute 0:$46C;} (*****************************************************) procedure initqueue; begin queue.l:=0; end; (*****************************************************) procedure addQ(i:byte); begin if queue.l=0 then begin queue.l:=1; queue.r:=1; end else if queue.r=30000 then queue.r:=1 else inc(queue.r); queue.a[queue.r]:=i; end; (*****************************************************) function delete:byte; begin delete:=queue.a[queue.l]; if queue.l=queue.r then queue.l:=0 else if queue.l=30000 then queue.l:=1 else inc(queue.l); end; (*****************************************************) function empty:boolean; begin empty:=queue.l=0; end; (*****************************************************) procedure main(var list:arr2); (*****************************************************) procedure init; begin fillchar(a, sizeof(a), 0); fillchar(b, sizeof(b), 0); fillchar( queue, sizeof(queue), 0); nl := 0; sum := 0; count := 0; fillchar(list,sizeof(list),0); end; (*****************************************************) procedure nhap; var i,j:integer; begin readln(m,n); for i:=1 to m do begin for j:=1 to n do read(a[i,j]); readln; end; end; (*****************************************************) procedure add(var l:ptype2;i,j:byte); var p:ptype2; begin new(p); p^.i:=i; p^.j:=j; p^.next:=l; l:=p; end; (*****************************************************) procedure createlist; var i,j:byte; l,r,mid:integer; begin nl:=0; for i:=1 to m do for j:=1 to n do begin if (nl=0) or (list[nl].h<a[i,j]) then begin inc(nl); list[nl].h:=a[i,j]; add(list[nl].list,i,j); continue; end; l:=1; r:=nl; while l<>r do begin mid:=(l+r) div 2; if list[mid].h=a[i,j] then begin l:=mid; r:=mid; break; end; if list[mid].h>a[i,j] then r:=mid else l:=mid+1; end; if list[l].h=a[i,j] then add(list[l].list,i,j) else begin inc(nl); move(list[l],list[l+1],(nl-l)*sizeof(_type1)); list[l].h:=a[i,j]; list[l].list:=nil; add(list[l].list,i,j); end; end; end; (*****************************************************) procedure loang(i,j:byte); var k:byte; begin initqueue; for k:=1 to 4 do if b[i+dx[k],j+dy[k]]=2 then begin addQ(i+dx[k]); addQ(j+dy[k]); dec(count); b[i+dx[k],j+dy[k]]:=0; end; while not empty do begin i:=delete; j:=delete; for k:=1 to 4 do if b[i+dx[k],j+dy[k]]=2 then begin addQ(i+dx[k]); addQ(j+dy[k]); dec(count); b[i+dx[k],j+dy[k]]:=0; end; end; end; (*****************************************************) procedure cat(x:integer); var p:ptype2; i,j,k:byte; begin p:=list[x].list; while p<>nil do begin i:=p^.i; j:=p^.j; for k:=1 to 4 do if b[i+dx[k],j+dy[k]]=0 then b[i,j]:=0; if b[i,j]=0 then loang(i,j) else begin b[i,j]:=2; inc(count); end; p:=p^.next; end; sum:=sum+(list[x+1].h-list[x].h)*count; end; (*****************************************************) procedure xuly; var i,j:integer; begin createlist; for i:=1 to m do for j:=1 to n do b[i,j]:=1; for i:=1 to nl-1 do begin cat(i); end; end; (*****************************************************) procedure ghi; begin writeln( sum); end; (*****************************************************) begin init; nhap; xuly; ghi; end; (*****************************************************) procedure mktest; var i,j:integer; k:integer; begin randomize; m:=100; n:=100; k:=0; writeln(m,' ',n); for i:=1 to m do begin for j:=1 to n do begin inc(k); write(k,' '); end; writeln; end; end; (*****************************************************) var i,t : integer ; begin { mktest; _t:=time;} //readln( t); //for i:=1 to t do // begin new(list); main(list^); dispose(list); // end; { writeln('Thoi gian:',(time-_t)/18.23 :0:4);} end.
Comments