CASTLE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập thuật toán)

Code:

uses math;
const
    tfi='';//castle.inp';
    tfo='';//castle.out';
 
var
    fi,fo:text;
    n,top1,top2,top3,dem:longint;
    tg,kq1,kq2,kq11,kq22:int64;
    p,q,a,b:array[0..5001] of longint;
    st:array[0..5001] of int64;
procedure nhap;
    var i,j:longint;
    begin
        read(fi,n);
        for i:=1 to n do read(fi,a[i],b[i]);
        kq2:=high(int64);
    end;
 
procedure swap(var x,y:longint);
    var tg:longint;
    begin
        tg:=x;
        x:=y;
        y:=tg;
    end;
 
procedure sort(l,r:longint);
    var i,j,k,k1,k2:longint;
    begin
        i:=l;
        j:=r;
        k:=l+random(r-l+1);
        k1:=a[k];
        k2:=b[k];
        repeat
            while (a[i]<k1) or ((a[i]=k1) and (b[i]<k2)) do inc(i);
            while (a[j]>k1) or ((a[j]=k1) and (b[j]>k2)) do dec(j);
            if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    inc(I);
                    dec(j);
                end;
        until i>j;
        if i<r then sort(i,r);
        if l<j then sort(l,j);
    end;
 
procedure lam(u,v:int64);
    var i,j:longint;
    begin
        top3:=0;
        j:=1;
        for i:=1 to top1 do
            begin
                while (j<=top2)and ( p[j]<=q[i]) do
                    begin
                        if p[j]=q[i] then
                            begin
                                inc(top3);
                                st[top3]:=p[j];
                            end;
                        inc(j);
                    end;
            end;
        dem:=dem+int64(top3)*(top3-1) DIV 2;
        if top3>=2 then
        begin
        tg:=int64(st[top3]-st[1])*(v-u);
        if tg=kq1 then inc(kq11);
        if tg>kq1 then
            begin
                kq1:=tg;
                kq11:=1;
            end;
        end;
        for i:=2 to top3 do
            begin
                tg:=int64(st[i]-st[i-1])*(v-u);
                if tg=kq2 then inc(kq22);
                if tg<kq2 then
                    begin
                        kq2:=tg;
                        kq22:=1;
                    end;
            end;
    end;
 
procedure xuli;
    var i,j,k,k1:longint;
    begin
        sort(1,n);
        i:=1;
        a[n+1]:=-maxlongint;
        while i<n do
            begin
                top1:=0;
                for j:=i to n+1 do
                    if a[j]<>a[i] then break
                    else
                        begin
                            inc(top1);
                            q[top1]:=b[j];
                        end;
                if j>n then break;
                k:=j;
                while k<=n do
                    begin
                        top2:=0;
                        for k1:=k to n+1 do
                            if a[k1]<>a[k] then break
                            else
                                begin
                                    inc(top2);
                                    p[top2]:=b[k1];
                                end;
                        lam(a[i],a[k]);
                        k:=k1;
                    end;
                i:=j;
            end;
        writeln(fo,dem);
        if dem>0 then
            begin
                writeln(fo,kq1,' ',kq11);
                writeln(fo,kq2,' ',kq22);
            end;
    end;
 
begin
    assign(fi,tfi);
    assign(fo,tfo);
    reset(fi);
    rewrite(fo);
    nhap;
    xuli;
    close(fo);
end.

PVOI14_4 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

Uses    math;
const   fi      ='';
        fo      ='';
        maxN    =5*trunc(1e4)+1;
 
type    arr1    =array[0..maxN] of longint;
        arr2    =array[0..maxN,1..4] of longint;
 
var     n       :longint;
        a       :arr1;
        T       :arr2;
        cs      :arr1;
        f       :arr2;
procedure QS(var a,cs:arr1;l,r:longint);
var     i,j,x,tg        :longint;
begin
        i:=l;j:=r;
        x:=a[l+random(r-l+1)];
        repeat
                while a[i]<x do inc(i);
                while a[j]>x do dec(j);
                if i<=j then
                begin
                        tg:=a[i];a[i]:=a[j];a[j]:=tg;
                        tg:=cs[i];cs[i]:=cs[j];cs[j]:=tg;
                        inc(i);
                        dec(j);
                end;
        until i>j;
        if l<j then QS(a,cs,l,j);
        if i<r then QS(a,cs,i,r);
end;
 
Procedure Update(x,k,v:longint);
begin
        while x<=maxN do
        begin
                T[x,k]:=max(T[x,k],v);
                x:=x+x and (-x);
        end;
end;
 
function Get(x,k:longint):longint;
begin
        Get:=0;
        while x>0 do
        begin
                Get:=Max(Get,t[x,k]);
                x:=x-x and (-x);
        end;
end;
 
procedure xuly;
var     i, j    :longint;
        a2 :arr1;
        dem     :longint;
        max_h   :longint;
        tmp     :longint;
        ans     :longint;
begin
        for i:=1 to n do a2[i]:=a[i];
        fillchar(t,sizeof(t),0);
        QS(a2,cs,1,n);
        dem:=1;
        a[cs[1]]:=dem;
        for i:=2 to n do
                begin
                        if a2[i]>a2[i-1] then inc(dem);
                        a[cs[i]]:=dem;
                end;
        //for i:=1 to n do write(a2[i],' ');writeln;
        max_h:=dem;
        ///// 1
        for i:=1 to n do
                begin
                        f[i,1]:=Get(a[i]-1,1)+1;
                        Update(a[i],1,f[i,1]);
                end;
        ///2
        for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],2)+1;
                        if tmp<=2 then tmp:=0;
                        begin
                                f[i,2]:=tmp;
                                Update(max_h-a[i]+1,2,max(f[i,1],f[i,2]));
                        end;
                end;
       // writeln(f[5,2]);
        ///3
         for i:=1 to n do
                begin
                        tmp:=Get(a[i]-1,3)+1;
                        if tmp<=3 then tmp:=0;
 
                        begin
                                f[i,3]:=tmp;
                                Update(a[i],3,max(f[i,2],f[i,3]));
                        end;
                end;
         //writeln(f[11,3]);
         //4
          for i:=1 to n do
                begin
                        tmp:=Get(max_h-a[i],4)+1;
                        if tmp<=4 then tmp:=0;
 
                        begin
                                f[i,4]:=tmp;
                                Update(max_h-a[i]+1,4,max(f[i,3],f[i,4]));
                        end;
                end;
         // writeln(f[14,4]);
          ans:=0;
          for i:=1 to n do ans:=max(ans,f[i,4]);
          writeln(ans);
end;
procedure run;
var     i :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                begin
                        read(a[i]);
                        cs[i]:=i;
                end;
        xuly;
        close(input);close(output);
end;
 
begin
        run;
end.

QMAX – spoj

Đề bài:

Thuật toán:

it - yeulaptrinh.pw

  • Đây là bài thuần sử dụng cấu trúc dữ liệu IT. Các bạn có thể tham khảo thêm tại: http://adf.ly/1f54AI

Code:

uses    math;
const   fi='';
        fo='';
        maxn=100000;
        oo      =2*trunc(1e10);
var     a       :array[0..maxn] of int64;
        i,j,n,p,q,m :longint;
        t       :array[1..4*maxn] of int64;
        res     :int64;
procedure enter;
var     u,v,k   :longint;
begin
        readln(n,m);
        for i:=1 to m do
                begin
                        read(u,v,k);
                        a[u] := a[u]+ k;
                        a[v+1] := a[v+1] -k;
                end;
        for i:=1 to n do
                a[i] := a[i-1] +a[i];
end;
procedure update(k,l,r:longint);
var     m :longint;
begin
        if l=r then
                begin
                        t[k] := a[l];
                        exit;
                end;
        m := (l+r) div 2;
        update(k*2,l,m);
        update(k*2+1,m+1,r);
        t[k] := max(t[k*2],t[k*2+1]);
end;
procedure find(k,l,r,i,j:longint);
var     m :longint;
begin
	if (i>r) or (j<l) then exit;
        if (i<=l) and (r<=j) then
                begin
                        res := max(t[k],res);
                        exit;
                end;
        m := (l+r) div 2;
        find(k*2,l,m,i,j);
        find(k*2+1,m+1,r,i,j);
end;
procedure process;
begin
        update(1,1,n);
end;
procedure print;
var     u,v     :longint;
	i	:longint;
begin
        read(q);
        for i:=1 to q do
          begin
                read(u,v);
                res := -oo;
                find(1,1,n,u,v);
                writeln(res);
          end;
end;
begin
assign(input,fi);reset(input);
assign(output,fo);rewrite(output);
        enter;
        process;
        print;
close(input);close(output);
end.

NTSEQ – spoj

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

Thuật toán:

  • Rời rạc hóa rồi sử dụng cấu trúc dữ liệu BIT để tính
  • Các bạn mới học cần phải làm bài này trước mới hiểu rõ được: http://yeulaptrinh.pw/102/lis-va-liq-su-dung-bit-spoj/
  • Mỗi nút của cây BIT lưu 2 giá trị là số lượng và độ dài dãy con dài nhất
  • Đọc code các bạn có thể hiểu ngay được

Code:

using namespace std;
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e5;
const int INF = 1e9 + 7;
 
int n, a[MAXN], b[MAXN], __max = 0;
int f[MAXN];
 
struct data{
    int val, sl;
} T[MAXN];
 
void add(int &a, int b)
{
    a += b;
    if (a > INF) a -= INF;
}
 
data get(int x)
{
    data ans; ans.val = 0; ans.sl = 0;
    for(int i = x; i > 0; i -= i & -i) {
        if (ans.val < T[i].val) ans = T[i];
        else if (ans.val == T[i].val) add(ans.sl, T[i].sl);
    }
    return ans;
}
 
void update(int x, int val, int sl)
{
    for(int i = x; i <= __max + 1; i += i & -i){
        if (val > T[i].val) T[i].val = val, T[i].sl = sl;
        else {
                if (val == T[i].val) add(T[i].sl, sl);
        }
    }
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
    cin >> n;
    FORE(i, 1, n) cin >> a[i];
    FORE(i, 1, n) b[i] = a[i]; sort(b + 1, b + n + 1);
    FORE(i, 1, n) a[i] = lower_bound(b + 1, b + n + 1, a[i]) - b;
    __max = *max_element(a + 1, a + n + 1);
    a[n + 1] = __max + 1;
    FORE(i, 1, n + 1){
        data tmp = get(a[i] - 1);
        f[i] = tmp.val + 1;
        if (tmp.sl == 0) tmp.sl++;
        if (i == n + 1) cout<<tmp.sl<<endl;
        update(a[i], f[i], tmp.sl);
    }
	return 0;
}

MPILOT – SPOJ

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

Thuật toán:

  • Đây là bài tập về thuật toán Heap cơ bản
  • Ta đưa yêu cầu bài toán thành chọn các lái phụ có chênh lệch giữa lương lái chính và lương lái phụ là lớn nhất mà vẫn đảm bảo yêu cầu có thể ghép được n/2 cặp mà tuổi lái phụ < lái chính
  • Heap sẽ lưu độ chênh lệch giữa lương lái phục và chính của mọi người
  • Duyệt i=1..n, đẩy i vào, nếu i lẻ thì lấy ở heap ra 1 thằng làm lại phụ
  • Các bạn hãy đọc code để rõ hơn

Code: [xem code]

const   fi='';
        fo='';
        maxn=10000+3;
var     p,h:array[1..maxn] of longint;
        i,j,n,res,sum:longint;
        a,c:array[1..maxn] of longint;
        nh:longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do read(a[i],c[i]);
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
function tinh(x:longint):longint;
begin
        exit(a[x]-c[x]);
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and ( tinh(h[j+1]) > tinh(h[j]) ) then inc(j);
        if tinh(h[i]) < tinh(h[j]) 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 tinh(h[i]) > tinh(h[j]) then
                begin
                        swap(h[i],h[j]);
                        upheap(j);
                end;
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        dec(nh);
        downheap(1);
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        upheap(nh);
end;
procedure process;
begin
        for i:=1 to n do
                begin
                        inc(sum,a[i]);
                        push(i);
                        if i mod 2 = 1 then inc(res,tinh(pop) );
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(sum-res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C11SEQ – spoj

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

Thuật toán:

  • Gọi S[i] là tổng từ a[1] đến a[i]
  • Ta biến đổi yêu cầu đề bài
    • <span class="coMULTI">L &lt;= a[i] + a[i+1] + ... + a[j] &lt;= R</span>
    • <span class="coMULTI">=&gt;    L&lt;=s[i] - s[j-1]&lt;=R</span>
    • =>        s[j-1]>=s[i]-r;
                   s[j-1]<=s[i]-l;
  • Lưu các giá trị s[i] – r và s[i] – l và mảng kt 2*n ——> rời rạc hóa thành mảng b[1..2*n] ——> lưa vào cây BIT để tính:
    <span class="st0">ans := ans + get(b[i]) - get(b[n+i]);</span>

Code:

const
  fi='';//c11seq.inp';
  fo='';//c11seq.out';
  maxn=trunc(1e5);
var
  s,sr,sl : array[0..maxn] of int64;
  a  : array[0..maxn*3] of int64;
  b,cs,t  : array[0..maxn*3] of longint;
  i,j,n,l,r : longint;
  ans : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    read(n,l,r);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do if (l<=a[i]) and (r>=a[i]) then inc(ans);
    close(input);
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg := x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint);
  var i,j : longint;
      x : int64;
  begin
    i :=l;j:=r;
    x := a[cs[(l+r) div 2]];
    repeat
      while a[cs[i]]<x do inc(i);
      while a[cs[j]]>x do dec(j);
      if i<=j then
        begin
          swap(cs[i],cs[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 init;
  var i,hold : longint;
  begin
    for i := 1 to n do s[i] := s[i-1] + a[i];
    for i := 1 to n do sl[i] := s[i] - l;
    for i := 1 to n do sr[i] := s[i] - r - 1;
    for i := 1 to n do
      begin
        a[i] := sl[i];
        a[n+i] := sr[i];
        a[n+n+i] := s[i-1];
      end;
    //a[2*n+1] := s[0] - l;
    //a[2*n+2] := s[0] - r;
    for i:=1 to 3*n do cs[i] := i;
    qs(1,3*n);
    b[cs[1]] := 1; hold := 1;
    for i:=2 to n*3 do
      if a[cs[i]] = a[cs[i-1]] then
        begin
          b[cs[i]] := hold;
        end
        else
        begin
          inc(hold);
          b[cs[i]] := hold;
        end;
  end;
procedure update(i : longint);
  begin
    while i<=3*n do
      begin
        t[i] := t[i] + 1;
        i := i + i and (-i);
      end;
  end;
function get(i : longint) : longint;
  begin
    get := 0;
    while i>0 do
      begin
        get := get + t[i];
        i := i - i and (-i);
      end;
  end;
procedure process;
  var i : longint;
  begin
    for i:=1 to n do
      begin
        ans := ans + get(b[i]) - get(b[n+i]);
        update(b[2*n+i]);
      end;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(Output);
    writeln(ans);
    close(output);
  end;
begin
  enter;
  init;
  process;
  print;
end.

SUBSTR – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi='';
  fo='';
  maxn=trunc(1e6);
  base=trunc(1e9)+7;
  pp=307;
var
  f : array[0..maxn] of int64;
  i,j,n,m : longint;
  hb : int64;
  a,b : array[1..maxn] of byte;
  ha,pow : array[0..maxn] of int64;
procedure enter;
var x : ansistring;
begin
  assign(input,fi);reset(input);
  readln(x);
  m := length(x);
  for i := 1 to m do a[i] := ord(x[i])-48;
  readln(x);
  n := length(x);
  for i := 1 to n do b[i] := ord(x[i])-48;
  close(input);
end;
function gethash(l,r : longint) : int64;
begin
  gethash := (ha[r]-ha[l-1]*pow[r-l+1] + base*base) mod base;
end;
procedure process;
begin
  assign(output,fo);rewrite(output);
  ha[0] := 0;
  for i:=1 to m do ha[i] := (ha[i-1]*pp + a[i]) mod base;
  pow[0] := 1;
  for i:=1 to m do pow[i] := pow[i-1]*pp mod base;
  hb := 0;
  for i:=1 to n do hb := (hb*pp + b[i]) mod base;
  for i:=1 to m-n+1 do
    if hb = gethash(i,i+n-1) then
      write(i,' ');
  close(output);
end;
begin
  enter;
  process;
end.