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.

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