LCS2X – spoj

December 2, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Gọi L[i,j] là độ dài dãy con chung bội hai dài nhất với số cuối cùng là A[i] và B[j]1) Với A[i] <> B[j] thì L[i,j] = 0

    2) Với A[i] = B[j] thì L[i,j] = max(L[x,y] + 1) ( với x<i, y<j, A[x]*2 <= A[i] )

  • Để tính max(L[x,y]) nhanh chóng, ta sử dụng mảng F với ý nghĩa:F[y] = max(L[x,y])   =>Kết quả là max(F[j]) (với 1<=j<=n)

    Gọi ma=max(F[y]) ( với y<j, B[y]*2 <= A[i] )

    Khi đó ta có đoạn code phần xử lý sẽ là:

    for (i=1;i<=m;++i){
        ma=0;
        for (j=1;j<=n;++j){
            matruocj=ma;
            if (b[j]*2<=a[i]) ma=max(ma,f[j]);
            if (a[i]==b[j]) f[j]=max(f[j],matruocj+1);
        }
    }
  • Với cách này thì bạn chỉ cần dùng mảng 1 chiềuĐộ phức tạp: O(M*N)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        oo      =trunc(1e4);

var     a, b, f :array[0..oo] of longint;
        ma,matruocj     :longint;
        ans     :longint;
        m, n    :longint;
procedure Optimize;
var     i, j    :longint;
begin
        fillchar(f, sizeof(f),0);
        for i:=1 to m do
                begin
                        ma:=0;
                        for j:=1 to n do
                                begin
                                        matruocj:=ma;
                                        if b[j]*2<=a[i] then ma:=Max(ma,f[j]);
                                        if b[j]=a[i] then f[j]:=max(f[j],matruocj+1);
                                end;
                 end;

end;

Procedure run;
var     i, t,l :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(t);
        for l:=1 to t do
                begin
                        readln(m, n);
                        for i:=1 to m do read(a[i]);
                        for i:=1 to n do read(b[i]);
                        Optimize;
                        ans:=0;
                        for i:=1 to n do
                                if f[i]>ans then ans:=f[i];
                        writeln(ans);
                end;
        close(input);close(output);
end;

begin
        run;
end.
Chủ đề: Quy hoạch động, SPOJ Mức độ:

VOGAME – spoj

November 30, 2016 by Leave a Comment

Đề bài:

Thuật toán:

  • Mình tham khảo từ solution của anh Lê Anh Đức
    Thuật toán:
    -Nhận xét là tính chẵn lẻ của số bi đỏ ko đổi, vậy nên kết quả sẽ là số bi đỏ modulo 2.
    -Hãy thử tạo 1 test và sinh ra dãy A, các bạn sẽ nhận thấy dãy A tuần hoàn theo chu kì D+1, từ đó có thể giải quyết bài toán này. Sau đây là code của mình:

Code:

#include
#define N 100001
using namespace std;
int t,n,d;
long long a[N], s[3];
int main()
{
	cin>>t;
	for (int z=1; z <= t; z++)
		{
			s[0]=s[1]=0;
			cin>>n>>d;
			for (int i=1; i <= d; i++)
				{
					cin>>a[i];
					s[a[i]]=s[a[i]]+1;
				}
			if (n == d)
				{
					cout<
Chủ đề: SPOJ, Toán học Mức độ:

PVOI14_3 – spoj

November 29, 2016 by Leave a Comment

Đề bài:

Thuật toán:

Ta có 1 công thức sau:

Gọi k là chi phí nhỏ nhất cần tìm.

Nếu tồn tại một chuyến đi để mất chi phí là k thì

(S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp) = k

⇔ S1 + S2 + … + Sp – k * (T1 + T2 + … + Tp) = 0

⇔ (S1 – k * T1) + (S2 – k * T2) + … + (Sp – k * Tp) = 0.

 

Giả sử tồn tại 1 chuyến đi có chi phí km < k khi đó ta có:

kmin < k = (S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp)

⇔ (S1 – kmin * T1) + (S2 – kmin * T2) + … + (Sp – kmin * Tp) > 0

 

Từ đây ta có nghĩ ra 1 thuật toán như sau.

  • Chặt nhị phân chi phí nhỏ nhất(x), với mỗi chi phí Mình tạo trọng số mỗi cho mỗi cạnh (s ,t) -> (s – x * t)
  • Nếu tồn tại 1 chu trình âm với trọng số mới -> không thể tạo ra chi phí là x.
  • Ngược lại nếu không tồn tại 1 chu trình âm nào thì kết quả cần tìm sẽ <=x
    => Chúng ta có thể sử dụng thuật toán FordBellman để tìm chu trình âm

Code:

#include 

using namespace std;

#define N 1010
#define M 10010
const double esp = 1e-5;

int n, m,  trace[N], u[M], v[M], c[M];
double d[N];

bool Ok(int x, int y) {
    while (x != 1){
        x = trace[x];
        if (x == 0) return false;
        if (x == y) return true;
    }
    return false;
}
bool FordBellman(double mid) {
    for (int i = 1; i<=n; i++) d[i] = 1e18;
    d[1] = 0;
    memset(trace, 0, sizeof trace);
    for (int i = 0; i d[x] + c[j] - mid) {
                d[y] = d[x] + c[j] - mid;
                if (Ok(x, y)) {
                    return true;
                }
                trace[y] = x;
            }
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i = 0; i>u[i]>>v[i]>>c[i];
    }
    double l = 0;
    double r = 1e10;
    double cur = 0;
    while (r - l >= esp) {
        double mid = (l + r) / 2;
        if (!FordBellman(mid)) {
            cur = mid;
            l = mid;
        }else r = mid;
    }
    if (abs (cur - 1e10) <=esp) {
        cout<<"NO TOUR";
    }else
    cout<

{$MODE OBJFPC}
program SmartDogContest;
const
  InputFile  = '';
  OutputFile = '';
  maxN = 1000;
  maxM = 10000;
  maxW = 1000000000;
  maxD = (maxN + 1) * maxW;
type
  TEdge = record
    u, v, c: Integer;
  end;
var
  fi, fo: TextFile;
  e: array[1..maxM] of TEdge;
  d: array[1..maxN + 1, 1..maxN] of Int64;
  n, m: Integer;
  BestMiu: Extended;

procedure Enter;
var
  i: Integer;
begin
  ReadLn(fi, n, m);
  for i := 1 to m do
    with e[i] do
      ReadLn(fi, u, v, c);
end;

procedure Init;
var
  i: Integer;
begin
  FillQWord(d, SizeOf(d) div 8, maxD);
  for i := 1 to n do
    d[1, i] := 0;
end;

procedure Minimize(var target: Int64; value: Int64); inline;
begin
  if target > value then target := value;
end;

procedure Optimize;
var
  k, i: Integer;
begin
  for k := 2 to n + 1 do //Tinh d[k, v] qua cac d[k - 1, u]
    for i := 1 to m do
      with e[i] do
        Minimize(d[k, v], d[k - 1, u] + c);
end;

procedure GetBest;
var
  v, k: Integer;
  min, max, trial: Extended;
begin
  min := maxD;
  for v := 1 to n do
    if d[n + 1, v] < maxD then
      begin
        max := -maxD;
        for k := 1 to n do
          if d[k, v] < maxD then
            begin
              trial := (d[n + 1, v] - d[k, v]) / (n - k + 1);
              if max < trial then max := trial;
            end;
        if max < min then
          min := max;
      end;
  BestMiu := min;
end;

begin
  AssignFile(fi, InputFile); Reset(fi);
  AssignFile(fo, OutputFile); Rewrite(fo);
  try
    Enter;
    Init;
    Optimize;
    GetBest;
    if BestMiu = maxD then
      Write(fo, 'NO TOUR')
    else
      Write(fo, BestMiu:0:2);
  finally
    CloseFile(fi); CloseFile(fo);
  end;
end.
Chủ đề: Đồ thị, Floyd, SPOJ Mức độ: ,

VOSMAXK – spoj

October 1, 2016 by Leave a Comment

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

Thuật toán:

  • Code mình viết bên dưới rất dễ hiểu các bạn có thể tham khảo

Code:

const   inp='';
        out='';
        maxn=1000000;
var     a:array[1..maxn] of longint;
        n,k,i:longint;
        res,tmp,hold:int64;
begin
    assign(input,inp); reset(input);
    assign(output,out); rewrite(output);
    readln(n,k);
    for i:=1 to n do read(a[i]);

    res:=0; hold:=0;
    for i:=1 to n do
    begin
        if a[i]=k then
                begin
                        res:=res+(i-hold);
                        tmp:=i-hold;
                end
                else
        if a[i]>k then begin hold:=i; tmp:=0; end
        else res:=res+tmp;
    end;

    writeln(res);
    close(input); close(output);
end.
Chủ đề: SPOJ Mức độ:

VPBINDEG – spoj

October 1, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

{$H+}
program Revolutions_VPbindeg;
const
  fi = '';//Revolutions.inp';
  fo = '';//Revolutions.out';
  maxn = 10001;
var
  n : longint;
  s : string;
  T,k : longint;

procedure open;
begin
  assign(input,fi); reset(input);
  assign(output,fo); rewrite(output);
end;

procedure clo;
begin
  close(input);
  close(output);
end;

function calc(k : longint) : longint;
var
  i,s1,s0,kq : longint;
begin
  s1:=0; s0:=0; kq:=0;
  for i:=1 to n do if s[i]='1' then inc(s1);
  for i:=1 to n do
    if s[i]='0' then
      begin
        inc(s0);
        if (s0>=k) and (s1>=k) then inc(kq,s1-k+1);
      end
    else dec(s1);
  calc:=kq;
end;

procedure main;
var
  test : longint;
begin
  readln(T);
  for test:=1 to T do
    begin
      readln(n,k);
      readln(S);
      writeln(calc(k)-calc(k+1));
    end;
end;

BEGIN
  open;
  main;
  clo;
END.
Chủ đề: SPOJ

QBPOINT – SPOJ

October 1, 2016 by Leave a Comment

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

Thuật toán:

  • Duyệt n điểm, với mỗi điểm i ta:
    • Duyệt các điểm j <> i rồi tính vector ij lưu lại vào 1 mảng ss[]
    • Sort lại mảng ss[]
    • 3 điểm i,j,k thẳng hàng nếu vector ij = vector ik

Code:

#include 
#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++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;

using namespace std;
int n,x[2001],y[2001];
long long res;
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("tripoint.inp", "r", stdin);
    freopen("tripoint.out", "w", stdout);
    #endif //
    cin>>n;
    FORE(i,1,n) cin>>x[i]>>y[i];
    FORE(i,1,n)
    {
        vector  ss; int cc=0;
        FORE(j,1,n)
        if (x[j]!=x[i])
            ss.push_back((double) (y[j]-y[i])/(x[j]-x[i]));
        else ++cc;
        sort(ss.begin(),ss.end());
        int sl=(cc-2)*(cc-1);
        if (ss.size())
        {
            int dem=1;
            FORE(j,1,ss.size()-1)
            if (ss[j]==ss[j-1]) ++dem;
            else
            {
                sl+=dem*(dem-1);
                dem=1;
            }
            sl+=dem*(dem-1);
        }
        res+=sl;
    }
    cout<
Chủ đề: Hình học, SPOJ Mức độ: ,

QUEENNB – SPOJ

September 10, 2016 by Leave a Comment

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

Thuật toán:

  • Thuật toán cũng không có gì phức tạp. Mình chỉ duyệt 2 lần: lần 1 từ đầu đến cuối bảng, lần 2 từ cuối về đầu bảng
  • Còn mỗi lần duyệt mình làm gì thì các bạn hãy đọc code vì mình viết code rất dễ hiểu

Code:

const   fi='';
        fo='';
        maxn=1000+3;

type    arrf    =array[0..maxn,0..maxn] of longint;

var     f       :arrf;
        h,c,d,d2   :arrf;
        i,j,n,m :longint;
        a       :array[1..maxn,1..maxn] of byte;

procedure enter;
var     tam     :char;
begin
        assign(input,fi);reset(input);
        readln(m,n);
        for i:=1 to m do
        begin
                for j:=1 to n do
                        begin
                                read(tam);
                                if tam='.' then a[i,j] := 1 else a[i,j] := 0;
                        end;
                readln;
        end;
        close(input);
end;

procedure process;
begin
        for i:=1 to m do
                for j:=1 to n do
                        begin
                                if a[i,j]=0 then
                                        begin
                                                h[i,j]:=0;
                                                c[i,j]:=0;
                                                d[i,j]:=0;
                                                d2[i,j] := 0;
                                                continue;
                                        end;
                                h[i,j] := h[i,j-1]+1;
                                c[i,j] := c[i-1,j]+1;
                                d[i,j] := d[i-1,j-1]+1;
                                d2[i,j] := d2[i-1,j+1]+1;
                                f[i,j] := h[i,j]+c[i,j]+d[i,j]+d2[i,j]-4;
                        end;
        fillchar(h,sizeof(h),0);
        fillchar(c,sizeof(c),0);
        fillchar(d,sizeof(d),0);
        fillchar(d2,sizeof(d2),0);
        for i:=m downto 1 do
                for j:=n downto 1 do
                        begin
                                if a[i,j]=0 then
                                        begin
                                                h[i,j] := 0;
                                                c[i,j] := 0;
                                                d[i,j] := 0;
                                                d2[i,j] := 0;
                                                continue;
                                        end;
                                h[i,j] := h[i,j+1]+1;
                                c[i,j] := c[i+1,j]+1;
                                d[i,j] := d[i+1,j+1]+1;
                                d2[i,j] := d2[i+1,j-1]+1;
                                inc(f[i,j] , h[i,j]+c[i,j]+d[i,j]+d2[i,j]-3 );
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        for i:=1 to m do
        begin
                for j:= 1 to n do
                        write(f[i,j],' ');
                writeln;
        end;
        close(output);
end;
begin
        enter;
        process;
        print;
end.
Chủ đề: SPOJ

TJALG – SPOJ

September 10, 2016 by Leave a Comment

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

Thuật toán:

  • Bài này thuần sử dụng thuật toánn Tarjan. Thuật toán Tarjan đơn thuần dựa trên thuật toán duyệt đồ thị DFS.
  • Các bạn có thể tham khảo thuầ toán Tarjan trong sách của thầy Lê Minh Hoàng

Code:

uses math;
const
  fi='';//spa.inp';
  fo='';//spa.out';
  maxn=trunc(1e5);
  maxm=trunc(1e6);
  oo=trunc(1e9);
var
  i,j,n,m,tpltm,top,tg,count : longint;
  link,head,ke : array[1..maxm] of longint;
  low,num : array[1..maxn] of longint;
  st : array[1..maxm*10] of longint;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure enter;
  var u,v : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m);
    for i:=1 to m do
      begin
        read(u,v);
        add(i,u,v);
      end;
  end;
function pop : longint;
  begin
    pop := st[top];
    dec(top);
  end;
procedure push(x : longint);
  begin
    inc(top);
    st[top] := x;
  end;
procedure dfs(u : longint);
  var i,v : longint;
  begin
    inc(count);
    num[u] := count;
    low[u] := count;
    push(u);
    i := head[u];
    while I<>0 do
      begin
        v := ke[i];
        if cx[v] then
        if num[v]=0 then
          begin
            dfs(v);
            low[u] := min(low[u],low[v]);
          end
          else
          begin
            low[u] := min(low[u],num[v]);
          end;
        i := link[i];
      end;
    if low[u]=num[u] then
      begin
        inc(tpltm);
        repeat
          v := pop;
          cx[v] := false;
        until v=u;
      end;
  end;
procedure process;
  var i : longint;
  begin
    fillchar(cx,sizeof(cx),true);
    for i:=1 to n do
      if num[i]=0 then
        begin
          dfs(i);
        end;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(tpltm);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Chủ đề: DFS, SPOJ Mức độ: ,

SUBSTR – SPOJ

August 26, 2016 by Leave a Comment

Đề bài: http://yeulaptrinh.de/319/substr-spoj/

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.
    Chủ đề: Hashing, SPOJ Mức độ:

    COIN34 – SPOJ

    August 21, 2016 by 1 Comment

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

    Thuật toán:

    Code:

    uses math;
const
  fi='';
  fo='';
  maxs=2*trunc(1e6);
  maxn=17;
var
  st,d : array[1..maxs] of longint;
  c : array[1..maxn*2] of longint;
  i,j,n,res,s1,s2,x,d1,c1,top : longint;
procedure enter;
  begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
    c[1] :=2; c[2] := 3; c[3] := 5;
    for i:=4 to 34 do
      c[i] := c[i-1]+c[i-2]+c[i-3];
  end;
procedure up1;
  begin
    //if c1=x then begin res := max(res,d1); exit; end;
    //if c1>x then exit;
    inc(top); st[top] := c1;
    d[top] := d1;
  end;
procedure try1( i : longint);
  var j : longint;
  begin
    for j:=0 to 1 do
      begin
        if j=1 then begin c1 := c1+c[i]; inc(d1) end;
        if i=s1 then up1 else try1(i+1);
        if j=1 then begin c1 := c1-c[i]; dec(d1) end;
      end;
  end;
procedure up2;
  var dau,cuoi,giua,xx : longint;
  begin
    if x=c1 then begin res := max(res,d1); exit; end;
    if c1>x then exit;
    xx := x-c1;
    dau:=1;cuoi:=top;
    giua:=(dau+cuoi) div 2;
    while (giua<>dau) and (giua<>cuoi) do
      begin
        if st[giua]>=xx then cuoi :=giua else dau := giua;
        giua :=(dau+cuoi) div 2;
      end;
    for giua := dau to cuoi do
      if st[giua]=xx then break;
    if st[giua]=xx then res := max(res,d1+d[giua]);
  end;
procedure try2( i :longint);
  var j : longint;
  begin
    for j:=1 downto 0 do
      begin
        if j=1 then begin c1 := c1+c[i]; inc(d1); end;
        if i=34 then up2 else try2(i+1);
        if j=1 then begin c1 := c1-c[i]; dec(d1); end;
      end;
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs1(l,r : longint);
  var i,j,x,y : longint;
  begin
    i :=l;j:=r;
    x:=st[(l+r) div 2];
    y:=d[(l+r) div 2];
    repeat
      while (x>st[i]) or((x=st[i]) and (d[i]>y)) do inc(i);
      while (xj;
    if i
    Chủ đề: Duyệt phân tập, SPOJ Mức độ: