MSE07B – spoj

Đề bài:

Thuật toán:

  • Nếu bạn sử dụng C++ thì có thể dùng cấu trúc dữ liệu có sẵn là std::set, còn nếu dùng Pascal thì sẽ phải code dài hơn một chút.
  • Toàn bộ về std::set cho bạn nào dùng C++: http://yeulaptrinh.pw/938/set-trong-c/

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
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;}
const int MAXN = 1E6+3;
const int oo = 1e9+3;
 
set<PII> s;
set<PII>::iterator it;
int p, k, x, i;
 
int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> x;
    while (x != 0) {
        //
        if (x == 1) {
            cin >> k >> p;
            s.insert(PII(p,k));
        }
        //
        if (x == 2)
        if (!s.empty()) {
            it = s.end(); -- it;
            cout << it -> se << endl;
            s.erase(it);
        } else cout << 0 << endl;
        //
        if (x==3)
        if (!s.empty()) {
            it = s.begin();
            cout << it -> se << endl;
            s.erase(it);
        } else cout << 0 << endl;
        //
        cin >> x;
    }
	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;
}

Cấu trúc dữ liệu Heap và ứng dụng

Heap là một trong những cấu trúc dữ liệu đặc biệt quan trọng, nó giúp ta có thể giải được nhiều bài toán trong thời gian cho phép. Độ phức tạp thông thường khi làm việc với Heap là O(logN). CTDL Heap được áp dụng nhiều trong các bài toán tìm đường đi ngắn nhất, tìm phần tử max, min… và trong lập trình thi đấu. Vậy Heap là gì? Cài đặt Heap như thế nào?

Heap là gì?

Heap thực chất là một cây cân bằng thỏa mãn các điều kiện sau

  • Một nút có không quá 2 nút con.
  • Với Heap Max thì nút gốc là nút lớn nhất, mọi nút con đều không lớn hơn nút cha của nó. Với Heap Min thì ngược lại.

Mặc dù được mô tả như cây nhưng Heap có thể được biểu diễn bằng mảng. Nút con của nút i là 2*i và 2*i+1. Do Heap là cây cân bằng nên độ cao của 1 nút luôn <= logN.

Ứng dụng chủ yếu của Heap là tìm Min, Max trong 1 tập hợp động (có thể thay đổi, thêm, bớt các phần tử) nhưng như vậy đã là quá đủ.

heap-yeulaptrinh

(Mô hình biểu diễn Heap bằng cây nhị phân và bằng mảng)

Các thao tác với Heap

Ở đây mình hướng dẫn các bạn với Heap Max còn với Heap Min thì tương tự

Khai báo

Ở ví dụ này, Heap sẽ là mảng một chiều kiểu LongInt, nHeap là số phần tử của mảng.

Const
  maxn = 100000;
Var
  nHeap : LongInt;
  Heap : array[0..maxn] of LongInt;

1. UpHeap

Nếu 1 nút lớn hơn nút cha của nó thì di chuyển nó lên trên:
upheap-yeulaptrinh

Procedure UpHeap(i : LongInt);
Begin
  if (i = 1) or (Heap[i] < Heap[i div 2]) then exit; // Nếu i là nút gốc hoặc  nhỏ hơn nút cha thì không làm việc
  swap(Heap[i] , Heap[i div 2]); // Đổi chỗ 2 phần tử trong Heap;
  UpHeap(i div 2); // Tiếp tục di chuyển lên trên
end;

2. DownHeap

downheap-1downheap-2

downheap-3

Procedure DownHeap(i : LongInt);
  Var
    j : LongInt;
  Begin
    j := i*2;
    if j > nHeap then exit; // Nếu i không có nút con thì không làm việc
    if (j < nHeap) and (Heap[j] < Heap[j+1]) then Inc(j); // Nếu i có 2 nút con thì chọn nút ưu tiên hơn
    if Heap[i] < Heap[j] then // Nếu nút cha nhỏ hơn nút con
      begin
        swap(Heap[i] , Heap[j]); // Đổi chỗ 2 phần tử trong Heap
        DownHeap(j); // Tiếp tục di chuyển xuống dưới
      end;
  end;

3. Push

Đưa 1 phần tử mới vào Heap: Thêm 1 nút vào cuối Heap và tiến hành UpHeap từ đây:

Procedure Push(x : LongInt);
  Begin
    Inc(nHeap); // Tăng số phần tử của Heap
    Heap[nHeap] := x; // Thêm x vào Heap
    UpHeap(nHeap);
  End;

4. Pop

Rút ra 1 phần tử ở vị trí v trong Heap: Gán Heap[v] := Heap[nHeap] rồi tiến hành chỉnh lại Heap:

Function Pop(v : LongInt) : LongInt;
  Begin
    Pop := Heap[v]; // Lấy phần tử ở vị trí v ra khỏi Heap
    Heap[v] := Heap[nHeap]; // Đưa phần tử ở cuối Heap vào vị trí v
    Dec(nHeap); // Giảm số phần tử của Heap đi 1
    {Chỉnh lại Heap}
    UpHeap(v);
    DownHeap(v);
  End;

Nguồn: không rõ

C11STR2 – spoj

Đề bài:

Thuật toán:

  • Nhận thấy nếu $x$ ký tự cuối của xâu $a$ trùng với $x$ ký tự cuối của xâu $b$ thì có thể ghép. Để kiểm tra hai xâu con có trùng nhau không với ĐPT O(n) thì ta sử dụng Hash.
  • Ta cần tìm $x$ lớn nhất.
  • Ta sẽ duyệt $x$ từ max(length(a),length(b)) về 0. Nếu đã tìm thấy $x$ thỏa mãn thì break.

Code:

{$H+}
uses math;
const
  fi='';
  fo='';
  base=trunc(1e9);
  pp=307;
  maxn=trunc(1e5);
var
  a,b,c : string;
  i,j,n,m : longint;
  ha,hb : array[0..maxn] of int64;
  pow : array[0..maxn] of int64;
procedure enter;
begin
  assign(input,fi);reset(input);
  readln(a);
  readln(b);
  close(input);
end;
procedure swap( var m,n : longint; var a,b : string);
var tg1 : longint;
    tg2 : string;
begin
  tg1 := m ; m := n ; n:= tg1;
  tg2 := a; a :=b ; b:= tg2;
end;
function getha(l,r : longint) : int64;
  begin
    getha := (ha[r]-ha[l-1]*pow[r-l+1] + base*base)  mod base;
  end;
function gethb(l,r : longint) : int64;
  begin
    gethb := (hb[r]-hb[l-1]*pow[r-l+1] + base*base) mod base;
  end;
procedure process;
begin
  m := length(a); n := length(b);
  c := a + b;
  //if m<n then swap(m,n,a,b);
  pow[0] := 1;
  for i:=1 to max(m,n) do pow[i] := pow[i-1]*pp mod base;
  ha[0] := 0; hb[0] := 0;
  for i:=1 to m do ha[i] := (ha[i-1]*pp + ord(a[i])-48) mod base;
  for i:=1 to n do hb[i] := (hb[i-1]*pp + ord(b[i])-48) mod base;
  for i:=min(m,n) downto 1 do
    if gethb(1,i) = getha(m-i+1,m) then
      begin
        delete(c,m-i+1,i);
        break;
      end;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(c);
  close(output);
end;
begin
  enter;
  process;
  print;
end.

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;
}

QBHEAP – spoj

Đề bài:

Thuật toán:

  • Với C++ bạn có thể dùng sẵn CTDL Priority Queue (hàng đợi ưu tiên). Còn với Pascal thì bạn phải tự viết CTDL Heap

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int MAXN = 20000;
string s;
priority_queue <int> h;
char key;
int num, a[MAXN];
 
bool cmp(int a, int b) {
    return (a > b);
}
 
int main() {
    //freopen("test.inp","r",stdin);
    //freopen("test.out","w",stdout);
    // solve
    getline(cin, s);
    do {
        key = s[0];
        if (key == '+') {
            s.erase(0,1);
            num = atoi(s.c_str());
            if (h.size()<15000) h.push(num);
        } else if (!h.empty())
        {
            num = h.top();
            while (!h.empty() && h.top()==num) h.pop();
        }
        getline(cin, s);
    } while (s != "");
    // pop
    int res = 0;
    while (!h.empty()) {
        res++;
        a[res] = h.top();
        while (!h.empty() && h.top()==a[res]) h.pop();
    }
    // print
    cout << res << endl;
    for (int i = 1; i <= res; i++) cout << a[i] << endl;
    return 0;
}
const   fi='';
        fo='';
        maxn=15000+3;
var     h:array[1..maxn] of longint;
        i,j:longint;
        res:array[0..maxn] of longint;
        nh,n,ans:longint;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x,i,j:longint;
begin
            i:=l;j:=r;
            x:=res[(i+j) div 2];
            repeat
                while res[i]>x do inc(i);
                while res[j]<x do dec(J);
                if i<=j then
                        begin
                            swap(res[i],res[j]);
                            inc(i);dec(j);
                        end;
            until i>j;
            if i<r then qs(i,r);
            if j>l then qs(l,j);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:= i + i;
        if j>nh then exit;
        if (j<nh) and (h[j]<h[j+1]) then inc(j);
        if h[j]>h[i] then
                begin
                        swap(h[i],h[j]);
                        downheap(j);
                end;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if h[i]>h[j] then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
procedure push(x:longint);
begin
        inc(nh);
        h[nh]:=x;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure xuat;
begin
        for i:=1 to n do
                if res[i]<>res[i-1] then writeln(res[i]);
end;
procedure main;
var     tam,s:string;
        x,err:longint;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    while not seekeof(input) do
        begin
            readln(s);
            if s[1]='+' then
            begin
              if nh<15000 then
                begin
                    tam:=copy(s,2,length(s));
                    val(tam,x,err);
                    push(x);
                end
                end
                ELSE
                if nh>0 then
                begin
                        if nh>0 then x:=pop;
                        while (nh>0) and (h[1]=x) do pop;
                end;
        end;
        for i:=1 to nh do
                begin
                        res[i]:=pop;
                        inc(n);
                end;
        qs(1,n);
        res[0]:=-1;
        for i:=1 to n do
                if res[i]<>res[i-1] then inc(ans);
        writeln(ans);
        xuat;
 
    close(input);close(output);
end;
begin
    main;
end.

PALINY – spoj

Đề bài:


Thuật toán:


Gợi ý 1
Gợi ý 2

Code:


{$H+}
uses math;
const
  fi='';//paliny.inp';
  fo='';//paliny.out';
  maxn=50003;
  pp=307;
  base=trunc(1e9)+7;
var
  i,j,n,d,c,g,top,ans : longint;
  ha,hb,pow : array[0..maxn] of int64;
  a : array[1..maxn] of longint;
  s : string;
function gethash1(l,r : longint) : int64;
  begin
    gethash1 := (ha[r] - ha[l-1] * pow[r-l+1] + base * base) mod base;
  end;
function gethash2(l,r : longint) : int64;
  begin
    gethash2 := (hb[r] - hb[l+1] * pow[l-r+1] + base * base) mod base;
  end;
function ok ( le : longint) : boolean;
  var i,j : longint;
  begin
    for i := 1 to n - le + 1 do
      if gethash1(i,i+le-1) = gethash2(i+le-1,i) then exit(true);
    exit(false);
  end;
procedure process;
  begin
  d := 1 ;
  c := top ;
  g := (d+c) div 2;
  while (G<>d) and (g<>C) do
    begin
      if ok (a[g]) then d := g else c := g;
      g := (d+c) div 2;
    end;
  for g := c downto d do
    if ok (a[g]) then
      begin
        ans := max(ans,a[g]);
        exit;
      end;
  end;
procedure push(x : longint);
  begin
    inc(top);
    a[top] := x;
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(n);
  readln(s);
  pow[0] := 1;
  for i := 1 to n do pow[i] := pow[i-1] * pp mod base;
  for i := 1 to n do ha[i] := ( ha[i-1] * pp + ord(s[i]) ) mod base;
  for i := n downto 1 do hb[i] := ( hb[i+1] * pp + ord(s[i]) ) mod base;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 0 then push(i);
  process;
  top := 0;
  for i := 1 to n do
    if i mod 2 = 1 then push(i);
  process;
  writeln(ans);
  close(input);close(output);
end.