V8SCORE – SPOJ

June 15, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

const   fi='';
        fo='';
        oo=20;
var     i,j,tmp2:longint;
        s,k,n,tong,ss,tmp:longint;
        a:array[1..oo,1..oo] of longint;
        c:array[0..200] of boolean;
        trace:array[0..oo] of longint;
        f:text;
        tim:boolean;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,s,k,n);
    for i:=1 to n do
        for j:=1 to k do read(f,a[i,j]);
    close(f);
end;
function max2(x,y:integer):integer;
begin
    if x>y then max2:=x else max2:=y;
end;
procedure init;
begin
    for i:=1 to n do c[a[i,k]]:=true;
end;
procedure thu(x,y,tong:integer);
var     j,ss:integer;
begin
if not(tim) then
 if y<k then
 begin
   if a[x,y]>=trace[y-1] then
   begin
        tmp:=tong+(k-y+1)*a[x,y];
        if tmp<=s then
                begin
                        tong:=tong+a[x,y];
                        trace[y]:=a[x,y];
                        for j:=1 to n do thu(j,y+1,tong);
                end;
   end;
 end else
        begin
        if (c[s-tong]) and (s-tong>=trace[k-1]) then
                begin
                trace[k]:=s-tong;
                tim:=true;
                end;
        end;
end;
procedure xuly;
begin
    trace[0]:=-1;
    for i:=1 to n do
    begin
        if tim then exit else
        begin
                fillchar(trace,sizeof(trace),0);
                thu(i,1,0);
        end;
    end;
end;
procedure inkq;
begin
    assign(f,fo);
    rewrite(f);
    if tim then
    begin
        writeln(f,'YES');
        for i:=1 to k do write(f,trace[i],' ');
    end
        else writeln(f,'NO');
    close(f);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.
Chủ đề: Đệ quy, SPOJ

QBMARKET – SPOJ

June 15, 2016 by Leave a Comment

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

Thuật toán:

Gọi  L[j] là số cách mua hàng khi có j đồng .Như vậy khi ta có khi ta mua các mặt hàng từ (1..i-1) hết j đồng và số cách mua là L[j] thì khi xét đến mặt hàng thứ i với k là số lượng mặt hàng i mà ta sẽ mua thì số cách mua hết j+c[i]*k ( S) đồng sẽ tăng thêm một lượng L[j]. Ta có công thức quy hoạch động :

Nếu j+c[i]*k<=S thì L[j+c[i]*k]:=L[j+c[i]*k]+L[j] (j=S..1,i=1..n,k=1..mi). Khởi tạo L[0]=1, L[1..S]=0.

Tại sao vì j+c[i]*k<=S vì nếu lớn hơn S rồi ta không cần quan tâm vì ta chỉ có tối đa S đồng thôi.

Trong qua trình cài đặt ta thấy nếu ta duyệt nếu ta duyệt j tăng dần từ 1 đến S, k tăng dần từ 1 đến mi thì sẽ xảy ra trường hợp như sau:j=0,L[0]=1,i=1,c[1]=1. Đầu tiên k=1 thì L[0+1*1]=L[0]+L[2]=1, k=2 thì L[0+1*2]=L[0]+L[2]=1.
Tăng  j và i giữ nguyên, j=1.Đầu tiên k=1 thì L[1+1*1]=L[1]+L[1]=2 đến đây ta đã thấy vô lí L[2] với i=1 không thể nào bằng 2 được mà L[2]=1. Trường hợp này là do khi j=j1 ta tính L[j1+x], j tăng lên j1+x ta tính L[j1+x+y] ta có

L[j1+x+y]=L[j1+x+y]+L[j1+x] mà khi đó L[j1+x] không còn là số cách mua hết j1+x đồng từ i-1 mặt hàng (1..i-1) mà là mua i mặt hàng (1..i) vì ta vừa tính L[j1+x] khi mua k mặt hàng i mà c[i]*k=x, tất nhiên k>=1.Nói ngắn gọn bạn phải hiểu L[j] trong công thức trên là số cách mua hết j đồng từ i-1 mặt hàng (1..i-1)

Để khắc phục tình trạng này ta duyệt j giảm từ S về 0 .

Code bên dưới nộp sẽ được 85 điểm do chạy quá thời gian. Nếu bài cho time limit 1s thì sẽ được 100 điểm. Tất nhiên thuật toán trên hoàn toàn đúng.

Code:

Const
        fi='';
        fo='';
        maxn=500;
        maxs=100000;
 
Type
        arr1    =array[1..maxn] of longint;
        arr2    =array[0..maxs] of int64;
 
Var
        n,s     :longint;
        c,m     :arr1;
        L       :arr2;
        f       :text;
 
procedure nhap;
var
        i       :longint;
begin
        assign(f,fi);
        reset(f);
        readln(f,s,n);
        for i:=1 to n do readln(f,c[i],m[i]);
        close(f);
end;
 
procedure solution;
var
        i,j,k   :longint;
begin
        L[0]:=1; {Neu co 0 dong thi coi la co mot cach la khong mua gi ca}
        for j:=1 to s do L[j]:=0; { Khoi tao mang L }
        for i:=1 to n do
                for j:=s downto 0 do
                        if L[j]>0 then
                        	for k:=1 to m[i] do
                                if j+k*c[i]<=s then
                                        L[j+c[i]*k]:=L[j]+L[j+c[i]*k];
end;
 
procedure xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,L[s]); {Ket qua nam o L[s]}
        close(f);
end;
 
begin
        nhap;
        solution;
        xuat;
end.
Chủ đề: Quy hoạch động, SPOJ Mức độ:

MMOD29 – SPOJ

June 15, 2016 by 2 Comments

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

Thuật toán:

  • (đang cập nhập)

Code:

const   fi      ='';
        fo      ='';
 
var     f1, f2       :text;
        x       :longint;
        a, b, c :longint;
function get(a, b:longint):longint;
var     tmp     :longint;
begin
        if b = 0 then exit(1);
        if b mod 2 = 0 then exit(sqr(get(a, b div 2)) mod 29 )
        else exit( (sqr(get(a, b div 2))*a) mod 29 );
end;
 
BEGIN
        assign(f1, fi);
        reset(f1);
        assign(f2, fo);
        rewrite(f2);
        while not eof(f1) do
                begin
                        readln(f1, x);
                        if x = 0 then break;
                        a:=(get(2, 2*x + 1) - 1 ) mod 29;
                        b:=(get(3,   x + 1) - 1 ) mod 29;
                        c:=(get(167, x + 1) - 1 ) mod 29;
                        writeln(f2,(a*b*c*9) mod 29);
                end;
        close(f1);
        close(f2);
END.
Chủ đề: SPOJ

QBROBOT – SPOJ

June 10, 2016 by Leave a Comment

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

Thuật toán:

  • Tìm đường đi ngắn nhất bằng Dijkstra
  • Chắt nhị phân giá trị w
  • Với mỗi giá trị w kiểm tra xem có thỏa mãn không

Code:

#include <iostream>
#include <cmath>
#include <fstream>
#include <bits/stdc++.h>
#define MAXN 502
#define MAXM 30002
#define VC 2000000000
int n, m, dau[MAXM], cuoi[MAXM], t[MAXM], c[MAXM], x[MAXN];
long tro[MAXN];
int ke[2*MAXM];
int qn, q[MAXN], vt[MAXN];
long kc[MAXN], nl[MAXN], ds;
int prev[MAXN];
int tt[MAXN], sl=0;
using namespace std;
int doc()
{
    int i;
    cin >> n;
    for (i=1; i<=n; i++) cin >> x[i];
    cin >> m;
    for (i=1; i<=m; i++) cin >> dau[i] >> cuoi[i] >> t[i] >> c[i];
}
 
// Ham dung do thi
int dungdt()
{
    long u,v;
    int i;
    for (i=1; i<=m; i++) {tro[dau[i]]++; tro[cuoi[i]]++;}
    for (v=0,i=1; i<=n; i++) {u=tro[i]; tro[i]=v+1; v+=u;}
    tro[n+1]=v+1;
    for (i=1; i<=m; i++) {ke[tro[dau[i]]++]=i; ke[tro[cuoi[i]]++]=i;}
    for (i=n; i>=2; i--) tro[i]=tro[i-1]; tro[1]=1;
}
 
// Cac ham quan ly hang doi uu tien
int up(int k)
{
    int v=q[k];
    while (kc[q[k/2]]>kc[v])
    {
        q[k]=q[k/2];
        vt[q[k]]=k;
        k/=2;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int down(int k)
{
    int v=q[k];
    while (2*k<=qn)
    {
        int l=2*k;
        if ((l<qn) && (kc[q[l+1]]<kc[q[l]])) l++;
        if (kc[q[l]]>=kc[v]) break;
        q[k]=q[l];
        vt[q[k]]=k;
        k=l;
    }
    q[k]=v;
    vt[q[k]]=k;
}
int initq() {qn=0; vt[0]=0; kc[0]=-1;}
int put(int u) {q[++qn]=u; vt[u]=qn; up(qn);}
int get() {int kq=q[1]; q[1]=q[qn--]; vt[q[1]]=1; down(1); return kq;}
int update(int u) {int k=vt[u]; up(k);}
int qempty() {return (qn==0);}
 
// Ham dijstra tim khoang cach ngan nhat
int dijstra()
{
    initq();
    kc[1]=0; prev[1]=-(n+1);
    put(1);
    while (!qempty())
    {
        int u=get(); prev[u]=-prev[u];
        tt[++sl]=u;
        for (long i=tro[u]; i<tro[u+1]; i++)
        {
            int v;
            if (dau[ke[i]]!=u) v=dau[ke[i]]; else v=cuoi[ke[i]];
            if ((prev[v]<0) && (kc[v]>kc[u]+t[ke[i]]))
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                update(v);
            }
            if (prev[v]==0)
            {
                kc[v]=kc[u]+t[ke[i]];
                prev[v]=-u;
                put(v);
            }
        }
    }
    return 0;
}
 
 
// Ham kiem tra co di duoc hay khong
int diduoc(long w)
{
    long i,k,u,v,tg,cp,cl;
    for (i=1; i<=n; i++) nl[i]=-VC;
    nl[1]=w;
    for (k=1; k<=sl; k++)
    {
        u=tt[k];
        if (nl[u]>=0)
        for (i=tro[u]; i<tro[u+1]; i++)
        {
            if (dau[ke[i]]!=u) v=dau[ke[i]]; else v=cuoi[ke[i]];
            tg=t[ke[i]]; cp=c[ke[i]];
            if ((kc[v]==kc[u]+tg) && (nl[u]>=cp))
            {
                cl=(x[v]==1) ? w : nl[u]-cp;
                if (cl>nl[v]) nl[v]=cl;
            }
        }
    }
    return (nl[n]>=0);
}
 
// Ham tim chi phi be nhat (dua vao theo tim kiem nhi phan)
int solve()
{
    long first=0, last=1, lim;
    while (!diduoc(last)) {first=last; last*=2;}
    while (last-first>1)
    {
        lim=(last+first)/2;
        if (diduoc(lim)) last=lim; else first=lim;
    }
    ds=last;
}
 
// Ham in ket qua
int viet()
{
    cout << ds;
    //<< // '\n';
    /*out << kc[n] << '\n';
    for (long i=tro[1]; i<tro[2]; i++)
    {
        int v;
        if (dau[ke[i]]!=1) v=dau[ke[i]]; else v=cuoi[ke[i]];
        if (v==n) out << t[ke[i]] << ' ' << c[ke[i]] << '\n';
    } */
    }
 
// CHUONG TRINH CHINH
int main()
{
    doc();
    dungdt();
    dijstra();
    solve();
    viet();
}
Chủ đề: Dijkstra, SPOJ, Tìm kiếm nhị phân Mức độ: ,

CATALAN – SPOJ

June 9, 2016 by Leave a Comment

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

Thuật toán:

  • Bài này sử dụng phương pháp đệ quy có nhớ. Bạn có thể đọc code để hiểu thêm

Code:

const
  fi='';
  fo='';
  maxn=21;
var
  f : array[1..2*maxn,0..2*maxn] of int64;
  i,j,n : longint;
  x,kq2 : array[1..2*maxn] of longint;
  res,kq1,k : int64;
procedure enter;
  begin
    assign(input,fi);reset(input);
    readln(n);
    for i:=1 to 2*n+1 do read(x[i]);
    readln(k);
    close(input);
  end;
function tinh(i,tr : longint) : int64;
  var sl : int64;
  begin
    if f[i,tr]>-1 then exit(f[i,tr]);
    if i>2*n+1 then
      if tr=0 then exit(1) else exit(0);
    sl := 0;
    sl := sl + tinh(i+1,tr+1);
    if tr>0 then
    sl := sl + tinh(i+1,tr-1);
    f[i,tr] := sl;
    exit(sl);
  end;
procedure truyvan1;
  begin
    kq1 := 0;
    for i:=2 to 2*n do
      if x[i]>x[i-1] then
        if x[i]-2>=0 then
          kq1 := kq1 + tinh(i+1,x[i]-2);
    inc(kq1);
  end;
procedure lankq(i : longint);
  begin
    if i>2*n then exit;
    if kq2[i-1]-1>=0 then
      begin
        if k>tinh(i+1,kq2[i-1]-1) then
          begin
            k:=k-tinh(i+1,kq2[i-1]-1);
            kq2[i] := kq2[i-1]+1;
            lankq(i+1);
            exit;
          end;
      end
      else
        begin
          kq2[i] := kq2[i-1]+1;
          lankq(i+1);
          exit;
        end;
    kq2[i] := kq2[i-1]-1;
    lankq(i+1);
  end;
procedure truyvan2;
  begin
    kq2[1] := 0;
    lankq(2);
  end;
procedure process;
  begin
    fillchar(f,sizeof(f),255);
    res := tinh(2,0);
    f[1,0] := res;
    truyvan1;
    truyvan2;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    //writeln(res);
    writeln(kq1);
    for i:=1 to 2*n+1 do write(kq2[i],' ');
    close(output);
  end;
begin
  enter;
  process;
  print;
end.
Chủ đề: Đệ quy có nhớ, Phương pháp, SPOJ

MINCUT – SPOJ

June 4, 2016 by Leave a Comment

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

Thuật toán:

  • Với mỗi cách cắt ngang, cắt dọc. Ta chặt nhị phân tìm nhát cắt sao cho độ chênh lệch 2 phần nhỏ nhất.
  • Chú ý với mỗi cách cắt ta phải chặt nhị phân 2 lần: value >= trunggian và value <= trunggian
  • Các bạn có thể đọc code để hiểu rõ hơn

Code:

uses    math;
const   fi='';
        fo='';
        maxn=trunc(1e3)+3;
        oo=trunc(1e15);
type    data=record
                x,y,u,v:longint;
                end;
var     m,n,i,j,k:longint;
        s:array[0..maxn,0..maxn] of int64;
        a:array[1..maxn,1..maxn] of longint;
        q:array[1..maxn*maxn] of data;
        res     :int64;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n,k);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    for i:=1 to k do
        with q[i] do
                read(x,y,u,v);
    close(input);
end;
procedure init;
begin
    for i:=1 to m do
        for j:=1 to n do s[i,j]:=s[i-1,j]+s[i,j-1]-s[i-1,j-1]+a[i,j];
end;
function tinh(x,y,u,v:longint):int64;
begin
        exit(s[u,v]+s[x-1,y-1]-s[x-1,v]-s[u,y-1]);
end;
procedure solve;
var     tam,tam2        :int64;
        d,c,g   :longint;
begin
assign(output,fo);rewrite(output);
    for i:=1 to k do
      with q[i] do
        begin
            tam:=tinh(x,y,u,v);
            tam2 := tam div 2;
            res := oo;
            // cat hang
            d :=x; c:=u-1;
            g := (d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,g,v)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=c downto d do
                if tinh(x,y,g,v)<=tam2 then
                        begin
                                res := min(res,tam-2*tinh(x,y,g,v));
                        end;
            d:=x; c:=u-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,g,v)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=d to c do
                if tinh(x,y,g,v)>=tam2 then
                        begin
                                res := min(res,2*tinh(x,y,g,v)-tam);
                        end;
            // cat cot;
            d:=y; c:=v-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,u,g)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=c downto d do
                if tinh(x,y,u,g)<=tam2 then
                        begin
                                res := min(res,tam-2*tinh(x,y,u,g));
                        end;
            d:=y; c:=v-1;
            g:=(d+c) div 2;
            while (g<>d) and (g<>c) do
                begin
                        if tinh(x,y,u,g)>=tam2 then c:=g else d:=g;
                        g:=(d+c) div 2;
                end;
            for g:=d to c do
                if tinh(x,y,u,g)>=tam2 then
                        begin
                                res := min(res,2*tinh(x,y,u,g)-tam);
                        end;
            writeln(res);
        end;
end;
begin
    nhap;
    init;
    solve;
end.
Chủ đề: SPOJ, Tìm kiếm nhị phân Mức độ:

VMKEY – SPOJ

May 24, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

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++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
int d[100][100];
int w[100][100];
string s;
typedef pair<int, int> ii;
int x[101];
ii p[110];
vector< ii > v;
int pos[11];
int dist[100][100];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("vao.inp", "r", stdin);
    freopen("ra.out", "w", stdout);
    #endif //MIKELHPDATKE
   // cout<<"wtf"<<endl;
    FORE(i, 1, 9) x[i] = i;
    x[10] = 0;
    cin >> s;
    //cout<<s<<endl;
    FOR(i, 0, s.size() - 1){
        d[s[i] - '0'][s[i + 1] - '0']++;
        if (d[s[i] - '0'][s[i + 1] - '0'] == 1) v.push_back(ii(s[i] - '0', s[i + 1] - '0'));
    }
 
    p[1].first = 1; p[1].second = 1;
    p[2].first = 1; p[2].second = 2;
    p[3].first = 1; p[3].second = 3;
    p[4].first = 2; p[4].second = 1;
    p[5].first = 2; p[5].second = 2;
    p[6].first = 2; p[6].second = 3;
    p[7].first = 3; p[7].second = 1;
    p[8].first = 3; p[8].second = 2;
    p[9].first = 3; p[9].second = 3;
    p[10].first = 4; p[10].second = 1;
    FORE(u, 1, 10) FORE(v, 1, 10) dist[u][v] = abs(p[u].first - p[v].first) + abs(p[u].second - p[v].second);
    int ans = INF;
    //FOR(i, 0, s.size() - 1) ans += dist[s[i] - '0'][s[i + 1] - '0'] * d[s[i] - '0'][s[i + 1] - '0'];
    while (next_permutation(x + 1, x + 11)){
        int sum = 0;
        FORE(i, 1, 10) pos[x[i]] = i;
        FOR(i, 0, v.size()){
            int u = v[i].first, vv = v[i].second;
            sum += dist[pos[u]][pos[vv]] * d[u][vv];
        }
        ans = min(ans, sum);
    }
    cout << ans;
    return 0;
}
Chủ đề: SPOJ Mức độ:

NKCITY – SPOJ

May 24, 2016 by Leave a Comment

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

Thuật toán:

  • Giải bài này có thể sử dụng thuật toán Prim hoặc thuật toán Kruskal đều được.
  • Các bạn có thể tham khảo cả 2 cách làm ở bên dưới.

Code:

Kruskal

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;
        maxm    =10000;
 
type    data    =record
                u, v, c :longint;
                end;
 
var     f       :Text;
        n, m    :longint;
        Edges   :array[1..maxm] of Data;
        b       :Array[1..maxm] of longint;
        Father  :Array[1..maxn] of longint;
        res     :longint;
procedure nhap;
var     i, u, v, c :longint;
begin
        assign(f, fi);
        reset(f);
        readln(f, n, m);
        for i:=1 to m do
                begin
                        readln(f, u, v, c);
                        Edges[i].u:=u;
                        Edges[i].v:=v;
                        Edges[i].c:=c;
                end;
        close(f);
end;
 
Procedure init;
var     i :longint;
begin
        for i:=1 to m do b[i]:=i;
        for i:=1 to n do father[i]:=-1;
        res:=-1;
end;
 
procedure QS(l,r:longint);
var     i, j, x, tg     :longint;
begin
        i:=l;
        j:=r;
        x:=edges[b[ (l+r) div 2] ].c;
        repeat
                while Edges[b[i]].c < x do inc(i);
                while Edges[b[j]].c > x do dec(j);
                if i<=j then
                        begin
                                tg:=b[i];
                                b[i]:=b[j];
                                b[j]:=tg;
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l<j then QS(l,j);
        if i<r then QS(i,r);
end;
 
function find(i:longint):longint;
var     t       :longint;
begin
        t:=i;
        while father[t]>0 do t:=father[t];
        exit(t);
end;
 
procedure union(i, j:longint);
var     x :longint;
begin
        x:=father[i]+father[j];
        if father[i]>father[j] then
                begin
                        father[i]:=j;
                        father[j]:=x;
                end
        else    begin
                        father[j]:=i;
                        father[i]:=x;
                end;
end;
 
procedure Kruskal;
var     i, u,v, c, r1, r2 :longint;
begin
        init;
        QS(1,m);
        for i:=1 to m do
                begin
                        u:=Edges[b[i]].u;
                        v:=Edges[b[i]].v;
                        c:=Edges[b[i]].c;
                        r1:=find(u);
                        r2:=find(v);
                        if r1<>r2 then
                                begin
                                        union(r1,r2);
                                        res:=max(res,c);
                                end;
                end;
end;
 
procedure xuat;
begin
        assign(f, fo);
        rewrite(f);
        writeln(f, res);
        close(f);
end;
 
BEGIN
        nhap;
        Kruskal;
        xuat;
END.

Prim

const   fi='';
        fo='';
        maxn=1000;
        maxc=trunc(1e9);
var     d:array[1..maxn] of longint;
        i,j,n,m,res:longint;
        u,v,t:longint;
        cx:array[1..maxn] of boolean;
        c:array[1..maxn,1..maxn] of longint;
procedure init;
begin
    for i:=1 to n do d[i]:=maxc;
    d[1]:=0;
    fillchar(cx,sizeof(cx),true);
end;
procedure prim;
var     min,u:longint;
begin
        repeat
                min:=maxc;u:=0;
                for i:=1 to n do
                        if cx[i] then
                        if d[i]<min then
                                begin
                                    min:=d[i];
                                    u:=i;
                                end;
                if (u=0) then exit;
                cx[u]:=false;
                if d[u]>res then res:=d[u];
                for v:=1 to n do
                        if cx[v] then
                                if d[v]>c[u,v] then
                                        begin
                                            d[v]:=c[u,v];
                                        end;
        until false;
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
    readln(n,m);
    for i:=1 to n do
        for j:=1 to n do
                if i<>j then c[i,j]:=maxc else c[i,j]:=0;
    for i:=1 to m do
        begin
            readln(u,v,t);
            c[u,v]:=t;
            c[v,u]:=t;
        end;
    init;
    prim;
    writeln(res);
    close(input);close(output);
end.
Chủ đề: Kruskal, Prim, SPOJ Mức độ: , ,

VMRESTO – SPOJ

May 24, 2016 by Leave a Comment

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

Thuật toán:

  • Thuật toán bài này khá đơn giản. Bạn có thể đọc code của mình bên dưới, mình viết code cũng khá dễ đọc.

Code:

const   fi='';
        fo='';
        maxn=100;
var     hang,cot:array[1..maxn] of int64;
        cheo,n,i,j,k:longint;
        a:array[1..maxn,1..maxn] of int64;
        res,hold:int64;
procedure nhap;
begin
    assign(input,fi);reset(input);
 
    readln(n);
    for i:=1 to n do
        for j:=1 to n do read(a[i,j]);
 
    close(input);
end;
procedure init;
begin
    for i:=1 to n do
        for j:=1 to n do
                begin
                        inc(hang[i],a[i,j]);
                        inc(cot[j],a[i,j]);
                end;
end;
procedure xuly;
begin
    hold:=0;
    for i:=2 to n do
      begin
        a[i,i]:=hang[1]-hang[i];
        inc(hold,a[i,i]);
      end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(Output);
    res:=(hang[1]-hold) div (n-1);
    for i:=1 to n  do
        begin
            for j:=1 to n do
                if i<>j then write(a[i,j],' ') else write(res+a[i,j],' ');
            writeln;
        end;
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.
Chủ đề: SPOJ Mức độ:

BGBOARD – SPOJ

May 24, 2016 by 2 Comments

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

Thuật toán:

  • (đang cập nhập)

Code:

#include <iostream>
#include <fstream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <list>
#include <iomanip>
#include <math.h>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <climits>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <sstream>
 
using namespace std;
 
#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <double> vd;
typedef vector <string> vs;
typedef map <string, int> mpsi;
typedef map <double, int> mpdi;
typedef map <int, int> mpii;
 
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
 
template <class T> inline T abs1(T a) {return a < 0 ? -a : a;}
 
template <class T> inline T max1(T a, T b) { return a > b ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
 
inline int jud(double a, double b){
	if(abs(a) < eps && abs(b) < eps) return 0;
	else if(abs1(a - b) / abs1(a) < eps) return 0;
	if(a < b) return -1;
	return 1;
}
template <typename t> inline int jud(t a, t b){
	if(a < b) return -1;
	if(a == b) return 0;
	return 1;
}
 
// f_lb == 1��?����ͬ��һ������߽磬f_small == 1��?�����û��Ѱ�ҵ�ֵ����С����
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1){
	int be = 0, en = na - 1;
	if(*a <= *(a + na - 1)){
		if(f_lb == 0) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != 1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != -1) en = mid;
			else be = mid + 1;
		}
		if(f_small && jud(*(a + be), val) == 1) be--;
		if(!f_small && jud(*(a + be), val) == -1) be++;
	} else {
		if(f_lb) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != -1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != 1) en = mid;
			else be = mid + 1;
		}
		if(!f_small && jud(*(a + be), val) == -1) be--;
		if(f_small && jud(*(a + be), val) == 1) be++;
	}
	return be;
}
 
 
 
template <class T> inline T lowb(T num) {return num & (-num); }
inline int bitnum(ui nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(ull nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitnum(ll nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitmaxl(ui a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(int a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(ull a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
inline int bitmaxl(ll a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
 
long long pow(long long n, long long m, long long mod = 0){
	if(m < 0) return 0;
	long long ans = 1;
	long long k = n;
	while(m){
		if(m & 1) {
			ans *= k;
			if(mod) ans %= mod;
		}
		k *= k;
		if(mod) k %= mod;
		m >>= 1;
	}
	return ans;
}
 
//#define debug
//.........................��.......��.......��.......��.......��.......ֹ.......hack...............................................
 
const int maxn = 5000;
int dp[maxn][maxn];
int arr[maxn][maxn];
mpii biao[maxn * maxn];
int n, m;
 
int main(){
    ios_base::sync_with_stdio(0);
	#ifdef debug //......................................................................................................
	freopen("input.txt", "r", stdin);
	#endif //...........................................................................................................
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
		scanf("%d", arr[i] + j);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		 for(int j = 0; j < m; j++) {
			 mpii :: iterator it;
			 it = biao[arr[i][j]].begin();
			 for(; it != biao[arr[i][j]].end(); it++) {
				 int a = it->first, b = j;
				 if(a > b) swap(a, b);
				 dp[a][b] = max(it->second, dp[a][b]);
			 }
			 biao[arr[i][j]][j] = i + 1;
		 }
		 for(int j = 1; j < m; j++) for(int k = 0; k < m - j; k++)
			 dp[k][k + j] = max1(dp[k][k + j], dp[k][k + j - 1], dp[k + 1][k + j]);
		 for(int j = 0; j < m; j++) for(int k = j; k < m; k++) {
			 ans = max1(ans, (i - dp[j][k] + 1) * (k - j + 1));
		 }
	}
	cout << ans << endl;
    return 0;
}
Chủ đề: Quy hoạch động, SPOJ