TRAKA – spoj

Đề bài:

Tóm tắt đề

Có N người thợ, M chiếc xe. Người thứ i hoàn thành việc sửa bộ phận xe mình phụ trách với tốc độ T[i]. Xe thứ j có độ rắc rối là F[j]. Thời gian người thứ i cửa xong bộ phận người i phụ trách trên xe j trong thời gian T[i] * F[j]. Các công việc được thực hiện theo thứ tự từ người 1 -> n. Người i làm việc liên tục ko đc dừng lại(tức là sửa xong xe i thì đến xe i + 1). Với mỗi thời điểm t, mỗi chiếc xe chỉ được sửa bởi tối đa 1 người. Tính thời điểm bé nhất để n người sửa xong m chiếc xe.

Dữ Liệu:

  • Dòng đầu gồm 2 số nguyên N (1 <= N <= 100 000) – số người thợ, M (1 <= M <= 100 000) – số chiếc xe cần sửa.
  • Dòng thứ i trong n dòng tiếp theo là T[i] – tốc độ sửa xong bộ phận người i phụ trách.
  • Dòng thứ j trong m dòng tiếp theo là F[j] – độ rắc rối của chiếc xe thứ j.

Kết quả:

  • Gồm 1 dòng là kết quả của bài toán.

Ví dụ:

Input:

3 3
2
1
1
2
1
1

Output:

11

Thuật toán:

Ở bài toán này thì thời điểm kết thúc công việc của người n là kết quả bài toán. Vì mỗi người thợ sẽ làm việc liên tục ko nghỉ nên ta cần tìm thời điểm bắt đầu thực hiện công việc của người n.
Gọi q[i] là tổng độ phức tạp của các chiếc xe từ 1 -> i.

Xét:
Người thứ u bắt đầu công việc từ thời điểm 0, tốc độ C. Thời điểm người u hoàn thành xe i là q[i] * C, hoàn thành xe i + 1 là q[i + 1] * c.
Người thứ v bắt đầu công việc ngay sau u, tốc độ D. Có thời điểm hoàn thành xe i là q[i] * D.
=> Để người v sửa xe i + 1 thì v cần chờ 1 khoảng thời gian là q[i + 1] * C – q[i] * D. Ta cần tìm min(q[i + 1] * C – q[i] * D).
Từ đây, ta để tính được thời điểm bắt đầu làm việc của người n là delta.
Kết quả bài toán là: delta + q[m] * t[n].

Nhận thấy độ phức tạp của thuật toán trâu bò là O(n * m) không đem lại thuật toán đủ tốt để giải bài toán. Nên ta cần tìm cách giảm độ phức tạp xuống.

Vậy, chúng ta nên làm thế nào ?? 😀 ??

Nhìn vào biểu thức q[i + 1] * C – q[i] * D có j đặc biệt ? Đây là biểu thức tích chéo của 2 vector (C; D) * (q[i]; q[i + 1]).

Coi (q[i]; q[i + 1]) là 1 điểm trên mặt phẳng tọa độ Oxy, và ta có vector u = (C; D).
Ta cần tìm điểm A(x, y) sao cho vector OA * u bé nhất. Nhận thấy điểm A cần tìm nằm trên đường lồi.

Trong hình vẽ bên dưới, đường thẳng màu xanh là đường lồi.

traka-yeulaptrinh.pw

Nhận thấy, các điểm trên đường lồi có tích chéo với (C; D) có giá trị theo hình parabol. Đến đây ta có thể áp dụng kĩ thuật chặt nhị phân hoặc tam phân để tìm đỉnh có tích chéo bé nhất.

Độ phức tạp là: O(m * log(n)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
typedef pair <long long, long long> ii;
 
const int N = 1e5 + 10;
 
int n, m, k;
ii A[N], p[N];
long long t[N];
 
ii operator - (ii a, ii b) { return  make_pair(b.first - a.first, b.second - a.second); }
long long operator * (ii a, ii b) { return a.first * b.second - a.second * b.first; }
 
bool cw(ii a, ii b, ii c) { return (b - a) * (c - b) < 0; }
 
void load() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &t[i]);
        t[i] += t[i - 1];
    }
    for (int i = 1; i <= n; ++i)
        A[i] = make_pair(t[i - 1], t[i]);
}
 
void findConvexLine() {
    k = 0;
    p[k++] = make_pair(0, 0);
    for (int i = 1; i <= n; ++i) {
        while (k > 1 && !cw(p[k - 2], p[k - 1], A[i])) k--;
        p[k++] = A[i];
    }
}
 
long long get(int x, int y) {
    //ii v = make_pair(x, y);
    int l = 0, r = k - 2, cur = 0;
    while (l <= r) { // (l - 1) * v <= 0 && (r + 1) * v > 0
        int mid = (l + r) >> 1;
        if ((p[mid + 1].first - p[mid].first) * y <= (p[mid + 1].second - p[mid].second) * x) {
            l = mid + 1;
            cur = l;
        } else {
            r = mid - 1;
        }
    }
    return make_pair(x, y) * p[cur];
}
 
void process() {
    findConvexLine();
    int x = 0, y = 0;
    long long delay = 0;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &y);
        delay += get(x, y);
      //  cerr << get(x, y) << "\n";
        x = y;
    }
    long long ans = delay + 1ll * t[n] * x;
    printf("%lld\n", ans);
}
 
int main() {
 
    load();
    process();
 
    return 0;
}

Tìm kiếm nhị phân (chặt nhị phân) toàn tập

Đã lâu rồi mình chưa viết bài mới, hôm nay mình xin chia sẻ với các bạn cách code thuật toán tìm kiếm phân mà mình thường sử dụng.

Chắc mọi người cũng biết, cùng một thuật toán tìm kiếm nhị phân nhưng có rất nhiều cách code khác nhau, tất cả đều chính xác, tốc độ nhanh như nhau. Và cách mình chia sẻ dưới đây là một trong những cách dễ hiểu nhất, linh hoạt nhất mà tốc độ chạy cũng khá tốt (cách này của anh Kiên – HCB Olympic Tin học Quốc tế)

Dãy con tăng – Tìm phần tử lớn nhất nhỏ hơn x (chỉ số lớn nhất)

// day con tang – tim phan tu lon nhat nho hon x ( chi so lon nhat);

function tim2(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>=x then c:=g else d:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto  d do

      if b[g]<x then exit(g);

   end;

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số bé nhất)

// day con tang – so be nhat lon hon hoac bang x (chi so be nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>=k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = left to right do

if a[i]>=k then return a[i];

print “Not found”

Dãy con tăng – Tìm số bé nhất lớn hơn hoặc bằng x (chỉ số lớn nhất)

// day con tang – so be nhat lon hon hoac bang x ( chi so lon nhat);

sort(a);

left=1, right=n;
i = (left + right) / 2;

while (left != i) and (i != right) do
    if a[i]>k then right = i;
    else left = i;
    i = (left + right) / 2;

for i = right to left do

if a[i]<=k then return a[i];

print “Not found”

Dãy con giảm – Tìm phần tử cuối cùng lớn hơn x

//day con giam – tim phan tu cuoi cung lon hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=c downto d do

      if b[g]>x then exit(g);

  end;

Dãy con giảm – Tìm phẩn tử đầu tiên nhỏ hơn x

//day con giam – tim phan tu dau tien nho hon x

function tim1(r,x : longint) : longint;

  var d,c,g : longint;

  begin

    d:=0;c:=r;

    g:=(d+c) div 2;

    while (g<>d) and (g<>c) do

      begin

        if b[g]>x then d:=g else c:=g;

        g:=(d+c) div 2;

      end;

    for g:=d to c do

      if b[g]>x then exit(g);

  end;

Các bài khác nhau với các yêu cầu tìm kiếm khác nhau bạn có thể dễ dàng sửa đổi cho phù hợp nếu sử dụng cách tìm kiếm nhị phân mình vừa trình bày.

Mọi thắc mắc rất mong nhận được từ quý bạn đọc <3

DTTUI1 – spoj

Đề bài:


Thuật toán:


  • Duyệt phân tập kết hợp Chặt nhị phân
  • Bạn có thể tham khảo thuật toán Duyệt phân tập tại đây

Code:


Program DTtui1;
CONST
        fin='';
        fon='';
        maxn=40;
        maxth=1048576;
Type
        Opt=Record
                kl,gt:longint;          //Khoi luong, Gia tri
        End;
        ToHop=array [1..maxth] of Opt;
Var
        o:array [1..2] of ToHop;
        dem:array [1..2] of longint;
        amax:array [1..maxth] of longint;
        w,v:array [1..maxn] of longint;   //Weight, Value
        m,i,j,sw,sv,sum:longint;
        n,mid:byte;
        f:text;
//--------------------------------------------------
        Procedure Nhap;
        Var i:byte;
        Begin
                Assign(f,fin);
                Reset(f);
                Readln(f,n,m);
                For i:=1 to n do
                        Readln(f,w[i],v[i]);
                Close(f);
        ENd;
        //------------------------------------------
 
                Procedure Sort(l,r:longint);
                Var i,j,x:longint;
                        y:Opt;
                Begin
                        i:=l;
                        j:=r;
                        x:=o[2,l+random(r-l+1)].kl;
                        Repeat
                                While o[2,i].kl<x Do inc(i);
                                While o[2,j].kl>x do dec(j);
                                If not(i>j) Then
                                        Begin
                                        y:=o[2,i];
                                        o[2,i]:=o[2,j];
                                        o[2,j]:=y;
                                        inc(i);
                                        dec(j);
                                        ENd;
                        Until i>j;
                        If i<r Then sort(i,r);
                        If l<j Then sort(l,j);
                End;
        //-----------------------------------------
        Procedure Luu(x:byte);
        Var k:longint;
        Begin
                inc(dem[x]);
                k:=dem[x];
                o[x,k].kl:=sw;
                o[x,k].gt:=sv;
        End;
        //----------------------------------------
        Procedure Duyet(bit,i,k:byte);
        Var j:byte;
        Begin
                If sw>m Then Exit;
                For j:=0 to 1 do
                        Begin
                        sw:=sw+j*w[i];
                        sv:=sv+j*v[i];
                        If i=k Then
                                Begin
                                If sw<=m Then Luu(bit);
                                End
                        else Duyet(bit,i+1,k);
                        sw:=sw-j*w[i];
                        sv:=sv-j*v[i];
                        End;
        End;
        //-------------------------------------
        Procedure CheckMax;
        Var i,max:longint;
        Begin
                amax[1]:=1;
                max:=1;
                For i:=2 to dem[2] do
                        Begin
                        If o[2,i].gt>o[2,max].gt Then max:=i;
                        amax[i]:=max;
                        End;
        End;
        //-----------------------------------
        Function Find(bit:byte; x:longint):longint;
        Var dau,giua,cuoi:longint;
        Begin
                dau:=1;
                cuoi:=dem[bit]+1;
                Repeat
                        giua:=(dau+cuoi) div 2;
                        If o[bit,giua].kl <= x Then dau:=giua
                        else cuoi:=giua;
                Until dau+1=cuoi;
                Exit(dau);
        End;
        //------------------------------------
        Procedure Xuat;
        Begin
                Assign(f,fon);
                Rewrite(f);
                Writeln(f,sum);
                Close(f);
        End;
Begin
        Randomize;
        Nhap;
        mid:=n div 2;
        Duyet(1,1,mid);
        Duyet(2,mid+1,n);
        sort(1,dem[2]);
        CheckMax;
 
        For i:=1 to dem[1] do
                Begin
                j:=Find(2,m-o[1,i].kl);
                If o[1,i].gt + o[2,amax[j]].gt > sum Then sum:=o[1,i].gt + o[2,amax[j]].gt;
                End;
        Xuat;
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.

NKSGAME – spoj

Đề bài:

Thuật toán:

Bài yêu cầu với mỗi số \(b[i]\) tìm \(c[j]\) sao cho \(|b[i]+c[j]|\) nhỏ nhất. Suy ra chọn sao cho \(b[i]+c[j]\) có giá trị gần \(0\) nhất

Thuật toán sẽ là:

  1. Sắp xếp lại mảng \(c[]\).
  2. Với mỗi \(b[i]\) tìm kiếm nhị phân \(c[j]\) thỏa mãn \(b[i]+c[j]\) có giá trị gần \(0\) nhất.

Nếu chưa hiểu rõ bạn có thể xem code bên dưới.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 100009;
const int oo = 2000000009;
int i, j, n, ans, tmp, b[maxn], a[maxn];
 
bool cmp (int x, int y) {
     return(x < y);
}
 
int main() {
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];
    for (i = 1; i <= n; i++) cin >> b[i];
    sort (b+1, b+n+1, cmp);
    ans = oo;
    for (i = 1; i <= n; i++) {
        tmp = lower_bound(b+1,b+n+1,0-a[i]) - b;
        if (tmp > n) tmp = n;
        ans = min(ans, abs(a[i] + b[tmp]));
        if (tmp == 1) continue;
        ans = min(ans, abs(a[i] + b[tmp-1]));
    }
    cout << ans;
    return 0;
}

NKJUMP – spoj

Đề bài: [xem đề bài]

Thuật toán:

  • Nhận thấy một vòng bất kỳ chỉ có thể nhảy đến vòng có số lớn hơn. Ta nghĩ đến sử dụng phương pháp Quy hoạch động để giải.
  • Ban đầu sắp xếp lại mảng A.
  • Gọi F[i] là số bước lớn nhất để nhảy đến ô thứ i.
  • F[i] = max(F[j]+1, F[i]) với i=1..n, j=1..i-1 và tồn tại k sao cho a[k]+a[j]=a[i].
  • Kiểm tra xem có tồn tại k bằng cách sử dụng tìm kiếm nhị phân

Code:

C++ (xem code trên ideone)

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 1009;
int i, j, n, a[maxn], b[maxn], f[maxn];
 
int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    int tmp, ans = 0;
    for (int i = 1; i <= n; i++) f[i] = 1;
    for (int i = 3; i <= n; i++) {
        for (int j = 1; j < i; j++) {
            bool tmp = binary_search(a+1,a+j,a[i] - a[j]);
            if (tmp == 1) {
                f[i] = max(f[i], f[j] + 1);
            }
        }
        ans = max(ans, f[i]);
    }
    cout << ans << endl;
    return 0;
}

Pascal (xem code trên ideone)

uses    math;
const   fi='';
        fo='';
        maxn=1000;
type    arra=array[1..maxn] of longint;
var     f:text;
        a,l:arra;
        i,j,n:integer;
        tmp2:longint;
        res:longint;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do
    begin
        read(f,a[i]);
    end;
    close(f);
end;
procedure sort;
var     w:longint;
begin
    for i:=1 to n do
        for j:=i+1 to n do
        if a[i]>a[j] then
        begin
            w:=a[i];
            a[i]:=a[j];
            a[j]:=w;
        end;
end;
procedure init;
begin
    res:=0;
    for i:=1 to n do l[i]:=1;
end;
function kt(x,k:longint):boolean;
var     d,c,g,ii:longint;
begin
    d:=1; c:=k;
    kt:=false;
    while d<=c do
    begin
        g:=(d+c) div 2;
        if a[g]=x then begin tmp2:=g; exit(true); end;
        if a[g]<x then d:=g+1 else c:=g-1;
    end;
end;
function max3(x,y,z:longint):longint;
begin
    max3:=x;
    if y>max3 then max3:=y;
    if z>max3 then max3:=z;
end;
procedure xuly;
var     tmp:longint;
begin
    for i:=1 to n do
    begin
        tmp:=a[i];
        for j:=i-1 downto 1 do
        begin
            if a[j]>=tmp div 2 then
                begin
                   if kt(tmp-a[j],j-1) then
                        begin
                        l[i]:=max3(l[i],l[j]+1,l[tmp2]+1);
                        if l[i]>res then res:=l[i];
                        end;
                end
            else break;
        end;
    end;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    sort;
    init;
    xuly;
    xuat;
end.

BLGEN – spoj

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

Thuật toán:

  • (đang cập nhập)

Code:

uses math;
const   fi      ='';
        fo      ='';
        oo      =1000;
        maxc    =trunc(3e6);
var     n       :array[1..2] of longint;
        a       :array[1..2,1..1000] of qword;
        f       :array[0..oo,0..oo] of longint;
        mp      :longint;
        g       :array[1..maxc] of longint;
        nto     :Array[1..300000] of qword;
procedure nhap;
var     i :longint;
        k :longint;
        p :qword;
begin
        assign(input,fi);
        reset(input);
                k:=0;
                while not seekeof() do
                begin
                        inc(k);
                        while not seekeoln() do
                        begin
                                inc(n[k]);
                                read(p);
                                a[k,n[k]]:=p;
                        end;
                        readln;
                end;
        close(input);
end;
procedure sang;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxc)) do
        if g[i]=0 then
        begin
                j:=i*I;
                while j<=maxc do
                begin
                        g[j]:=i;
                        inc(j,i);
                end;
        end;
        for i:=2 to maxc do
        if g[i]=0 then
        begin
                inc(mp);
                nto[mp]:=i;
        end;
end;
function find(x:qword):boolean;
var     d,c,mid   :longint;
        t1,t2,t3      :qword;
begin
        d:=1; c:=mp;
        while d<=c do
        begin
                mid:=(d+c) div 2;
                t1:=x mod nto[mid];
                t2:=x div nto[mid];
                t3:=nto[mid]*nto[mid];
                if (t1=0) and (t2=t3) then exit(true);
                if (t3>t2) then c:=mid-1
                else d:=mid+1;
        end;
        exit(false);
end;
function kt(x:qword):boolean;
var     x1      :qword;
begin
        x1:=trunc(sqrt(x));
        if x1*x1=x then exit(true);
        if find(x) then exit(true);
        exit(false);
end;
procedure xuli;
var     i,j     :longint;
begin
        for i:=1 to n[1] do
        for j:=1 to n[2] do
        if (a[1,i]=a[2,j]) and kt(a[1,i]) then f[i,j]:=f[i-1,j-1]+1
        else f[i,j]:=max(f[i-1,j],f[i,j-1]);
end;
procedure xuat;
begin
        assign(output,fo);
        rewrite(output);
                writeln(f[n[1],n[2]]);
        close(Output);
end;
begin
        nhap;
        sang;
        xuli;
        xuat;
end.