Tài liệu chuyên đề thuật toán duyệt

January 14, 2017 by Leave a Comment

Tải về: CHUYEN-DE-DUYET-CAU-HINH-TO-HOP-YEULAPTRINH.PW

Hiện nay chưa có tài liệu chính thức dành cho lớp Chuyên Tin khối THPT. Mà chỉ tồn tại ở dưới dạng tên chuyên đề của Bộ Giáo dục gửi về cho các trường. Do vậy việc dạy và học gặp nhiều khó khăn trong việc thống nhất về nội dung cũng như mức độ về kiến thức chuyên môn. Nên việc nghiên cứu và xây dựng chuyên đề này là thực sự cần thiết.

Mục đích của chuyên đề là truyền tải một cách tổng quát, chi tiết và sự thống nhất về mặt nội dung để người đọc dễ hiểu và thấy được tầm quan trọng của bài toán liệt kê tổ hợp và một số bài tập ứng dụng trong Tin học dành cho học sinh chuyên tin ở trường THPT.

Nội dung của chuyên đề đã được các tác giả chọn lọc qua chương trình đã thực dạy tại trường và tham khảo của một số đồng nghiệp khác trong nước.

Kiến thức là vô hạn, trong chuyên đề này chúng tôi đã có gắng sáng  tạo, sưu tầm và trao đổi một cách tốt nhất có thể về mặt lý thuyết, các bài tập ứng dụng và các bài tập trong các kỳ thi trong nước để tạo thành cuốn tài liệu hiệu quả dành cho giáo viên và các em học sinh đam mê tin học chính thức làm tài liệu cho mình trong quá trình học tập và nghiên cứu.

THPT Chuyên Bắc Giang.

 

Chủ đề: Đệ quy, Tài liệu, Thuật toán

Thuật toán duyệt phân tập

August 21, 2016 by 1 Comment

Bài toán cơ bản: Cho mảng A[1..n] đếm số dãy con của mảng có tổng bằng S với n<=40.

  • Inp: n, S, mảng A.
  • Out: kết quả bài toán.

Inp:

4 4

1 2 3 4

Out:

2

Các dãy con: (4) , (1,3)

Phân tích: 

  • Thuật toán ta nghĩ ra ngay là duyệt dãy nhị phân 01
  • Nhưng duyệt chỉ giải quyết được với n <= 20. Chính vì vậy phải dùng thuật toán duyệt phân tập mới có thể ăn full test 🙂

Tư tưởng thuật toán duyệt phân tập:

  • Chia mảng A làm 2 mảng nhỏ độ dài n/2
  • Khi đó max(n/2)=20 => duyệt
  • Khi duyệt các mảng nhỏ ta lưu tổng các dãy con của mảng nhỏ vào các mảng riêng S1[] và S2[]
  • Với mỗi giá trị S1[] ta tìm kiếm nhị phần trong S2[] phần tử có giá trị S-S1[i] (cộng res với số gt S-S1[i] trong S2[]
  • res là kết quả bài toán

Các bài tập:

http://yeulaptrinh.de/312/coin34-spoj/
http://yeulaptrinh.de/673/vector-spoj/

Chủ đề: Duyệt phân tập, Tài liệu, Thuật toán

MATCH1 – SPOJ

May 11, 2016 by Leave a Comment

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

Thuật toán:

Code:

const
  fi='';
  fo='';
  maxn=100;
var
  a : array[1..maxn,1..maxn] of boolean;
  match : array[1..maxn] of longint;
  i,j,n,m,res : longint;
procedure enter;
  var u,v : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m);
    while not eof(input) do
      begin
        readln(u,v);
        a[u,v] := true;
      end;
  end;
procedure process;
  var found : boolean;
      nlist,i,j,old : longint;
      list : array[1..maxn] of longint;
      cx : array[1..maxn] of boolean;
  procedure dfs(u : longint);
    var i,v : longint;
    begin
      for v:=1 to m do
        if a[u,v] then
          if cx[v] then
          begin
            cx[v] := false;
            if match[v]=0 then found := true else dfs(match[v]);
            if found then
              begin
                match[v] := u;
                exit;
              end;
          end;
    end;
  begin
    nlist := n;
    for i:=1 to n do list[i ] := i;
    repeat
      old := nlist;
      fillchar(cx,sizeof(cx),true);
      for i:=nlist downto 1 do
        begin
          found := false;
          dfs(list[i]);
          if found then
            begin
              list[i] := list[nlist];
              dec(nlist);
            end;
        end;
    until old = nlist;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    for i:=1 to m do if match[i]<>0 then inc(res);
    writeln(res);
    for i:=1 to m do if match[i]<>0 then writeln(match[i],' ',i);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Chủ đề: Cặp ghép, SPOJ, Thuật toán Mức độ: ,

PBCGANGS – SPOJ

May 11, 2016 by Leave a Comment

Đề 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.
Chủ đề: DFS, Thuật toán Mức độ: , ,

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

May 2, 2016 by Leave a Comment

Đề 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.
Chủ đề: Phương pháp, Quy hoạch động, Thuật toán Mức độ: , , ,

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

May 2, 2016 by Leave a Comment

Đề 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
#include 
#include 
#define FOR(i,a,b) for (long long i=a;i=b; i--)

int n, a[300010], T[300010], c[300010], f[300010], dem;
pair 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<
Chủ đề: BIT, Cấu trúc dữ liệu, SPOJ, Thuật toán Mức độ: , , , ,

NKGOLF – SPOJ

April 29, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;

#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define DOW(i,a,b) for(int i = (a); i >= (b); i--)
#define RESET(c,val) memset(c,val,sizeof(c))
#define sz(a) int(a.size())
#define pb push_back

typedef long long ll;
typedef unsigned long long ull;

/*---------------------------*/

const int maxn = 1e3 + 2;
int m, n, res, tt;
ll a[maxn][maxn];
bool b[maxn][maxn];

void input() {
    scanf("%d %d", &m, &n);
    RESET(a,0);
    FOR(i,1,m)
    FOR(j,1,n)
    scanf("%lld", &a[i][j]);
}

void solve() {
    FOR(i,1,m-1)
    FOR(j,1,n-1)
    b[i][j]=((a[i][j]<=a[i+1][j]) && (a[i][j]<=a[i][j+1])
             && (a[i+1][j]<=a[i+1][j+1]) && (a[i][j+1]<=a[i+1][j+1]));

    res=1;
    // search row
    FOR(i,1,m) {
        tt=1;
        FOR(j,2,n)
        if ( a[i][j]>=a[i][j-1] ) {
            tt++;
            res=max(res,tt);
        } else tt=1;
    }

    // search col
    FOR(j,1,n) {
        tt=1;
        FOR(i,2,m)
        if ( a[i][j]>=a[i-1][j] ) {
            tt++;
            res=max(res,tt);
        } else tt=1;
    }

    int h[maxn], l[maxn], r[maxn];
    RESET(h,0);
    RESET(l,0);
    RESET(r,0);
    FOR(i,1,m-1) {
        FOR(j,1,n-1)
        if ( b[i][j] ) h[j]++;
        else h[j]=0;

        //deque
        int d[maxn];
        int top=0;
        d[0]=0;
        FOR(j,1,n-1) {
            while(top && h[j]<=h[d[top]])
                r[d[top--]]=j-1;
            l[j]=d[top]+1;
            d[++top]=j;
        }
        while(top) r[d[top--]]=n-1;

        FOR(j,1,n-1)
        if ( h[j]>0 ) {
            res=max(res,(h[j]+1)*(r[j]-l[j]+2));
        }
    }
}

void output() {
    printf("%d", res);
}

int main() {
    input();
    solve();
    output();

    return 0;
}
Chủ đề: SPOJ, Thuật toán Mức độ: ,

CTNOWN – SPOJ

April 29, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

uses    math;
const   fi='';
        fo='';
        maxn=350;
var     n,i,j   :longint;
        dem     :longint;
        nto     :array[1..maxn] of longint;
        cx      :array[1..maxn] of boolean;
        f       :array[0..maxn,0..maxn] of qword;
        t,tt,k    :longint;
        res,tam     :qword;
procedure sangnto;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxn)) do
                if cx[i]=false then
                        begin
                                j := i*i;
                                while (j<=maxn) do
                                        begin
                                                cx[j]:=true;
                                                j := j+i;
                                        end;
                        end;
        for i:=2 to maxn do
                if cx[i]=false then
                        begin
                                inc(dem);
                                nto[dem] := i;
                        end;
end;
function max(x,y : qword) : qword;
  var tg : qword;
  begin
    if x>y then exit(x) else exit(y);
  end;
procedure main;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
        sangnto;
        read(t);
                for i:=0 to dem do
                  for j:=0 to maxn do f[i,j] := 1;
                        for i:=1 to dem do
                                begin
                                        for j:=1 to maxn do
                                        begin
                                        f[i,j] := f[i-1,j];
                                        tam:=1;
                                        while tam*nto[i]<=j do
                                                begin
                                                        tam := tam * nto[i];
                                                        f[i,j] := max(f[i,j], f[i-1,j-tam]*tam );
                                                end;
                                        end;
                                end;
        for tt := 1 to t do
                begin
                        read(n);
                        writeln(f[dem,n]);
                end;
        close(input);close(output);
end;
procedure __;
begin
end;
begin
  __ ;
  main;
  __ ;
end.
Chủ đề: Quy hoạch động, SPOJ, Thuật toán Mức độ:

DHFRBUS – SPOJ

April 18, 2016 by Leave a Comment

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

Thuật toán:

  • Sử dụng thuật toán tìm đường đi ngắn nhất dijkstra.
  • Gọi d[u,x] là quãng đường ngắn nhất đi từ s đến u khi dùng x vé xe miến phí
  • Kết quả là d[t,k].

Code:

{$inline on}

const   fi      ='';
        fo      ='';
        maxN    =trunc(1e5)*2;
        maxM    =trunc(1e5)*10;
        maxK    =5;
        oo       =2*trunc(1e12);
type    Tadj    =record
                v,w,link:int64;
        end;

        THeap   =record
                v1,v2:int64;
        end;

        Arr1    =array[0..maxN] of int64;
        Arr2    =array[0..maxM] of Tadj;
        Arr4    =array[0..maxN*maxK] of THeap;
        Arr5    =array[0..maxN,0..maxK] of int64;

var     n, m, k :longint;
        Adj     :arr2;
        Head    :arr1;
        s, t    :longint;
        d       :arr5;
        Pos     :arr5;
        H       :arr4;
        nHeap   :longint;
        c       :longint;
//heapmin;
procedure hv(var a, b:int64);
var     tg      :int64;
begin
        tg:=a;a:=b;b:=tg;
end;

procedure UpHeap(i:longint);
begin

        if (i<=1) or (d[H[i div 2].v1,H[i div 2].v2]<=d[H[i].v1,H[i].v2]) then exit;
        hv(Pos[H[i div 2].v1,H[i div 2].v2],Pos[H[i].v1,H[i].v2]);
        hv(H[i div 2].v1,H[i].v1);
        hv(H[i div 2].v2,H[i].v2);
        UpHeap(i div 2);
end;

procedure DownHeap(i:longint);
var     j :longint;
begin
        j:=i*2;
        if j>nHeap then exit;
        if (j0 do
                begin
                        v:=adj[i].v;
                        w:=adj[i].w;
                        if d[v,x]>d[u,x]+w then
                        begin
                                d[v,x]:=d[u,x]+w;
                                Update(v,x);
                        end;
                        if (xd[u,x]) then
                        begin
                                d[v,x+1]:=d[u,x];
                                Update(v,x+1);
                        end;
                        i:=adj[i].link;
                end;
        until nHeap=0;
        ans:=oo;
        ans:=d[t,k];
        {for x:=0 to k do
                if d[t,x]
Chủ đề: Dijkstra, SPOJ, Thuật toán Mức độ: , , , ,

SPOJ – DHLOCK

April 18, 2016 by Leave a Comment

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

Thuật toán:

  • Bài này không quá khó. Ta chỉ cần duyệt số lần sử dụng cách biến đổi khóa thứ 2 là kk (kk=0..n-1,) với mỗi giá trị kk ta tính số lần ít nhất sử dụng phép biến đổi 1,3 để thỏa.

Code:

const   fi='';
        fo='';
        maxn=300;
var     i,j,n,k:longint;
        kiluc,kq,tam:longint;
        a,b,c:array[1..maxn] of longint;
procedure xuly;
var     kk:longint;
        tmp:longint;
begin
        for kk:=0 to n-1 do
        begin
            for i:=1 to n do
            begin
                if i+kk>n then tam:=(i+kk) mod n else tam:=i+kk;
                if b[tam]>=a[i] then c[i]:=b[tam]-a[i]
                        else c[i]:=b[tam]+k-a[i]+1;
            end;
            for i:=1 to n do
                begin
                    kq:=0;
                    tam:=c[i];
                    for j:=1 to n do
                        if c[j]>=tam then inc(kq,c[j]-tam)
                                else inc(kq,c[j]+k-tam+1);
                    if kq+kk+tam=a[i] then inc(kiluc,b[i]-a[i])
                else inc(kiluc,b[i]+k-a[i]+1);
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);

    readln(n,k);
    for i:=1 to n do read(a[i]);
    for j:=1 to n do read(b[j]);

    init;
    xuly;

    writeln(kiluc);

    close(input);close(output);
end.
Chủ đề: SPOJ, Thuật toán, Vét cạn Mức độ: , ,