KPLANK – spoj

Đề bài:

Thuật toán:

  • Sừ dụng thuật toán tìm max/min trên một đoạn tịnh tiến.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e6)+3;
var
  st : array[1..maxn] of longint;
  a,l,r : array[1..maxn] of longint;
  i,j,n : longint;
  res : int64;
  top : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to n do read(a[i]);
  end;
procedure push(x : longint);
  begin
    inc(top);
    st[top] := x;
  end;
function get: longint;
  begin
    get := st[top];
  end;
procedure process;
  begin
    top :=0 ;
    for i:=1 to n do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then l[i] := 0 else l[i] := get;
        push(i);
      end;
    top := 0;
    for i:=n downto 1 do
      begin
        while (top<>0) and (a[get]>=a[i]) do dec(top);
        if top=0 then r[i]:=n+1 else r[i] := get;
        push(i);
      end;
    for i:=1 to n do
      if r[i]-l[i]-1>=a[i] then
        res := max(res, a[i]);
end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(res);
  end;
begin
  enter;
  process;
  print;
end.

QBRECT – spoj

Đề bài:

Thuật toán:

Sau đây là cách tìm hình chữ nhật lớn nhất trong thời gian O(n^2):

Với mỗi ô j trên hàng i, ta tìm f(j) là số ô 1 liên tiếp trên cột j, tính từ hàng i trở lên. Sau đó, với mỗi cột j, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có f nhỏ hơn f(j), sau đó tính diện tích hình chữ nhật ở cột j là S=f(j)×(r−l−1) với l,r là chỉ số 2 ô bên trái và bên phải nói trên.
Hình minh hoạ khi tính f(4):
deque-yeulaptrinh.pw
Để tìm l,r nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Code:

uses    math;
const   fi='';
        fo='';
        maxn=1000;
var     a:array[1..maxn,1..maxn] of byte;
        i,j,m,n,res,top:longint;
        h,s,left,right:array[1..maxn] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    close(input);
end;
procedure push(x:integer);
begin
    inc(top);
    s[top]:=x;
end;
function get:integer;
begin
    exit(s[top]);
end;
procedure pop;
begin
    dec(top);
end;
procedure xuly;
begin
    for i:=1 to m do
     begin
        for j:=1 to n do
           if a[i,j]=1 then
                begin
                    h[j]:=h[j]+1;
                end else h[j]:=0;
        top:=0;
        for j:=1 to n do
            begin
                while (top<>0) and (h[j]<=h[get]) do pop;
                if top=0 then left[j]:=0 else left[j]:=get;
                push(j);
            end;
        top:=0;
        for j:=n downto 1 do
                begin
                    while (top<>0) and (h[j]<=h[get]) do pop;
                    if top=0 then right[j]:=n+1 else right[j]:=get;
                    push(j);
                end;
        for j:=1 to n do
                begin
                    res:=max(res,h[j]*(right[j]-left[j]-1));
                end;
     end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.

CROSS12 – spoj

Đề bài:


Thuật toán:


Đầu tiên ta cần tính thời gian qua cầu của mỗi người (khi đi một mình). Có thể tính bằng tham lam như cách được sử dụng trong code ở trên hoặc kết hợp quy hoạch động với deque để tìm min trên đoạn tịnh tiến.

Độ phức tạp khi tính là $O(m)$ cho mỗi người, vì $r$ chỉ dao động từ 1 đến 100 nên ta dùng một mảng phụ để cache giá trị đã tính lại.

Sau khi tính xong, gọi thời gian qua cầu của $n$ người là $A(n)$, ta sắp xếp $A$ tăng dần.

Gọi $F(i)$ là thời gian ít nhất để những người từ 1 đến i qua cầu, ta có công thức:

$ F(1) = A(1) \ F(2) = A(2) \ F(i) = min \begin{cases} F(i-2) + A(1) + 2A(2) + A(i) & \quad (1)\ F(i-1) + A(1) + A(i) & \quad (2)\ \end{cases} $

Trong trường hợp $(1)$, ta cho $A(2)$ quay về, sau đó $A(i)$ và $A(i-1)$ qua cầu, sau đó $A(1)$ từ bên kia cầu quay về, $A(1)$ và $A(2)$ cùng qua cầu.

Trong trường hợp $(2)$, $A(1)$ quay về sau đó cùng $A(i)$ qua cầu.

Code:


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int time(int r, int m, const char *bridge) {
    int i = 0, res = 1;
    while (i + r <= m) {
        res++;
        i += r;
        while (bridge[i] == '1') i--;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (auto &x: a) cin >> x;
    string bridge; cin >> bridge;
    bridge = '0' + bridge + '0';
    vector<int> cache(101, 0);
    for (auto &x: a) {
        if (!cache[x]) x = cache[x] = time(x, m, bridge.data());
        else x = cache[x];
    }
    sort(a.begin(), a.end());
    if (n == 1) cout << a[0];
    else if (n == 2) cout << a[1];
    else {
        int f0 = a[0], f1 = a[1];
        for (int i=2; i<n; i++) {
            int f2 = min(f0 + a[0] + 2*a[1] + a[i], f1 + a[0] + a[i]);
            f0 = f1, f1 = f2;
        }
        cout << f1;
    }
    return 0;
}

MESSAGE1 – spoj

Đề bài

Thuật toán
message1-yeulaptrinh.pw

Ở bài này ta dời bảng B như hình, trong mỗi lần dời ta so sách các ô trong vùng giao nhau nữa 2 bảng, ô bằng nhau có giá trị 1, khác nhau có giá trị 0.

Cụ thể hơn, giả sử ta dời bảng B theo một vector $(x, y)$, khi đó ô $A(i, j)$ sẽ được so sánh với ô $B(i-x, j-y)$. Ta tính toạ độ các ô trong phần giao giữa 2 bảng như sau, có 4 điều kiện:

$
\begin{cases}
0 <= i < m\\
0 <= j < n\\
0 <= i-x < m\\
0 <= i-y < n\\
\end{cases}
$

Từ đó suy ra:

$
\begin{cases}
max(0, x) <= i < min(m, m + x)\\
max(0, y) <= j < min(n, n + y)\\
\end{cases}
$

Sau đó ta tìm hình chữ nhật chứa toàn số 1 và có diện tích lớn nhất (như bài QBRECT).

Sau đây là cách tìm hình chữ nhật như trên trong thời gian $O(n^2)$:

Với mỗi ô $j$ trên hàng $i$, ta tìm $f(j)$ là số ô 1 liên tiếp trên cột $j$, tính từ hàng $i$ trở lên. Sau đó, với mỗi cột $j$, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có $f$ nhỏ hơn $f(j)$, sau đó tính diện tích hình chữ nhật ở cột $j$ là $S = f(j)\times(r – l – 1)$ với $l, r$ là chỉ số 2 ô bên trái và bên phải nói trên.

Hình minh hoạ khi tính $f(4)$:

message1-2-yeulaptrinh.pw

Để tìm $l, r$ nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Độ phức tạp của toàn bộ lời giải là $O(n^4)$.

Code

#include <iostream>
#include <vector>
#include <string>
using namespace std;
 
void calc(int &res, int x, int y, const vector<string> &a, const vector<string> &b) {
    int m = a.size(), n = a[0].size();
    int low_i = max(0, x), high_i = min(m, m + x);
    int low_j = max(0, y), high_j = min(n, n + y);
    if ((high_i - low_i)*(high_j - low_j) <= res) return;
    vector<int> f(high_j, 0);
    vector<int> l(high_j), q(high_j), idx(high_j);
    for (int i=low_i; i < high_i; i++) {
        int top = 0;
        for (int j=low_j; j < high_j; j++) {
            if (a[i][j] == b[i-x][j-y]) {
                f[j]++;
                while (top && q[top-1]>=f[j]) top--;
                if (!top) l[j] = low_j-1;
                else l[j] = idx[top-1];
                q[top] = f[j], idx[top] = j, top++;
            } else {
                f[j] = 0;
                q[0] = 0, idx[0] = j, top = 1;
            }
        }
        top = 0;
        int r;
        for (int j=high_j-1; j >= low_j; j--) {
            if (f[j]) {
                while (top && q[top-1]>=f[j]) top--;
                if (!top) r = high_j;
                else r = idx[top-1];
                res = max(res, f[j]*(r - l[j] - 1));
                q[top] = f[j], idx[top] = j, top++;
            } else {
                q[0] = 0, idx[0] = j, top = 1;
            }
        }
    }
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> m >> n;
        vector<string> a(m), b(m);
        for (auto &s: a) cin >> s;
        for (auto &s: b) cin >> s;
        int res = 0;
        for (int i=-m+1; i<m; i++) for (int j=-n+1; j<n; j++) {
            calc(res, i, j, a, b);
        }
        cout << res << '\n';
    }
    return 0;
}

MINK – spoj

Đề bài:

Thuật toán:

  • Bài này chỉ thuần sử dụng thuật toán Kỹ thuật sử dụng Deque tìm Max/Min trên một đoạn tịnh tiến

Code:

const   fi='';
        fo='';
        maxn=17000;
var     a:array[1..maxn] of longint;
        hold:array[1..maxn] of integer;
        i,j,n,k,t:integer;
        top,below:integer;
procedure push(i:integer);
begin
    while (top<>below-1) and (a[i]<a[hold[top]]) do dec(top);
    inc(top); hold[top]:=i;
end;
procedure pop(i:integer);
begin
    while (below<>top+1) and (hold[below]<=i) do inc(below);
end;
procedure print;
begin
    write(a[hold[below]],' ');
end;
procedure solve;
var     i:integer;
begin
    top:=0; below:=1;
    for i:=1 to k do push(i); print;
    for i:=k+1 to n do
        begin
            pop(i-k);
            push(i);
            print;
        end;
    writeln;
end;
procedure main;
var     i,j:integer;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    readln(t);
    for i:=1 to t do
        begin
            read(n,k);
            for j:=1 to n do read(a[j]);
            solve;
        end;
 
    close(input);close(output);
end;
begin
    main;
end.
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef long long ll;
typedef pair<int,int> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
deque<int> q;
int i, n, k, a[20000], t, tt;
int main() {
	cin >> t;
	for (int tt=1; tt<=t; tt++) {
        cin >> n >> k;
        for (int i=1; i<=n; i++) cin >> a[i];
        while (!q.empty()) q.pop_back();
        for (int i=1; i<=n; i++) {
            while ((!q.empty())&&(q.front() < i-k+1)) q.pop_front();
            while ((!q.empty())&&(a[q.back()]>a[i])) q.pop_back();
            q.push_back(i);
            if (i>=k) cout << a[q.front()] << " ";
        }
        cout << endl;
	}
	return 0;
}

CREC01 – SPOJ

Đề bài:

Thuật toán:

  • Bài này ta sử dụng kỹ thuật deque. Thuật toán cũng không có gì phức tạp. Bạn có thể đọc code bên dưới để hiểu thêm

Code:

Pascal : https://ideone.com/swTkml

const   fi      ='';
        fo      ='';
        oo      =1000;
 
var     a       :array[0..oo,0..oo] of 0..1;
        l,h,dem:array[0..oo+1] of int64;
        m, n    :longint;
 
procedure Optimize;
var     i, j    :longint;
        ans     :int64;
begin
        fillchar(h, sizeof(h),0);
        ans:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                begin
                                        if a[i,j]=1 then begin
                                        l[j]:=j;
                                        h[j]:=h[j]+1;
                                        while h[l[j]-1]>h[j] do
                                                l[j]:=l[l[j]-1];
                                        dem[j]:=h[j]*(j-l[j]+1)+dem[l[j]-1];
                                        ans:=ans+dem[j];
                                        //writeln(ans,'==');
                                        //if (i=3) and (j=2) then writeln(dem[1]);
                                        end
                                        else begin
                                                dem[j]:=0;
                                                l[j]:=0;
                                                h[j]:=0;
                                        end;
 
                                end;
 
                end;
        writeln(ans);
end;
 
procedure run;
var     i, j, tg    :longint;
        s       :ansistring;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                        readln(s);
                        for j:=1 to n do
                                        val(s[j],a[i,j]);
                end;
        Optimize;
        close(input);close(output);
 
end;
 
begin
        run;
end.

C++ : https://ideone.com/S0t4zZ

using namespace std;
#include<bits/stdc++.h>
 
#define BG begin()
#define ED end()
#define st first
#define nd second
#define PB push_back
#define PF push_front
#define FOR(i,a,b) for (long long i=a;i<b;i++)
#define FORE(i,a,b) for (long long i=a;i<=b;i++)
#define FORD(i,a,b) for (long long i=a;i>=b; i--)
#define ri(n)({\
    int neg=0;\
    n=0;\
    char ch;\
    for(ch=getchar(); ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') neg=1-neg;\
    n=ch-48;\
    for(ch=getchar(); ch>='0' && ch<='9'; ch=getchar()) n=(n<<3)+(n<<1)+ch-48;\
    if (neg) n=-n;\
})
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> II;
typedef pair<ll,ll> LL;
const ll INF=1000000000+7;
const double esp=1e-13;
const double pi=3.141592653589;
 
 
ll m, n, a[1001][1001], H[1001], dem[1001], L[1001];
 
int main()
{
    //freopen("CREC01.inp", "r", stdin);
    //freopen("CREC01.out", "w", stdout);
    cin>>m>>n;
    char ch;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            cin>>ch;
            a[i][j] = ch - '0';
        }
    memset(H, 0, sizeof(H));
    memset(L, 0, sizeof(L));
    memset(dem, 0, sizeof(dem));
    long long ans = 0;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            //cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
            if (a[i][j] == 1) {
                H[j]++;
                int k = j;
                while ( (k > 1) && (a[i][k-1] == 1) && (H[ k - 1 ] >= H[j]) ) k = L[k - 1];
                L[j] = k;
                dem[j] = H[j]*(j - L[j] + 1) + dem[L[j] - 1];
                ans += dem[j];
                //cout<<i<<"=="<<j<<"=="<<"=="<<H[j]<<"=="<<ans<<endl;
            }
            else
            {
                H[j] = 0;
                dem[j]= 0;
                L[j] = 0;
            }
        }
    cout<<ans;
}