Archives for Tháng Mười 2016


QBBISHOP – spoj

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

covua-yeulaptrinh.pw

Thuật toán:

  • BFS từ ô (s.x,s.y)
  • Mỗi lần BFS lấy ra ô (u,v) đi theo 4 đường chéo có dạng (u-x,v-x) , (u-x,v+x) , (u+x,v-x) , (u+x,v+x).
  • Đừng quên là không thể đi đến ô đang có cờ.

Code: [xem code]

const   fi='';
        fo='';
        maxn=200;
        dx:array[1..4] of integer =(1,-1,1,-1);
        dy:array[1..4] of integer =(1,1,-1,-1);
type    point=record
                x,y:integer;
                end;
var     free:array[0..maxn+1,0..maxn+1] of boolean;
        bac:array[0..maxn+1,0..maxn+1] of integer;
        q:array[1..maxn*maxn] of point;
        n,m,i,j:integer;
        s,f:point;
        dau,cuoi,res:longint;
procedure nhap;
var     x,y:integer;
begin
    assign(input,fi);reset(input);
    readln(n,m,s.x,s.y,f.x,f.y);
    fillchar(free,sizeof(free),false);
    for i:=1 to n do
        for j:=1 to n do free[i,j]:=true;
    for i:=1 to m do
        begin
            readln(x,y);
            free[x,y]:=false;
        end;
end;
procedure init;
begin
 
end;
procedure push(x,y:integer);
begin
    inc(cuoi);
    q[cuoi].x:=x;
    q[cuoi].y:=y;
end;
procedure bfs;
var     u,v:point;
begin
    dau:=1;cuoi:=1;
    q[1].x:=s.x;q[1].y:=s.y;
    while dau<=cuoi do
        begin
            u:=q[dau]; inc(dau);
            for i:=1 to 4 do
                for j:=1 to n do
                        begin
                            v.x:=dx[i]*j+u.x;
                            v.y:=dy[i]*j+u.y;
                            if (v.x=f.x) and (v.y=f.y) then
                                begin
                                        res:=bac[u.x,u.y]+1;
                                        exit;
                                end;
                            if (v.x>=1) and (v.y>=1) and (v.x<=n) and (v.y<=n) and (free[v.x,v.y])  then
                                begin
                                   bac[v.x,v.y]:=bac[u.x,u.y] +1;
                                   free[v.x,v.y]:=false;
                                   push(v.x,v.y);
                                end else break;
                        end;
        end;
    res:=-1;exit;
end;
procedure xuly;
begin
    if (s.x+s.y) mod 2<>(f.x+f.y) mod 2 then begin res:=-1; exit; end;
    bfs;
 
end;
procedure inkq;
begin
    assign(output,fo);rewrite(Output);
 
    writeln(res);
 
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.

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.

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.

[Kiếm tiền Online] Cộng tác viên cho YeuLapTrinh.pw

Nhằm mục đích xây dựng nội dung YeuLapTrinh.pw, khiến website giúp ích nhiều hơn nữa cho các bạn lâp trình viên, chúng tôi mời bạn trở thành công tác viên cho blog…

Khi đã trở thành cộng tác viên các bạn sẽ được cập một tài khoản có thể post bài lên YeuLapTrinh.pw nhưng vẫn cần qua quá trình kiểm duyệt của admin trước khi xuất bản. Với mỗi bài viết các bạn sẽ được trả ít nhất 6 nghìn đồng, nếu bài viết có giá trị cao thì sẽ được trả nhiều hơn, có thể là vài chục ngàn đồng. Khi tích lũy được trên 50 ngàn bạn sẽ được gửi tiền mặt.

cong-tac-vien yeulaptrinh.pw

Hãy đăng ký ngay! Không giới hạn thời gian đăng ký. Để đăng ký các bạn gửi mail về địa chỉ yeulaptrinh.pw@gmail.com với nội dung:

  • Họ và tên:
  • Địa chỉ mail liên hệ:
  • Số điện thoại hoặc nick facebook:
  • Tên đăng nhập muốn dùng:
  • Bạn biết và giỏi về mảng gì?:

 

 

QBSELECT – spoj

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

Tóm tắt đề bài: Cho bảng 4*n, chọn các ô không kề cạnh sao cho tổng các ô chọn lớn nhất

Ví dụ: Xét bảng với n=3 trong hình vẽ dưới đây:

qbselect-yeulaptrinh

 

Cách chọn cần tìm là tập các ô S = {(3,1), (1,2), (4,2), (3,3)} với trọng lượng 32.

Thuật toán:

–         Theo đề bài thì bảng có 4 dòng và n cột;

  • Gọi S là trạng thái chọn các ô ở cột thứ j, ta có thể biểu diễn S bằng 4 bit (các bit được đánh số từ phải sang bắt đầu bằng 0) với ý nghĩa:

+    S[i-1] = 0: dòng thứ i của cột j không được chọn;

+    S[i-1] =1: dòng thứ i của cột j được chọn.

  • Với 4 bit, S có thể biểu diễn 16 trạng thái từ {0000} đến {1111} (từ 0 đến 15), tuy nhiên ta nhận thấy chỉ có 8 trạng thái sau là thỏa yêu cầu của bài toán: {0000}, {0001}, {0010},

{0100}, {1000}, {1001}, {0101}, {1010} (tương ứng với các giá trị 0, 1, 2, 4, 5, 8, 9, 10).

  • Gọi T[S, j] là trọng lượng lớn nhất khi chọn các ô đến cột thứ j với trạng thái chọn là S, ta có công thức quy hoạch động như sau:

T[S, j] = max(T[P, j-1] + value(S))

với P là trạng thái của cột liền trước của S sao cho P và S không có 2 bit 1 đồng thời ở cùng vị trí, còn value (S) là giá trị cách chọn cột j với trạng thái S.

  • Khi cài đặt, với bài toán này, ta chỉ cần xây dựng hàm getBit để giải mã trạng thái S
  • Còn thao tác quy hoạch động được thực hiện bình thường

Code:

uses    math;
const   fi='';
        fo='';
        maxn=10000;
        s:array[1..8] of integer = (0,1,2,4,5,8,9,10);
var     t:array[0..maxn,1..8] of longint;
        i,j,k,n:integer;
        res,tam:longint;
        a:array[1..maxn,1..4] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);
 
    readln(n);
 
    for i:=1 to 4 do
        for j:=1 to n do read(a[j,i]);
 
    close(input);
end;
function getbit(x,y:integer):byte;
begin
    getbit:=(x shr y) and 1;
end;
procedure xuly;
begin
    for i:=1 to n do
        for j:=1 to 8 do
        begin
            tam:=0;
            for k:=1 to 4 do tam:=tam+getbit(s[j],k-1)*a[i,k];
            for k:=1 to 8 do
              if (s[j] and s[k]=0) and (t[i-1,k]+tam>t[i,j])
                then t[i,j]:=t[i-1,k]+tam;
        end;
 
    res:=low(longint);
    for i:=1 to 8 do res:=max(res,t[n,i]);
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
 
    tam:=low(integer);
    for i:=1 to n do
        for j:=1 to 4 do tam:=max(tam,a[i,j]);
 
    if tam<=0 then begin writeln(tam); halt; end;
 
    writeln(res);
 
    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
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;
}

SEQ198 – spoj

Đề bài:

Thuật toán:

  • Sử dụng phương pháp quy hoạch động kết hợp với bitmask.
  • Sắp xếp lại mảng A.
  • f[i,state] là số phần tử cần loại bỏ của dãy A[1..i] khi có state là trạng thái giữ hoặc chọn của 10 số cuỗi của dãy.

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; ++i)
#define FORD(i, a, b) for(int i = a; i >= b; --i)
#define FOR(i, a, b) for(int i = a; i < b; ++i)
#define X first
#define Y second
#define ll long long
#define mp make_pair
#define pb push_back
#define endl '\n'
 
const int MAXN = 1e5 * 5;
const int inf = 1024;
const int N = 5000;
 
using namespace std;
int n,p[N],a[N],b[N],l[N],ans,ss,c[N],f[2001][1025];
 
void update()
{
    int cnt = 0;
    int dem = 0;
    FORE(i,1,min(n,10))
    if (l[i])
            c[++cnt] = a[i],dem += b[i];
    sort(c+1,c+cnt+1);
    FORE(i,1,cnt)
    FORD(j,i-1,1)
    if (c[i] - c[j] > 9) break;
    else
    {
        if (c[i] - c[j] == 1) return;
        if (c[i] - c[j] == 8) return;
        if (c[i] - c[j] == 9) return;
    }
    f[10][ss] = dem;
    ans = max(ans , dem);
}
 
void duyet(int i)
{
    FORE(j,0,1)
    {
        ss = ss*2 + j;
        l[i] = j;
        if (i == min(n,10)) update();
        else duyet(i+1);
        ss /= 2;
    }
}
 
int ok(int u,int v)
{
    if (u - v == 1) return 1;
    if (u - v == 8) return 1;
    if (u - v == 9) return 1;
    return 0;
}
 
int check(int s,int i)
{
    FORE(j,0,8)
    {
        int xx = (s >> j)&1;
        if (xx && ok(a[i],a[i - j - 1])) return 1;
    }
    return 0;
}
 
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("", "r", stdin);
    freopen("", "w", stdout);
    #endif //yeulaptrinh.pw
    cin>>n;
    int lx = n;
    FORE(i,1,n) cin>>p[i];
    sort(p+1,p+n+1);
    int po = -1;
    int n1 = 0;
    FORE(i,1,n)
    if (p[i] != po)
    {
        po = p[i];
        ++n1;
        a[n1] = p[i];
        ++b[n1];
    }
    else ++b[n1];
    n = n1;
    duyet(1);
    if (n <= 10)
    {
        cout<<lx - ans;
        return 0;
    }
    FORE(i,10,n-1)
    FORE(x,0,1023)
    {
        int xx = (2*x)%inf;
        f[i+1][xx] = max(f[i+1][xx] , f[i][x]);
        if (check(x,i+1)) continue;
        xx = (2*x + 1)%inf;
        f[i+1][xx] = max(f[i+1][xx] , f[i][x] + b[i+1]);
    }
    int kq = 0;
    FORE(i,10,n)
    FORE(x,0,1024)
        kq = max(kq , f[i][x]);
    cout<<lx - kq;
    return 0;
}
uses math;
const
  fi = '';
var
  a,b,cnt : array[0..2001] of longint;
  f : array[0..2001,0..511] of longint;
  dd : array[0..2001,0..511] of boolean;
  n,n1 : longint;
 
procedure enter;
  var
    i : longint;
  begin
    assign(input,fi);
    reset(input);
    readln(n);
    for i := 1 to n do
      read(b[i]);
    close(input);
  end;
 
 
procedure qsort(l,r : longint);
  var
    i,j,k,tmp : longint;
  begin
    i := l;
    j := r;
    k := b[l + random(r - l + 1)];
    while i < j do
      begin
        while b[i] < k do inc(i);
        while b[j] > k do dec(j);
        if i <= j then
          begin
            tmp := b[i];
            b[i] := b[j];
            b[j] := tmp;
            inc(i);
            dec(j);
          end;
      end;
    if l < j then qsort(l,j);
    if i < r then qsort(i,r);
  end;
 
function getbit(x,i : longint) : longint;
  begin
   exit(1 and (x shr (i - 1)));
  end;
 
function check(stt : longint) : boolean;
  begin
    if (getbit(stt,1) = 1) or (getbit(stt,8) = 1) or (getbit(stt,9) = 1) then exit(false);
    exit(true);
  end;
 
function batbit(x,i : longint) : longint;
  begin
    exit(x or (1 shl (i - 1)));
  end;
 
function sttnext(tt,stt,i : longint) : longint;
  var
    res,kc,j : longint;
  begin
    kc := a[i+1] - a[i];
    res := 0;
    for j := 0 to 9 - kc do
      if j = 0 then
        begin
          if tt = 1 then res := batbit(res,kc)
        end
      else
        if getbit(stt,j) = 1 then
          res := batbit(res,kc + j);
    exit(res);
  end;
 
procedure init;
  var
    i,j : longint;
  begin
    qsort(1,n);
    a[1] := b[1];
    j := 1;
    cnt[1]:=1;
    for i := 2 to n do
      if b[i] <> a[j] then
        begin
          inc(j);
          a[j] := b[i];
          cnt[j] := 1;
        end
      else inc(cnt[j]);
    n1:=j;
    a[n1+1] := high(longint)
  end;
 
function cal(i,stt: longint) : longint;
  var
    ff : longint;
  begin
    if dd[i,stt] then exit(f[i,stt]);
    dd[i,stt] := true;
    if i = n1 + 1 then
      ff := 0
    else
      begin
        ff := cal(i + 1,sttnext(0,stt,i)) + cnt[i];
        if check(stt) then
          ff := min(ff,cal(i + 1,sttnext(1,stt,i)));
      end;
    f[i,stt] := ff;
    exit(ff);
  end;
 
procedure print;
  begin
    writeln(cal(1,0));
  end;
 
begin
  enter;
  init;
  print;
end.