Hello world!

January 19, 2026 by Leave a Comment

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!

Chủ đề: Uncategorized

Hello world!

January 16, 2026 by 1 Comment

Welcome to WordPress. This is your first post. Edit or delete it, then start writing!

Chủ đề: Uncategorized

STABLE – spoj

August 15, 2017 by Leave a Comment

Đề bài:

Thuật toán:

  • BFS từ đỉnh S
  • Gọi bac[i] là đồ dài đường đi ngắn nhất từ s đến i
    • bac[i] = bac[j] + 1
    • với i kề j và j duyệt BFS trước i
  • ok[i] = 1 nếu i ổn định, ok[i] = 0 nếu i không ổn định.
  • Hãy tham khảo code để biết cách kiểm tra xem i có ổn định không

Code:

#include 
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair 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;}
const int MAXN = 1E4+3;
const int oo = 1e9+3;

int n, m, s, u, v, res, bac[MAXN],adj[MAXN][MAXN];
bool ok[MAXN];
queue q;
vector a[MAXN];

int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    cin >> n >> m >> s;
    FOR(i,1,m) {
        cin >> u >> v;
        if (!adj[u][v])
            a[u].push_back(v);
        adj[u][v] = 1;
    }
    q.push(s); bac[s] = 1;
    while (!q.empty()) {
        u = q.front();
        q.pop();
        for(int i=0; i

const
  fi='stable.inp';
  fo='stable.out';
  maxn=10000;
  maxm=50000;
var
  link,head,ke : array[1..maxm] of longint;
  i,j,n,m,st,ans,s,dau,cuoi,u,v : longint;
  q,bac : array[1..maxn] of longint;
  ok : array[1..maxn] of boolean;
  a : array[1..maxn,1..maxn] of boolean;
procedure push(x : longint);
  begin
    inc(cuoi);
    q[cuoi] := x;
  end;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
begin
//  assign(input,fi);reset(input);
//  assign(output,fo);rewrite(output);
  read(n,m,s);
  for i := 1 to m do
    begin
      read(u,v);
      if a[u,v] = false then
      add(i,u,v);
      a[u,v] := true;
    end;
  dau := 1; cuoi := 0;
  push(s);
  bac[s] := 1;
  while (dau <= cuoi) do
    begin
      u := q[dau];
      inc(dau);
      i := head[u];
      while i <> 0 do
        begin
          v := ke[i];
          if bac[v] = 0 then
            begin
              if ok[u] then ok[v] := true;
              bac[v] := bac[u] + 1;
              push(v);
            end
            else
          if bac[v] = bac[u] + 1 then
            begin
              ok[v] := true;
            end;
          i := link[i];
        end;
    end;
  for i := 1 to n do
    if ok[i] then inc(ans);
  writeln(ans);
//  close(input);close(output);
end.
Chủ đề: BFS, Đồ thị, SPOJ Mức độ:

listgame – kattis

August 15, 2017 by Leave a Comment

[mathjax]
[su_accordion][su_accordion]
[su_spoiler title=”Đề bài” open=”yes”]
Có hai người chơi trò chơi với nhau, luật như sau:

  • Người thứ nhất chọn một số nguyên dương X
  • Người thứ hai tìm các số $Y_1, Y_2, .. Y_k$ sao cho $(Y_1 + 1)(Y_2 + 1)…(Y_k + 1) = X$. Khi đó người chới thứ hai được k điểm

Cho X tìm số điểm tối đa mà người chơi thứ hai có thể đạt

Input:

Số nguyên dương $X$ thỏa mãn $10^3 <= X <= 10^9$

Output:

Duy nhất số K là số điểm tối đa có thể đạt

Sample Input 1 65536
Sample Output 1 16

 

Sample Input 2 127381
Sample Output 2 3

[/su_spoiler]
[su_spoiler title=”Thuật toán”]

  • Nếu n là số nguyên tố => Kết quả: 1
  • Nếu không thì ta phần tích X thành tích các số nguyên tố => Kết quả: là số các số hạng phân tích được

    • Ví dụ: 12 = 2 * 2 * 3 => Kết quả: 3

[/su_spoiler]
[su_spoiler title=”Code”]

#include 
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair 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;}
const int MAXN = 1E6+3;
const int oo = 1e6+3;

bool prime[MAXN];
int i, j, x, cnt, k, sl[MAXN], nt[MAXN];

void tim_snt() {
    prime[1] = 1;
    int n = trunc(sqrt(oo));
    for(i=2; i<=n; i++) {
        if (!prime[i]) {
            j = i*i;
            while (j <= oo) {
                prime[j] = 1;
                j += i;
            }
        }
    }
    cnt = 0;
    for(i=2; i<=oo; i++) if (!prime[i]) {
        cnt++;
        nt[cnt] = i;
    }
}

void phan_tich() {
    int i = 1;
    while (x > 1) {
        while ((x > 1)&&(x % nt[i] == 0))
        {
            k++;
            x /= nt[i];
        }
        i++;
        if (i > cnt) break;
    }
    if (x > 1) k++;
}

bool ktnt(int x) {
    int n = trunc(sqrt(x));
    FOR(i,2,n) {
        if (x % i == 0) return 0;
    }
    return 1;
}

int main() {
    cin >> x;
    if (ktnt(x)) {
        cout << 1;
        return 0;
    }
    tim_snt();
    phan_tich();
    cout << k;
    return 0;
}

[/su_spoiler]
[/su_accordion]

Chủ đề: Kattis, Sàng nguyên tố, Toán học Mức độ:

APIO10A – spoj

August 14, 2017 by Leave a Comment

Đề bài: http://www.spoj.com/problems/APIO10A/

Cho 1 dãy N số nguyên. Một hàm số bậc 2 : f(x) = a * x ^ 2 + b * x + c. Phân dãy trên thành các đoạn liên tiếp sao cho tổng các hàm f trên các dãy là lớn nhất (giá trị f của 1 dãy là f(x) với x là tổng của dãy đó).

Input format :

  • Dòng đầu là số test case T
  • Mỗi test case gồm 3 dòng :
    • Dòng đầu là số nguyên dương N – số phần tử của dãy.
    • Dòng 2 là 3 số nguyên a, b, c.
    • Dòng còn lại gồm n số x1, x2, …, xn là n phần tử của dãy.

Output format :

  • Mỗi test case gồm 1 dòng, là kết quả của bài toán.

Giới hạn :

T<=3

n ≤ 1, 000, 000,

−5 ≤ a ≤ −1

b <= 10,000,000

c <= 10,000,000

1 ≤ xi ≤ 100.

Thuật toán:

Gọi f(x) = a * x ^ 2 + b * x + c

Thuật O(n^2):

Gọi dp(i) là chi phí lớn nhất khi phân hoạch đoạn từ 1 -> i.

sum(i) là tổng các phần tử từ 1 -> i.

dp(i) = max(dp(j) + f(sum(i) – sum(j)) (1 <= i <= n; 0 <= j < i)

 

Thuật O(n): dùng Convex Hull Trick

dp(i) = max(dp(j) + f(sum(i) – sum(j)) (1 <= i <= n; 0 <= j < i)

⇔ dp(i) = dp(j) + a * (sum(i) – sum(j))^ 2 + b * (sum(i) – sum(j)) + c

⇔ dp(i) = (a * sum(i) ^ 2 + b * sum(i) + c) + (-2 * a * sum(i) * sum(j)) + a * sum(j) ^ 2 – b * sum(j) ^ 2

Đặt A = -2 * a * sum(j), X = sum(i), B = a * sum(j) ^ 2 – b * sum(j) ^ 2

⇔ ta được đường thẳng y = A * X + B.

Vì mảng sum tăng dần -> ta có thể dùng two-pointer để giảm đpt xuống O(n)

Code:

#include 
using namespace std;

const int N = 1e6 + 10;

class ConvexHull {
private:
    int head, tail;
    long long A[N], B[N];
public:
    void init() { head = tail = 0; }
    bool bad(int l1, int l2, int l3) {
        return (long double) (B[l3] - B[l1]) / (A[l1] - A[l3]) < (long double) (B[l2] - B[l1]) / (A[l1] - A[l2]);
    }
    void add(long long a, long long b) {
        A[tail] = a; B[tail++] = b;
        while (tail > 2 && bad(tail - 3, tail - 2, tail - 1)) {
            A[tail - 2] = A[tail - 1];
            B[tail - 2] = B[tail - 1];
            tail--;
        }
    }
    long long query(long long x) {
        if (head >= tail) head = tail - 1;
        while (head < tail - 1
               && A[head + 1] * x + B[head + 1] >= A[head] * x + B[head]) head++;
        return A[head] * x + B[head];
    }
} hull;

int n, a, b, c;
long long sum[N];

long long f(long long x) { return a * x * x + b * x + c; }

void load() {
    scanf("%d%d%d%d", &n, &a, &b, &c);
    for (int i = 1; i <= n; ++i) {
        scanf("%lld", sum + i);
        sum[i] += sum[i - 1];
    }
}

void process() {
    hull.init();
    long long cost = f(sum[1]);
    hull.add(-2 * a * sum[1], cost + a * sum[1] * sum[1] - b * sum[1]);

    for (int i = 2; i <= n; ++i) {
        cost = f(sum[i]) + max(0ll, hull.query(sum[i]));
        hull.add(-2 * a * sum[i], cost + a * sum[i] * sum[i] - b * sum[i]);
    }
    printf("%lld\n", cost);
}

int main() {
  //  freopen("input.in", "r", stdin);
 //   freopen("output.out", "w", stdout);

    int test; scanf("%d", &test);
    while (test--) {
        load();
        process();
    }

    return 0;
}
Chủ đề: Convex Hull, Hình học, SPOJ

NKPATH – spoj

August 14, 2017 by Leave a Comment

[mathjax]

Đề bài:

Thuật toán:

Với mỗi ô (i,j) với  $i=1..m; j=1..n-1;$ kiểm tra xem ô (ii,jj) với $ii=1..i-1; jj=1..j;$ có đi được đến ô (i,j) không

  • Nếu có 
    l[i,j]:=(l[i,j]+l[ii,jj]) mod base;

Kết quả: $\sum_{i=1}^{m}L[i][n]$

Code:

const   fi='';
        fo='';
        maxn=100;
        base=1000000000;
type    arra=array[1..maxn,1..maxn] of integer;
        arrl=array[1..maxn,1..maxn] of longint;
var     a:arra;
        i,j,m,n:byte;
        l:arrl;
        f:text;
        res:int64;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,m,n);
    for i:=1 to m do
        for j:=1 to n do read(f,a[i,j]);
    close(f);
end;
procedure init;
begin
    for i:=1 to m do l[i,1]:=1;

    res:=0;
end;
function kt(x,y:longint):boolean;
var     tmp:longint;
begin
        while y>0 do
        begin
            x:=x mod y;
            tmp:=x;
            x:=y;
            y:=tmp;
        end;
        if x=1 then exit(false) else exit(true);
end;
procedure xuly;
var     ii,jj:byte;
begin
    for i:=1 to m do
        for j:=1 to n-1 do
        begin
            for ii:=i-1 downto 1 do
                for jj:=j downto 1 do
                        if kt(a[i,j],a[ii,jj]) then l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
            for jj:=j-1 downto 1 do
                if kt(a[i,j],a[i,jj]) then l[i,j]:=(l[i,j]+l[i,jj]) mod base;
        end;

    for i:=1 to m do
        for ii:=i downto 1 do
                for jj:=n-1 downto 1 do
                if kt(a[i,n],a[ii,jj]) then res:=(res+l[ii,jj]) mod base;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    init;
    xuly;
    xuat;
end.
Chủ đề: Quy hoạch động, SPOJ

C11BC1 – spoj

August 12, 2017 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e5);
  maxk=50;
  base=790972;
var
  f : array[0..maxn,0..maxk] of int64;
  i,j,n,k,m : longint;
  kq : int64;
  a,b : array[1..maxn] of longint;
procedure enter;
begin
  assign(input,fi);reset(input);
  readln(n,k);
  for i:=1 to n do read(a[i],b[i]);
  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,x : longint;
  begin
    i:=l;j:=r;
    x:=b[(l+r) div 2];
    repeat
      while x>b[i] do inc(i);
      while xj;
    if il then qs(l,j);
  end;
function muk(x : longint) : int64;
  var i : longint;
  begin
    muk := 1;
    for i:=1 to k do muk:=muk*x;
  end;
function cnk(n,k : longint) : int64;
  begin
    cnk := 1;
    for i:=n-k+1 to n do cnk := cnk*i;
    for i:=1 to k do cnk := cnk div i;
  end;
function tinh : int64;
begin
  fillchar(f,sizeof(f),0);
  for i:=0 to m do f[i,0] := 1;
  for i:=1 to m do
    for j:=1 to min(k,i) do
      f[i,j] := (f[i-1,j] + f[i-1,j-1]*a[i]) mod base;
  exit(f[m,k]);
end;
procedure process;
var i,j,dem : longint;
    dau,cuoi : longint;
begin
  qs(1,n);
  m := n;
  kq := tinh;
  dau := 1;
  while (dau<=n) do
  begin
    cuoi := dau+1;
    m := 1; a[1] := a[dau];
    while (cuoi<=n) and (b[cuoi]=b[dau]) do
      begin
        m := m+1;
        a[m] := a[cuoi];
        inc(cuoi);
      end;
    if cuoi-dau>=k then
      kq := (kq - tinh + base + base) mod base;
    dau := cuoi;
  end;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(kq);
  close(output);
end;
begin
  enter;
  process;
  print;
end.
Chủ đề: Quy hoạch động, SPOJ Mức độ:

UPGRANET – spoj

August 12, 2017 by Leave a Comment

Đề bài:

Thuật toán:

Ta thấy thông lượng truyền tin từ u đến v là giá trị lớn nhất của cạnh nhỏ nhất trên mọi con đường từ u đến v.
Vì vậy, ban đầu, ta sẽ xây dựng cây khung lớn nhất(tương tự như cây khung nhỏ nhất nhưng sort ngược lại).

Gọi dis(u,v) là cạnh có trọng số nhỏ nhất khi đi từ u đến v trên cây vừa tạo. Ta chọn nút 1 làm gốc, duyệt dfs để lưu trữ cạnh nhỏ nhất và các nút cha của u khi đi từ 1 đến u (đều dùng RMQ). Với mỗi 1 cạnh không nằm trong cây khung, ta tìm nút cha chung gần nhất(gọi là p), kết quả cộng thêm một lượng bằng hiệu của min(dis(u, p), dis(v, p)) và rọng số cạnh đang xét.

Code:

#include 
#define maxn 1000005
#define maxm 10000005
#define maxc 1000000007
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair
#define fort(i, a, b) for(int i = (a); i <= (b); i++)
#define ford(i, a, b) for(int i = (a); i >= (b); i--)
#define Task "UPGRANET"
#define fast ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define stop1 {cout << "-1\n"; return;}
#define stop2 {cout << "0\n"; return;}
#define stop3 {cout << "yes\n"; exit(0);}
#define skip1 {cout << "Yes\n"; continue;}
#define skip2 {cout << "No\n"; continue;}
#define ll long long

using namespace std;

ll n, m, root[maxn], h[maxn], res;
pii  par[maxn][20];
bool dd[maxn];
vector > ke[maxn];
struct canh
{
    ll u, v, w;
}ed[maxn];

void setup()
{
    cin >> n >> m;
    fort(i, 1, m)
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
}

bool cmp(canh p, canh q)
{
    return p.w > q.w;
}

ll getroot(ll u)
{
    if(root[u] == 0) return u;
    return root[u] = getroot(root[u]);
}

void make_tree()
{
    sort(ed+1, ed+m+1, cmp);
    fort(i, 1, m)
    {
        ll p = getroot(ed[i].u);
        ll q = getroot(ed[i].v);
        if(p == q) continue;
        root[p] = q;
        dd[i] = 1;
        ke[ed[i].u].pb(mp(ed[i].v, ed[i].w));
        ke[ed[i].v].pb(mp(ed[i].u, ed[i].w));
    }
}

void dfs(ll u, ll tr)
{
    fort(i, 0, int(ke[u].size()) - 1)
    {
        ll v = ke[u][i].F;
        if(v == tr) continue;
        h[v] = h[u] + 1;
        par[v][0] = mp(u,ke[u][i].S);
        fort(j, 1, 18)
        {
            par[v][j].F = par[par[v][j-1].F][j-1].F;
            par[v][j].S = min(par[par[v][j-1].F][j-1].S, par[v][j-1].S);
        }
        dfs(v, u);
    }
}

pii lca(ll u, ll v)
{
    pii p;
    p.S = 1ll* maxc * maxc;
    if( h[u] > h[v])
        swap(u, v);
    ll diff = h[v] - h[u];
    ford(i, 18, 0)
        if((diff >> i) & 1)
        {
            p.S = min(p.S, par[v][i].S);
            v = par[v][i].F;

        }
    if(v == u) return mp(u, p.S);
    ford(i, 18, 0)
        if(par[u][i].F != par[v][i].F)
        {
            p.S = min(p.S, min(par[v][i].S, par[u][i].S));
            v = par[v][i].F;
            u = par[u][i].F;
        }
    return mp(par[u][0].F, min(p.S, min(par[u][0].S, par[v][0].S)));
}

void work()
{
    make_tree();
    h[1] = 1;
    dfs(1, 0);
    fort(i, 1, m)
        if(!dd[i])
        {
            pii l = lca(ed[i].u, ed[i].v);
            res += max(0ll, l.S - ed[i].w);
        }
    cout << res;
}


int main()
{
    fast
  //  freopen(Task".inp", "r", stdin);
  //  freopen(Task".out", "w", stdout);
    setup();
    work();
    return 0;
}

Cowboy

Chủ đề: DFS, Đồ thị, Kruskal, LCA, Phương pháp Mức độ:

Cấu trúc dữ liệu BIT – Binary Indexed Tree (Fenwick Tree)

August 12, 2017 by Leave a Comment

Giới thiệu về cây Fenwick (hay còn được gọi là BIT)
BIT-yeulaptrinh.pw

Tổng quát, đặt m = 2k.p (với p là số lẻ). Hay nói cách khác, k là vị trí của bít 1 bên phải nhất của m. Trong Fenwick-Tree, nút có số hiệu m sẽ là nút gốc của một cây con gồm 2k nút có số hiệu từ m- 2k+1 đến m.

Ví dụ:

    – 8 = 23.1, vậy 8 là nút gốc của các nút 1, 2, 3, …, 8.

    – 12 = 22.3, vậy 12 là nút gốc của các nút  9, 10, 11, 12

    – 10 = 21.5, vậy 10 là nút gốc của các nút  9, 10.

    – 7 = 20.7, vậy 7 là nút gốc của chỉ nút  7.

    – 16 = 24.1, vậy 16 là nút gốc của các nút 1, 2, 3, …, 16.

Trong Fenwick-Tree, nút gốc đại diện cho tất cả các nút con của nó. Ý nghĩa của từ đại diện ở đây thường dùng là nút gốc lưu tổng giá trị của các nút con. Vì vậy khi tính toán, ta chỉ cần truy xuất nút gốc là đủ mà không cần thiết phải truy xuất đến các nút con. Xét ví dụ:

       Cho mảng gồm n phần tử a1, a2, …, an. Hãy tính tổng Am =  a1 + a2 + … + am (m ≤ n).

Thay vì sử dụng vòng lặp từ 1 đến m để truy xuất từng phần tử ai một (độ phức tạp O(m)), ta sử dụng cấu trúc FENWICK-TREE như sau:

    – t1 = a1

    – t2 = a1 + a2

    – t3 = a3

    – t4 = a1 + a2 + a3 + a4

    – t5 = a5

    – t6 = a5 + a6

    – t7 = a7

    – t8 = a1 + a2 + a3 + a4+ a5 + a6 + a7 + a8

    – …

    – t12 = a9 + a10 + a11 + a12

    – … (tiếp tục như vậy theo cách xây dựng Fenwick-Tree)

 

    * Để tính A15 (m=15), thay vì phải duyệt từ a1 đến a15, ta chỉ cần tính t8 + t12 + t14 + t15 .

    * Để tính A10, chỉ cần tính t8 + t10

    * Để tính A13, chỉ cần tính t8 + t12 + t13

    * Để tính A16, lấy ngay giá trị t16

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, sau đó lần lượt xóa các bít 1 của m theo thứ tự từ phải sang trái, tại mỗi bước trung gian chính là chỉ số nút cần truy xuất trong Fenwick-Tree.

Ví dụ: m = 13 có biểu diễn nhị phân là 1101:

     1) 1101 -> truy xuất nút 13

     2) Xóa bít 1 bên phải nhất còn 1100 -> truy xuất nút 12

     3) Xóa bít 1 bên phải nhất còn 1000 -> truy xuất nút 8

     4) Xóa bít 1 bên phải nhất và dừng.

Thao tác truy xuất các nút như trên được gọi là getFENWICK-TREE. May mắn là ta có một công thức rất đơn giản để xóa bít 1 bên phải dùng phép toán AND. Thủ tục getFENWICK-TREE như sau:

int getFENWICK-TREE(int m)
{
            int result = 0;
            for(; m> 0; m &= m-1) 
            {
                        result += t[m];
            }
            return result;
}

Độ phức tạp của getFENWICK-TREE là O(log2m)

Vấn đề còn lại là làm thế nào để xây dựng được Fenwick-Tree như trên? Cách thực hiện là ban đầu khởi tạo các nút của Fenwick-Tree là 0. Sau đó ứng với mỗi giá trị am thì cập nhật các nút cha liên quan trong cây. Ví dụ:

    – Cập nhật giá trị a5 -> cần cập nhật các nút t5, nút cha t6, nút cha t8, nút cha t16,….

    – Cập nhật giá trị a9 -> cần cập nhật các nút t9, nút cha t10, nút cha t12, nút cha t16,…

    – Cập nhật giá trị a4 -> cần cập nhật các nút t4, nút cha t8, nút cha t16,…

Tổng quát với m bất kỳ, biểu diễn m thành dạng nhị phân, nếu cộng 1 vào bít bên phải nhất của m thì ta được nút cha của m.

Ví dụ, m = 5 có biểu diễn nhị phân là 101:

    1) 101 -> cập nhật nút 5

    2) Cộng 1 vào bít phải nhất thành 0110 -> cập nhật nút 6

    3) Cộng 1 vào bít phải nhất thành 1000 -> cập nhật nút 8

    4) Cộng 1 vào bít phải nhất thành 10000 -> cập nhật nút 16.

Thao tác cập nhật các nút từ con đến cha như trên được gọi là updateFENWICK-TREE. Ta cũng có một công thức rất đơn giản để cộng 1 vào bít 1 bên phải nhất dùng phép toán AND. Thủ tục updateFENWICK-TREE như sau:

void updateFENWICK-TREE(int m, int value)
{
   for(; m<= n; m += m & -m)
   {
        t[m] += value;
   }
}

Độ phức tạp của updateFENWICK-TREE là O(log2n)

Trên đây là lý thuyết về Binary Indexed Tree. Bây giờ ta sẽ áp dụng FENWICK-TREE để giải bài Dãy nghịch thế và Dĩa nhạc 3.

Dãy nghịch thế: (Theo cách vét cạn thì cần xét tất cả các cặp, độ phức tạp là O(n2))

Phác thảo thuật toán:

– Dùng một mảng đếm t[100.000], t[u] cho biết hiện giờ có bao nhiêu số nhỏ hơn u.

– Đầu tiên khởi tạo các phần tử mảng t là 0.

– Duyệt từ cuối mảng lên đầu mảng (i từ n->1), ứng với mỗi ai thực hiện hai thao tác:

    1) Kiểm tra xem hiện giờ có bao nhiêu số nhỏ hơn ai (truy xuất t[ai]).

    2) Cập nhật ai vào mảng t, nghĩa là tăng các phần tử từ t[ai+1] đến t[100.000], mỗi phần tử thêm 1.

Tuy nhiên trong thao tác 2 việc cập nhật như vậy tổng thể độ phức tạp vẫn là O(n2). Bây giờ ta sẽ chuyển mảng t thành cấu trúc FENWICK-TREE. Đối với thao tác 1 dùng getFENWICK-TREE, đối với thao tác 2 dùng updateFENWICK-TREE.

Chương trình hoàn chỉnh

cin>>n;
for(i= 1; i<= n; i++) cin>>a[i];
kq = 0;
for(i= n; i>= 1; i–)
{
            kq += getFENWICK-TREE(a[i]);
            updateFENWICK-TREE(a[i]+1, 1);
}
cout<<kq;

Độ phức tạp là O(nlog2n)

Chủ đề: BIT, Cấu trúc dữ liệu

Thông tin về Google Code Jam World Finals 2017

August 11, 2017 by Leave a Comment

 

Theo dõi link bên dưới:

 

  1. Live Stream

  2. Problemset

  3. Score Board

Chủ đề: Kiếm tiền Online