Tạo bài viết
Đăng ký
02/10/2018, 13:59

MINCUT spoj – VOI 2015 Day 2 – Cắt hình

Lời giải cho đề thi học sinh giỏi quốc qua môn tin học năm học 2014 – 2015, VOI 2015. MINCUT spoj – VOI 2015 Day 2 – Cắt hình Nguồn đề bài : http://vn.spoj.com/problems/MINCUT/ 1. Đề bài MINCUT spoj Cho A là lưới ô vuông gồm m dòng và n cột. Các dòng của lưới được đánh số ...

Lời giải cho đề thi học sinh giỏi quốc qua môn tin học năm học 2014 – 2015, VOI 2015. MINCUT spoj – VOI 2015 Day 2 – Cắt hình

Nguồn đề bài: http://vn.spoj.com/problems/MINCUT/

1. Đề bài MINCUT spoj

Cho A là lưới ô vuông gồm m dòng và n cột. Các dòng của lưới được đánh số từ 1 đến m, từ trên xuống dưới. Các cột của lưới được đánh số từ 1 đến n, từ trái sang phải. Ô nằm trên giao của dòng i và cột j của lưới, được gọi là ô (i, j), chứa số nguyên không âm ai,jcó giá trị không vượt quá 106.

Các lưới ô vuông như vậy luôn là đối tượng cho nhiều nghiên cứu thú vị. Vừa qua, trong giờ học ôn luyện cho kỳ thi học sinh giỏi Tin học, Hùng được cô giáo giao cho giải quyết bài toán trả lời truy vấn sau đây đối với bảng đã cho:

Cho một hình chữ nhật con có ô trái trên là ô (x,y) và ô phải dưới là ô (u,v), cần đưa ra chênh lệch nhỏ nhất trong số các chênh lệch giữa hai tổng các số trong hai hình chữ nhật thu được bằng việc cắt ngang hoặc cắt dọc hình chữ nhật đã cho dọc theo đường kẻ của lưới. Giả thiết (x,y) và (u,v) là hai ô khác nhau trên lưới.

Bạn hãy giúp Hùng giải quyết bài toán đặt ra.

Yêu cầu: Cho lưới A và k bộ xq, yq , uq, vq (q = 1, 2, …, k) tương ứng với k truy vấn, hãy đưa ra các câu trả lời cho k truy vấn.

Dữ liệu vào

  • Dòng đầu tiên chứa ba số nguyên m, n, k (k ≤ m×n);
  • m dòng tiếp theo, dòng thứ i chứa n số nguyên không âm ai1, ai2, …, ain;
  • Dòng thứ q trong số k dòng tiếp theo chứa 4 số nguyên xq, yq, uq, vq (q = 1, 2, …, k).

Dữ liệu ra

  • Ghi ra file văn bản MINCUT.OUT gồm k dòng, mỗi dòng chứa một số là câu trả lời cho một truy vấn theo thứ tự xuất hiện trong file dữ liệu vào.

Ràng buộc

  • Có 30% số test ứng với 30% số điểm của bài có m, n ≤ 10.
  • Có 30% số test khác ứng với 30% số điểm của bài có  m, n ≤ 100.
  • Có 40% số test  ứng với 40% số điểm còn lại của bài có m, n ≤ 1000.

Ví dụ

Input

3 3 2
1 1 1
1 1 1
1 1 1
1 1 3 3
1 1 3 2

Output

3

0

2. Hướng dẫn MINCUT spoj

– Xây dựng mảng tổng A[i,j] là tổng của hình chữ nhật từ ô 1;1 đến ô i;j. giống như bài BONUS trên vn spoj.

BONUS spoj – VOI 2011 Phần thưởng

vừa nhập vừa xử lí có thể viết như sau:

for i:=1 to m do

for j:=1 to n do

begin

read(f,a[i,j]);

A[i,j]:=A[i,j]+A[i-1,j]+a[i,j-1]-A[i-1,j-1];

end;

– Sau đó chặt nhị phân để tìm độ chênh lệch nhỏ nhất. ý tưởng là vậy, cách chặt nhị phân các bạn có thể tham khảo code mẫu.

Độ phức tạp thuật toán: O(n^2 log2 N).

3. code tham khảo MINCUT spoj

a. Code Pascal

const fi='; nmax=1000; type data=longint; var f:text; A:array[0..nmax+1,0..nmax+1] of int64; n,m,k:data; function GetS(x,y,u,v:data):int64; begin gets:=A[u,v]-A[u,y-1]-a[x-1,v]+a[x-1,y-1]; end; function min(a,b:int64):int64; begin if a<b then exit(a); exit(b); end; procedure xuli(x,y,u,v:data); var i,j:data; res,Sfull,stam:int64; dau,cuoi,giua:data; begin Sfull:=getS(x,y,u,v); res:=high(int64); dau:=x; cuoi:=u-1; while dau<=cuoi do begin giua:=(dau+cuoi) shr 1; stam:=getS(x,y,giua,v); if 2*stam<=sfull then begin res:=min(res,sfull-2*stam); dau:=giua+1; end else cuoi:=giua-1; end; dau:=x; cuoi:=u-1; while dau<=cuoi do begin giua:=(dau+cuoi) shr 1; stam:=getS(x,y,giua,v); if 2*stam>=sfull then begin res:=min(res,2*stam-sfull); cuoi:=giua-1; end else dau:=giua+1; end; dau:=y; cuoi:=v-1; while dau<=cuoi do begin giua:=(dau+cuoi) shr 1; stam:=gets(x,y,u,giua); if 2*stam>=sfull then begin res:=min(res,2*stam-sfull); cuoi:=giua-1; end else dau:=giua+1; end; dau:=y; cuoi:=v-1; while dau<=cuoi do begin giua:=(dau+cuoi) shr 1; stam:=gets(x,y,u,giua); if 2*stam<=sfull then begin res:=min(res,sfull-2*stam); dau:=giua+1 end else cuoi:=giua-1; end; writeln(res); end; Procedure docfile; var i,j,x,y,u,v:data; begin assign(f,fi); reset(f); read(f,m,n,k); for i:=0 to m+1 do A[i,0]:=0; for j:=0 to n+1 do a[0,j]:=0; for i:=1 to m do for j:=1 to n do begin read(f,a[i,j]); A[i,j]:=A[i,j]+A[i-1,j]+a[i,j-1]-A[i-1,j-1]; end; for i:=1 to k do begin read(f,x,y,u,v); xuli(x,y,u,v); end; close(f); end; begin docfile; end.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
const   fi=';
        nmax=1000;
type    data=longint;
var
        f:text;
        A:array[0..nmax+1,0..nmax+1] of int64;
        n,m,k:data;
 
function GetS(x,y,u,v:data):int64;
begin
        gets:=A[u,v]-A[u,y-1]-a[x-1,v]+a[x-1,y-1];
end;
 
function min(a,b:int64):int64;
begin
        if a<b then exit(a); exit(b);
end;
 
procedure xuli(x,y,u,v:data);
var     i,j:data;
        res,Sfull,stam:int64;
        dau,cuoi,giua:data;
begin
        Sfull:=getS(x,y,u,v);
        res:=high(int64);
        dau:=x;
        cuoi:=u-1;
        while dau<=cuoi do
                begin
                        giua:=(dau+cuoi) shr 1;
                        stam:=getS(x,y,giua,v);
                        if 2*stam<=sfull then
                                begin
                                        res:=min(res,sfull-2*stam);
                                        dau:=giua+1;
                                end
                        else
                                cuoi:=giua-1;
                end;
        dau:=x;
        cuoi:=u-1;
        while dau<=cuoi do
                begin
                        giua:=(dau+cuoi) shr 1;
                        stam:=getS(x,y,giua,v);
                        if 2*stam>=sfull then
                                begin
                                        res:=min(res,2*stam-sfull);
                                        cuoi:=giua-1;
                                end
                        else
                                dau:=giua+1;
                end;
        dau:=y;
        cuoi:=v-1;
        while dau<=cuoi do
                begin
                        giua:=(dau+cuoi) shr 1;
                        stam:=gets(x,y,u,giua);
                        if 2*stam>=sfull then
                                begin
                                        res:=min(res,2*stam-sfull);
                                        cuoi:=giua-1;
                                end
                        else
                                dau:=giua+1;
                end;
        dau:=y;
        cuoi:=v-1;
        while dau<=cuoi do
                begin
                        giua:=(dau+cuoi) shr 1;
                        stam:=gets(x,y,u,giua);
                        if 2*stam<=sfull then
                                begin
                                        res:=min(res,sfull-2*stam);
                                        dau:=giua+1
                                end
                        else
                                cuoi:=giua-1;
                end;
        writeln(res);
end;
 
Procedure docfile;
var     i,j,x,y,u,v:data;
begin
        assign(f,fi); reset(f);
        read(f,m,n,k);
        for i:=0 to m+1 do
                A[i,0]:=0;
        for j:=0 to n+1 do
                a[0,j]:=0;
        for i:=1 to m do
                for j:=1 to n do
                        begin
                                read(f,a[i,j]);
                                A[i,j]:=A[i,j]+A[i-1,j]+a[i,j-1]-A[i-1,j-1];
                        end;
        for i:=1 to k do
                begin
                        read(f,x,y,u,v);
                        xuli(x,y,u,v);
                end;
        close(f);
end;
 
begin
        docfile;
end.

b. Code C++

#include <stdio.h> long long s[1001][1001]; int n,m,k,u,v,z,t; long long value(int u,int v,int z,int t){ return s[z][t]-s[z][v-1]-s[u-1][t]+s[u-1][v-1]; } int main(){ scanf("%d%d%d",&n,&m,&k); for (int i=1;i<=n;i++) for (int j=1;j<=m;j++){ scanf("%lld",&s[i][j]); s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1]; } while (k--){ scanf("%d%d%d%d",&u,&v,&z,&t); long long res=1000000000000,tmp=value(u,v,z,t); for (int type=0;type<2;type++){ int d=(type==0)?(u):(v),c=(type==0)?(z-1):(t-1),g; while (d<=c){ g=(d+c)/2; long long s=(type==0?value(u,v,g,t):value(u,v,z,g))*2-tmp; if (s>=0){ res=(s<res)?(s):(res); c=g-1; } else { res=(-s<res)?(-s):(res); d=g+1; } } } printf("%lld ",res); } return 0; }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <stdio.h>
long long s[1001][1001];
int n,m,k,u,v,z,t;
long long value(int u,int v,int z,int t){
    return s[z][t]-s[z][v-1]-s[u-1][t]+s[u-1][v-1];
}
int main(){
    scanf("%d%d%d",&n,&m,&k);
    for (int i=1;i<=n;i++)
        for (int j=1;j<=m;j++){
            scanf("%lld",&s[i][j]);
            s[i][j]+=s[i-

Tạ Quốc Bảo

23 chủ đề

7270 bài viết

Có thể bạn quan tâm
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024