QMAX – spoj

October 25, 2016 by Leave a Comment

Đề 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.
Chủ đề: IT Mức độ:

NTSEQ – spoj

October 13, 2016 by Leave a Comment

Đề 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.de/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;
}
Chủ đề: BIT, Nén số (rời rạc hóa mảng) Mức độ:

MATCH1 – SPOJ

September 27, 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 Mức độ: ,