Hướng dẫn giải của Khu vườn hoa
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> #include <cstdio> #include <cstring> #define fr(a,b,c) for (a=b;a<=c;a++) #define frr(a,b,c) for (a=b;a>=c;a--) #define oo 1000000000 using namespace std; int m,n,k,col[255][255],a[255][255],Bot_Right[255][255],Top_Left[255][255]; void calc(int f[255][255],int m,int n) { int i,j,h; fr(i,0,m) fr(j,0,n) f[i][j]=oo; fr(i,1,m) fr(h,0,i-1) { int left=1,sum=0; fr(j,1,n) if (col[i][j]!=col[h][j]) { sum+=col[i][j]-col[h][j]; if (sum<k) continue; while (sum>=k && left<=j) { sum-=(col[i][left]-col[h][left]); left++; } if (sum+col[i][left-1]-col[h][left-1]==k) f[i][j]=min(f[i][j],(i-h+j-left+2)*2); } } fr(i,1,m) fr(j,1,n) f[i][j]=min(f[i][j],min(f[i-1][j],f[i][j-1])); } int main() { int x,y,t; cin >> m >> n >> t >> k; while (t--) scanf("%d%d",&x,&y), a[x][y]++; fr(x,1,m) fr(y,1,n) col[x][y]=col[x-1][y]+a[x][y]; calc(Bot_Right,m,n); fr(x,1,m) fr(y,1,n) col[x][y]=col[x-1][y]+a[m+1-x][n+1-y]; calc(Top_Left,m,n); int re=oo; fr(x,1,m) fr(y,1,n) { if (x<m) re=min(re,Bot_Right[x][y]+Top_Left[m-x][n]); if (y<n) re=min(re,Bot_Right[x][y]+Top_Left[m][n-y]); } if (re==oo) cout << "NO" << endl; else cout << re << endl; return 0; }
Code mẫu của ladpro98
#include <iostream> #include <cstdio> #include <algorithm> const int N = 255; const int oo = 1000000000; using namespace std; int a[N][N], b[N][N], col[N][N], s[N], minP[N], n, m, k, t, res; void Init() { scanf("%d %d\n", &m, &n); scanf("%d %d\n", &t, &k); int x, y; for(int i=0; i<t; i++) { scanf("%d %d\n", &x, &y); a[x][y]++; } for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) col[i][j] = col[i-1][j] + a[i][j]; res = oo; } int Slide(int u, int d) { int j, l, p = oo; for(j=1; j<=n; j++) s[j] = s[j-1] + col[d][j] - col[u-1][j]; l = 0; for(j=1; j<=n; j++) { while ((s[j] - s[l]) > k) l++; while (s[j] - s[l + 1] == k) ++l; if ((s[j] - s[l]) == k) p = min(p, ((j - l) << 1) + ((d - u + 1) << 1)); } return p; } void Process() { int i, j; minP[0] = oo; for(i=1; i<m; i++) { minP[i] = minP[i-1]; for(j=i; j>0; j--) minP[i] = min(minP[i], Slide(j,i)); } for(i=m; i>1; i--) for(j=i; j<=m; j++) res = min(res, minP[i-1] + Slide(i,j)); } void Rotate() { for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) b[i][j] = a[j][i]; for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) a[i][j] = b[i][j]; swap(m, n); for(int i=1; i<=m; i++) for(int j=1; j<=n; j++) col[i][j] = col[i-1][j] + a[i][j]; } int main() { Init(); Process(); Rotate(); Process(); if (res == oo) printf("NO"); else printf("%d", 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 oo = 1000111000; int m, n, q, k; int a[511][511], s[511][511]; int l[511], r[511], u[511], d[511], x[511]; int main() { GN(m); GN(n); int q; GN(q); GN(k); while (q--) { int u, v; GN(u); GN(v); ++a[u][v]; } FOR(i,1,m) FOR(j,1,n) s[i][j] = s[i-1][j] + a[i][j]; FOR(i,1,m) u[i] = d[i] = oo; FOR(j,1,n) l[j] = r[j] = oo; FOR(i1,1,m) FOR(i2,i1,m) { FOR(j,1,n) *(x+j) = *(*(s+i2)+j) - *(*(s+i1-1)+j); int jj = 0, sum = 0, now; FOR(j,1,n) { sum -= *(x+j-1); while (jj < n && sum < k) { ++jj; sum += *(x+jj); } if (sum == k) { now = ((jj - j + 1) + (i2 - i1 + 1)) << 1; if (*(l+jj) > now) *(l+jj) = now; if (*(r+j) > now) *(r+j) = now; if (*(u+i1) > now) *(u+i1) = now; if (*(d+i2) > now) *(d+i2) = now; } } } FOR(i,2,m) d[i] = min(d[i], d[i-1]); FORD(i,m-1,1) u[i] = min(u[i], u[i+1]); FOR(j,2,n) l[j] = min(l[j], l[j-1]); FORD(j,n-1,1) r[j] = min(r[j], r[j+1]); // PR(d, m); // PR(u, m); // PR(l, n); // PR(r, n); int res = oo; FOR(i,1,m-1) res = min(res, d[i] + u[i+1]); FOR(j,1,n-1) res = min(res, l[j] + r[j+1]); if (res == oo) puts("NO"); else printf("%d\n", res); return 0; }
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<math.h> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> #define fi first #define se second #define PB push_back #define MP make_pair #define ep 0.0000001 #define oo 1ll << 60 #define mod 1000000007 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define rep(i, n) for(int i = 0; i < n; i++) #define FOR(i, a, b) for(int i = a; i <= b; i++) #define FORD(i, a, b) for(int i = a; i >= b; i--) //#define g 9.81 double const PI=4*atan(1.0); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; typedef long long ll; void OPEN(){ freopen("A.in","r",stdin); freopen("A.out","w",stdout); } int m, n, k, num; int x[10011], y[10011], a[255][255], sum[255][255], f[255][255]; int so(int x1, int Y1, int x2, int y2){ return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][Y1 - 1] + sum[x1 - 1][Y1 - 1]; } int chuvi(int x1, int Y1, int x2, int y2){ return (x2 - x1 + 1 + y2 - Y1 + 1) * 2; } int tinh(){ memset(a, 0, sizeof(a)); memset(sum, 0, sizeof(sum)); rep(i, k) a[y[i]][x[i]]++; FOR(i, 1, n) FOR(j, 1, m){ sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + a[i][j]; } int d1[255], d2[255]; memset(d1, 1, sizeof(d1)); memset(d2, 1, sizeof(d2)); FOR(i, 1, n) FOR(j, i, n){ f[i][j] = 1 << 20; int run = 1; for(int k = 1; k <= m; k++){ while(so(i, k, j, run) < num && run < m) run ++; if(so(i, k, j, run) == num) f[i][j] = min(f[i][j], chuvi(i, k, j, run)); } FOR(k, j, n) d1[k] = min(d1[k], f[i][j]); FOR(k, 1, i) d2[k] = min(d2[k], f[i][j]); } int res = 1 << 20; FOR(i, 1, n - 1) res = min(res, d1[i] + d2[i + 1]); return res; } int main(){ // OPEN(); scanf("%d %d %d %d", &m, &n, &k, &num); rep(i, k) scanf("%d %d", &x[i], &y[i]); int kq = tinh(); swap(n, m); rep(i, k) swap(x[i], y[i]); kq = min(kq, tinh()); if(kq < 10000) printf("%d", kq); else printf("NO"); }
Bình luận