Tổng hợp tài liệu về thuật toán cặp ghép

Tài liệu của thầy Lê Minh Hoàng: http://yeulaptrinh.pw/wp-content/uploads/2016/05/BipartiteMatching.pdf

 

PBCGANGS – SPOJ

Đề bài: http://vn.spoj.com/problems/PBCGANGS/

Thuật toán:

  • Bài này thuật toán chỉ là DFS bình thường.
  • Đặc biệt là ở chỗ mình xây dựng đồ thị từ dữ liệu input. Các bạn có thể đọc code để hiểu hơn

Code:

Const
        fi      ='';
        fo      ='';
        maxn    =1001;
        maxm    =5001;
 
Type
        Arr1    =array[1..maxn] of longint;
        Arr2    =array[1..6*maxm] of longint;
        Arr3    =array[1..maxn] of boolean;
 
Var
        n,m     :longint;
        adj,link:arr2;
        head    :arr1;
        kt      :arr1;
        free    :Arr3;
        kq      :longint;
        dm      :longint;
        f       :text;
 
Procedure AE(u,v:longint);
begin
        inc(dm);
        adj[dm]:=v;
        link[dm]:=head[u];
        head[u]:=dm;
end;
 
Procedure Nhap;
var
        i,u,v   :longint;
        c,k     :char;
begin
        assign(f,fi);
        reset(f);
        readln(f,n);
        for i:=1 to n do
          begin
            kt[i]:=0;
            head[i]:=0;
            free[i]:=true;
          end;
        dm:=0;
        readln(f,m);
        for i:=1 to m do
          begin
            readln(f,c,u,v);
            if c='E' then
              begin
                if kt[u]=0 then kt[u]:=v
                  else
                    begin
                      ae(v,kt[u]);
                      ae(kt[u],v);
                    end;
                if kt[v]=0 then kt[v]:=u
                  else
                    begin
                      ae(u,kt[v]);
                      ae(kt[v],u);
                    end;
              end
            else
              begin
                ae(u,v);
                ae(v,u);
              end;
          end;
        close(f);
end;
 
Procedure DFS(u:longint);
var
        i,v     :longint;
begin
        free[u]:=false;
        i:=Head[u];
        while i<>0 do
          begin
            v:=adj[i];
            if free[v] then DFS(v);
            i:=link[i];
          end;
end;
 
Procedure Sol;
var
        u       :longint;
begin
        kq:=0;
        for u:=1 to n do
         if free[u] then
           begin
             inc(kq);
             DFS(u);
           end;
end;
 
Procedure Xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,kq);
        close(f);
end;
 
begin
        Nhap;
        Sol;
        Xuat;
end.

Tổng hợp đề thi và đáp án Olympic chuyên KHTN môn Tin học các năm

  • logo khtn - yeulaptrinh.pw

Olympic chuyên KHTN là kì thi hàng năm dành cho học sinh lớp 10, lớp 11 trường chuyên toàn quốc ở các môn: Toán học, Tin học, Vật lý, Hóa học và Sinh học.

Kì thi được tổ chức bởi trường THPT chuyên Khoa học Tự nhiên.\

YeuLapTrinh.pw xin được tổng hợp lại đề thi và đáp án cho các bạn tham khảo:

DEMSO – SPOJ

Đề bài:

Thuật toán:

  • Bài này sử dụng phương pháp đệ quy có nhớ
  • (thuật toán đang cập nhập)

Bạn có thể đọc code để hiểu rõ hơn.

Code:

Pascal

const
  fi='';
  fo='';
  maxn=20;
var
  a,b,tg1,tg2 : int64;
  aa : array[1..maxn] of longint;
  i,j,n,k,d : longint;
  f : array[0..maxn,0..maxn,0..maxn,false..true,false..true] of int64; 
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure chuanbi(x : int64; var n : longint);
  var i,j : longint;
  begin
    n := 0;
    while x>0 do
      begin
        inc(n); aa[n] := x mod 10;
        x := x div 10;
      end;
    i:=1; j:=n;
    while (i<j) do
      begin
        swap(aa[i],aa[j]);
        inc(i);dec(j);
      end;
  end;
function tinh(i,tr,sl : longint; big0, small :boolean) : int64;
  var j,tg : longint;
      dem : int64;
  begin
    if f[i,tr,sl,big0,small] > -1 then exit(f[i,tr,sl,big0,small]);
    if i>n then
      if (sl<=k) and (small)  then exit(1) else exit(0);
    dem := 0;
    if not small then
      begin
        for j := 0 to aa[i] do
          begin
            if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0;
            dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j<aa[i]));
          end;
      end
      else
      begin
        for j := 0 to 9 do
          begin
            if big0 then tg := sl + ord(abs(j-tr)<=d) else tg := 0;
            dem := dem + tinh(i+1,j,tg,big0 or (j>0),small or (j<aa[i]));
          end;
      end;
    f[i,tr,sl,big0,small] := dem;
    exit(dem);
  end;
begin
  assign(input,fi);reset(input);
  assigN(output,fo);rewrite(output);
 
  readln(a,b,d,k);
 
  chuanbi(a, n);
 
  fillchar(f,sizeof(f),255);
  tg1 := tinh(1,0,0,false,false);
 
  chuanbI(b+1, n);
 
  fillchar(f,sizeof(f),255);
  tg2 := tinh(1,0,0,false,false);
 
  writeln(tg2-tg1);
 
  close(input);close(output);
end.

C++

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
 
long long l, r, D, K, n;
long long f[20][10][20][2][2];
int a[20];
 
bool check(long long x)
{
    bool ans = 1;
    int top = 0;
    int tmp = x;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1);
    int dem = 0;
    FORE(i, 2, top) if (abs(a[i] - a[i - 1]) <= D) dem++;
    //if (x == 103) cout << dem<<" "<<K<<"??"<<endl;
    return (dem <= K);
}
 
long long trau()
{
    long long ans = 0;
    FORE(i, l, r) if (check(i)) ans++;
    cout << ans << endl;
    return 0;
}
long long duyet(int i, int dig, int worse, bool ok, bool greater0)
{
    if (i > n){
        return (worse <= K && greater0 > 0);
    }
    if (f[i][dig][worse][ok][greater0] > -1) return f[i][dig][worse][ok][greater0];
 
    long long ans = 0;
    if (i == 1){
        FORE(x, 0, a[i]) ans += duyet(i + 1, x, worse, ok | (x < a[i]), (x > 0));
    } else {
        int last = 9;
        if (ok == 0) last = a[i];
        int wnext;
        //if (i == 3) cout << last << "??"<<endl;
        FORE(x, 0, last) {
            if (greater0 == 0) wnext = worse; else wnext = worse + (abs(x - dig) <= D);
            //if (last == 3) cout << x<< ' '<<dig<<" "<<wnext<<endl;
            ans += duyet(i + 1, x, wnext, ok | (x < a[i]), greater0 | (x > 0));
        }
    }
    f[i][dig][worse][ok][greater0] = ans;
    return ans;
}
 
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("DEMSO.inp", "r", stdin);
    freopen("DEMSO.out", "w", stdout);
    #endif //MIKELHPDATKE
    cin >> l >> r >> D >> K;
    //trau();
 
    long long tmp = r, top = 0;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1); n = top;
    memset(f, -1, sizeof(f));
 
    long long ans = duyet(1, 0, 0, 0, 0);
   // cout << ans << endl;
 
    tmp = l - 1, top = 0;
    while (tmp){
        a[++top] = tmp % 10;
        tmp /= 10;
    }
    reverse(a + 1, a + top + 1); n = top;
    memset(f, -1, sizeof(f));
    if (l - 1 == 0) cout << ans;
    else{
        ans -= duyet(1, 0, 0, 0, 0);
        cout << ans;
    }
    //cout<<check(103)<<endl;
    return 0;
}

QBSEQ – SPOJ

Đề bài:

Thuật toán:

  • Gọi F[i][j] là độ dài dãy con dài nhất của dãy A[1..i] có tổng các phần tử chia k dư j.

Các bạn có thể tham khảo thuật toán chi tiết ở trang 162 quyển “Giải thuật và lập trình” của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=1000;
  maxk=50;
var
  f : array[0..maxn,0..maxk] of longint;
  a : array[1..maxn] of longint;
  i,j,n,k : longint;
procedure enter;
  begin
    assign(input,fI);reset(input);
    readln(n,k);
    for i:=1 to n do read(a[i]);
    close(input);
  end;
function calc ( x,y : longint) : longint;
  var tg : longint;
  begin
    tg := (x-y) mod k ;
    if tg<0 then tg := tg+k;
    exit(tg);
  end;
procedure solve;
  begin
    for i:=0 to n do
      for j:=0 to k-1 do
        f[i,j] := -maxn*maxn;
    f[0,0] := 0;
    for i:=1 to n do
      for j:=0 to k-1 do
        f[i,j] := max(f[i-1,j],f[i-1,calc(j,a[i])] +1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[n,0]);
    close(output);
  end;
begin
  enter;
  solve;
  print;
end.

LIQ và LIS sử dụng phương pháp quy hoạch động – SPOJ

Đề bài:

Thuật toán:

  • Gọi L[i] là độ dài dãy con tăng dài nhất bắt đầu bằng phần tử thứ i trong dãy
  • L[i] = L[j] + 1 với j=i+1..n và a[j] > a[i]
  • Sử dụng tìm kiếm nhị phân để tính nhanh mảng L[]

Bạn hãy tham khảo cụ thể thuật toán bài này ở trang 143 quyển “Giải thuật và lập trình” – thầy Lê Minh Hoàng. Theo mình đánh giá thì đây là thuật + code chi tiết nhất, rất phù hợp cho các bạn newbie. Nếu đã hiểu rồi thì code sẽ ngắn hơn thầy nhiều 🙂

Code:

program LongestSubSequence;
const
  InputFile  = 'INCSEQ.INP';
  OutputFile = 'INCSEQ.OUT';
const
  max = 5000;
var
  a, L, T, StartOf: array[0..max + 1] of Integer;
  n, m: Integer;
 
procedure Enter;
var
  i: Word;
  f: Text;
begin
  Assign(f, InputFile); Reset(f);
  ReadLn(f, n);
  for i := 1 to n do Read(f, a[i]);
  Close(f);
end;
 
procedure Init;
begin
  a[0] := -32768;
  a[n + 1] := 32767;
  m := 1;
  L[n + 1] := 1;
  StartOf[1] := n + 1;
end;
 
function Find(i: Integer): Integer;
var
  inf, sup, median, j: Integer;
begin
  inf := 1; sup := m + 1;
  repeat
    median := (inf + sup) div 2;
    j := StartOf[median];
    if a[j] > a[i] then inf := median
    else sup := median;
  until inf + 1 = sup;
  Find := StartOf[inf];
end;
 
procedure Optimize;
var
  i, j, k: Integer;
begin
  for i := n downto 0 do
    begin
      j := Find(i);
      k := L[j] + 1;
      if k > m then
        begin
          m := k;
          StartOf[k] := i;
        end
      else
        if a[StartOf[k]] < a[i] then
          StartOf[k] := i;
      L[i] := k;
      T[i] := j;
    end;
end;
 
procedure Result;
var
  f: Text;
  i: Integer;
begin
  Assign(f, OutputFile); Rewrite(f);
  Writeln(f, m - 2);
  i := T[0];
  while i <> n + 1 do
    begin
      Writeln(f, 'a[', i, '] = ', a[i]);
      i := T[i];
    end;
  Close(f);
end;
 
begin
  Enter;
  Init;
  Optimize;
  Result;
end.

LIQ và LIS sử dụng BIT – SPOJ

Đề bài:

Thuật toán:

  • Rời rạc hóa lại dãy
  • Gọi F[i] là độ dài dãy con tăng dài nhất kết thúc là số <= i
  • F[i] = max(F[1..a[i]-1] + 1)
  • Sử dụng cấu trúc dữ liệu BIT để tính mảng F trong O(logn)
  • ĐPT: O(nlogn)

Code:

using namespace std;
//#include<bits/stdc++.h>
#include <algorithm>
#include <stdio.h>
#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--)
 
int n, a[300010], T[300010], c[300010], f[300010], dem;
pair<int, int> b[300010];
 
int Get(int x)
{
    int ans = 0;
    if (x == 0) return 0;
    while (x > 0) {
        ans = max(ans, T[x]);
        x -= x & (-x);
    }
    return ans;
}
 
void Update(int x, int v)
{
    while (x <= n){
        T[x] = max(T[x], v);
        x += x & (-x);
    }
}
 
int main()
{
    //freopen("LIS.inp", "r", stdin);
    //freopen("LIS.out", "w", stdout);
    //cin>>n;
    scanf("%d", &n);
    FORE(i, 1, n) {
        //cin>>a[i];
        scanf("%d", &a[i]);
        b[i].first = a[i];
        b[i].second = i;
    }
 
    sort(b + 1, b + n + 1);
 
    int dem = 1; c[ b[1].second ] = dem;
    FORE(i, 2, n) {
        if (b[i].first > b[i - 1].first) dem++;
        c[ b[i].second ] = dem;
    }
    int ans = 0;
 
    FORE(i, 1, n) a[i] = c[i];
    //FORE(i, 1, n) cout<<a[i]<<" ";cout<<"=="<<endl;
    //cout<<"????"<<endl;
    FORE(i, 1, n) {
        f[i] = Get(a[i] - 1) + 1;
        Update(a[i], f[i]);
        ans = max(ans, f[i]);
    }
 
    //cout<<ans<<endl;
    printf("%d", ans);
    return 0;
}