NKGOLF – SPOJ

April 29, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cmath>
#include <algorithm>
#include <string>
#include <map>
#include <set>
#include <vector>
#include <stack>
#include <deque>
#include <queue>
#include <utility>
#include <sstream>
using namespace std;
 
#define FOR(i,a,b) for(int i = (a); i <= (b); i++)
#define DOW(i,a,b) for(int i = (a); i >= (b); i--)
#define RESET(c,val) memset(c,val,sizeof(c))
#define sz(a) int(a.size())
#define pb push_back
 
typedef long long ll;
typedef unsigned long long ull;
 
/*---------------------------*/
 
const int maxn = 1e3 + 2;
int m, n, res, tt;
ll a[maxn][maxn];
bool b[maxn][maxn];
 
void input() {
    scanf("%d %d", &m, &n);
    RESET(a,0);
    FOR(i,1,m)
    FOR(j,1,n)
    scanf("%lld", &a[i][j]);
}
 
void solve() {
    FOR(i,1,m-1)
    FOR(j,1,n-1)
    b[i][j]=((a[i][j]<=a[i+1][j]) && (a[i][j]<=a[i][j+1])
             && (a[i+1][j]<=a[i+1][j+1]) && (a[i][j+1]<=a[i+1][j+1]));
 
    res=1;
    // search row
    FOR(i,1,m) {
        tt=1;
        FOR(j,2,n)
        if ( a[i][j]>=a[i][j-1] ) {
            tt++;
            res=max(res,tt);
        } else tt=1;
    }
 
    // search col
    FOR(j,1,n) {
        tt=1;
        FOR(i,2,m)
        if ( a[i][j]>=a[i-1][j] ) {
            tt++;
            res=max(res,tt);
        } else tt=1;
    }
 
    int h[maxn], l[maxn], r[maxn];
    RESET(h,0);
    RESET(l,0);
    RESET(r,0);
    FOR(i,1,m-1) {
        FOR(j,1,n-1)
        if ( b[i][j] ) h[j]++;
        else h[j]=0;
 
        //deque
        int d[maxn];
        int top=0;
        d[0]=0;
        FOR(j,1,n-1) {
            while(top && h[j]<=h[d[top]])
                r[d[top--]]=j-1;
            l[j]=d[top]+1;
            d[++top]=j;
        }
        while(top) r[d[top--]]=n-1;
 
        FOR(j,1,n-1)
        if ( h[j]>0 ) {
            res=max(res,(h[j]+1)*(r[j]-l[j]+2));
        }
    }
}
 
void output() {
    printf("%d", res);
}
 
int main() {
    input();
    solve();
    output();
 
    return 0;
}
Chủ đề: SPOJ, Thuật toán Mức độ: ,

CTNOWN – SPOJ

April 29, 2016 by Leave a Comment

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

Thuật toán:

  • (đang cập nhập)

Code:

uses    math;
const   fi='';
        fo='';
        maxn=350;
var     n,i,j   :longint;
        dem     :longint;
        nto     :array[1..maxn] of longint;
        cx      :array[1..maxn] of boolean;
        f       :array[0..maxn,0..maxn] of qword;
        t,tt,k    :longint;
        res,tam     :qword;
procedure sangnto;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxn)) do
                if cx[i]=false then
                        begin
                                j := i*i;
                                while (j<=maxn) do
                                        begin
                                                cx[j]:=true;
                                                j := j+i;
                                        end;
                        end;
        for i:=2 to maxn do
                if cx[i]=false then
                        begin
                                inc(dem);
                                nto[dem] := i;
                        end;
end;
function max(x,y : qword) : qword;
  var tg : qword;
  begin
    if x>y then exit(x) else exit(y);
  end;
procedure main;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
        sangnto;
        read(t);
                for i:=0 to dem do
                  for j:=0 to maxn do f[i,j] := 1;
                        for i:=1 to dem do
                                begin
                                        for j:=1 to maxn do
                                        begin
                                        f[i,j] := f[i-1,j];
                                        tam:=1;
                                        while tam*nto[i]<=j do
                                                begin
                                                        tam := tam * nto[i];
                                                        f[i,j] := max(f[i,j], f[i-1,j-tam]*tam );
                                                end;
                                        end;
                                end;
        for tt := 1 to t do
                begin
                        read(n);
                        writeln(f[dem,n]);
                end;
        close(input);close(output);
end;
procedure __;
begin
end;
begin
  __ ;
  main;
  __ ;
end.
Chủ đề: Quy hoạch động, SPOJ, Thuật toán Mức độ:

DHFRBUS – SPOJ

April 18, 2016 by Leave a Comment

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

Thuật toán:

  • Sử dụng thuật toán tìm đường đi ngắn nhất dijkstra.
  • Gọi d[u,x] là quãng đường ngắn nhất đi từ s đến u khi dùng x vé xe miến phí
  • Kết quả là d[t,k].

Code:

{$inline on}
 
const   fi      ='';
        fo      ='';
        maxN    =trunc(1e5)*2;
        maxM    =trunc(1e5)*10;
        maxK    =5;
        oo       =2*trunc(1e12);
type    Tadj    =record
                v,w,link:int64;
        end;
 
        THeap   =record
                v1,v2:int64;
        end;
 
        Arr1    =array[0..maxN] of int64;
        Arr2    =array[0..maxM] of Tadj;
        Arr4    =array[0..maxN*maxK] of THeap;
        Arr5    =array[0..maxN,0..maxK] of int64;
 
var     n, m, k :longint;
        Adj     :arr2;
        Head    :arr1;
        s, t    :longint;
        d       :arr5;
        Pos     :arr5;
        H       :arr4;
        nHeap   :longint;
        c       :longint;
//heapmin;
procedure hv(var a, b:int64);
var     tg      :int64;
begin
        tg:=a;a:=b;b:=tg;
end;
 
procedure UpHeap(i:longint);
begin
 
        if (i<=1) or (d[H[i div 2].v1,H[i div 2].v2]<=d[H[i].v1,H[i].v2]) then exit;
        hv(Pos[H[i div 2].v1,H[i div 2].v2],Pos[H[i].v1,H[i].v2]);
        hv(H[i div 2].v1,H[i].v1);
        hv(H[i div 2].v2,H[i].v2);
        UpHeap(i div 2);
end;
 
procedure DownHeap(i:longint);
var     j :longint;
begin
        j:=i*2;
        if j>nHeap then exit;
        if (j<nheap) and (d[H[j+1].v1,H[j+1].v2]<d[H[j].v1,H[j].v2]) then inc(j);
        if d[H[i].v1,H[i].v2]<=d[H[j].v1,H[j].v2] then exit;
        hv(Pos[H[i].v1,H[i].v2],Pos[H[j].v1,H[j].v2]);
        hv(H[i].v1,H[j].v1);
        hv(H[i].v2,H[j].v2);
        DownHeap(j);
end;
 
procedure Update(u,x:longint);
var     p :longint;
begin
        p:=pos[u,x];
        if p=0 then
                begin
                        inc(nHeap);
                        H[nheap].v1:=u;
                        H[nheap].v2:=x;
                        Pos[u,x]:=nHeap;
                        p:=nHeap;
                end;
        UpHeap(p);
end;
 
procedure GetMin(var u, x:longint);
begin
        if nheap=0 then
                begin
                        u:=0;x:=0;
                        exit;
                end;
        u:=H[1].v1;x:=H[1].v2;
        H[1].v1:=H[nHeap].v1;
        H[1].v2:=H[nheap].v2;
        Pos[H[1].v1,H[1].v2]:=1;
        dec(nHeap);
        downHeap(1);
end;
 
procedure Dijkstra;
var      i, v, w      :int64;
        ans     :int64;
        u     ,x  :longint;
begin
        fillchar(pos,n,0);
        for u:=1 to n do
                for x:=0 to k do d[u,x]:=oo;
        nHeap:=0;
        d[s,0]:=0;
        Update(s,0);
        repeat
                GetMin(u,x);
                i:=head[u];
                if u=0 then exit;
                while i<>0 do
                begin
                        v:=adj[i].v;
                        w:=adj[i].w;
                        if d[v,x]>d[u,x]+w then
                        begin
                                d[v,x]:=d[u,x]+w;
                                Update(v,x);
                        end;
                        if (x<k) and (d[v,x+1]>d[u,x]) then
                        begin
                                d[v,x+1]:=d[u,x];
                                Update(v,x+1);
                        end;
                        i:=adj[i].link;
                end;
        until nHeap=0;
        ans:=oo;
        ans:=d[t,k];
        {for x:=0 to k do
                if d[t,x]<ans then
                                ans:=d[t,x];}
        writeln(ans);
end;
 
procedure Tadd(u,v,w:longint);
begin
        inc(c);
        Adj[c].v:=v;
        Adj[c].w:=w;
        Adj[c].link:=head[u];
        head[u]:=c;
end;
 
procedure xuly;
var     i, u, v, w      :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n, m, k, s, t);
        c:=0;
        fillchar(head,sizeof(head),0);
        for i:=1 to m do
                begin
                        readln(u,v,w);
                        Tadd(u,v,w);
                        Tadd(v,u,w);
                end;
        Dijkstra;
        close(input);close(output);
end;
 
begin
        xuly;
end.
Chủ đề: Dijkstra, SPOJ, Thuật toán Mức độ: , , , ,

SPOJ – DHLOCK

April 18, 2016 by Leave a Comment

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

Thuật toán:

  • Bài này không quá khó. Ta chỉ cần duyệt số lần sử dụng cách biến đổi khóa thứ 2 là kk (kk=0..n-1,) với mỗi giá trị kk ta tính số lần ít nhất sử dụng phép biến đổi 1,3 để thỏa.

Code:

const   fi='';
        fo='';
        maxn=300;
var     i,j,n,k:longint;
        kiluc,kq,tam:longint;
        a,b,c:array[1..maxn] of longint;
procedure xuly;
var     kk:longint;
        tmp:longint;
begin
        for kk:=0 to n-1 do
        begin
            for i:=1 to n do
            begin
                if i+kk>n then tam:=(i+kk) mod n else tam:=i+kk;
                if b[tam]>=a[i] then c[i]:=b[tam]-a[i]
                        else c[i]:=b[tam]+k-a[i]+1;
            end;
            for i:=1 to n do
                begin
                    kq:=0;
                    tam:=c[i];
                    for j:=1 to n do
                        if c[j]>=tam then inc(kq,c[j]-tam)
                                else inc(kq,c[j]+k-tam+1);
                    if kq+kk+tam<kiluc then kiluc:=kq+kk+tam;
                end;
        end;
end;
procedure init;
begin
    for i:=1 to n do
        if b[i]>=a[i] then inc(kiluc,b[i]-a[i])
                else inc(kiluc,b[i]+k-a[i]+1);
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
 
    readln(n,k);
    for i:=1 to n do read(a[i]);
    for j:=1 to n do read(b[j]);
 
    init;
    xuly;
 
    writeln(kiluc);
 
    close(input);close(output);
end.
Chủ đề: SPOJ, Thuật toán, Vét cạn Mức độ: , ,

NKPALIN – SPOJ

April 3, 2016 by 2 Comments

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

Thuật toán:

Gọi F[i][j] là độ dài xâu đối xứng dài nhất trong đoạn S[i..j]. Khi đó:

  1. F[i,j] = F[i+1,j-1]+2 nếu S[i] = S[j]
  2. F[i,j] = max(F[i+1,j],F[i,j-1]) nếu S[i] <> S[j]

Bạn có thể đọc code bên dưới để hiểu hơn.

Code:

Program Xaucon;
Var s,st,st1:ansistring;
    i,j:integer;
    F: Array[1..2000,1..2000] Of Integer;
 
Procedure nhap;
 Begin
  Readln(s);
  For i:=1 to length(s) do F[i,i]:=1;
  Writeln;Writeln;
 end;
 
Function max(a,b:integer):integer;
 Begin
  If a>b then exit(a) else exit(b);
 End;
 
 
Procedure Solve;
 Begin
  For i:=length(s) downto 1 do
   For j:=i+1 to length(s) do
     If s[i]=s[j] then
         F[i,j]:=F[i+1,j-1]+2
     else F[i,j]:= max(F[i+1,j],F[i,j-1]);
   End;
 
Procedure PrintResult;
 Begin
  i:=1;
  j:=length(s);
    While (i<=j) do
    Begin
     If s[i]=s[j] then
       Begin
         st:=st+s[i];
         st1:=s[j]+st1;
         inc(i);
         dec(j);
       end
     Else
       If F[i+1,j]=F[i,j] then inc(i) else dec(j);
    End;
     If F[1,length(s)] mod 2 =1 then delete(st1,1,1);
    st:=st+st1;
  Writeln(st);
  end;
 
 Begin
 nhap;
 Solve;
 PrintResult;
readln
end.
Chủ đề: Phương pháp, Quy hoạch động, SPOJ Mức độ: ,

CREC01 – SPOJ

April 3, 2016 by Leave a Comment

đề bài: http://vn.spoj.com/problems/CREC01/

Thuật toán:

  • Bài này ta sử dụng kỹ thuật deque. Thuật toán cũng không có gì phức tạp. Bạn có thể đọc code bên dưới để hiểu thêm

Code:

Pascal:

const   fi      ='';
        fo      ='';
        oo      =1000;
 
var     a       :array[0..oo,0..oo] of 0..1;
        l,h,dem:array[0..oo+1] of int64;
        m, n    :longint;
 
procedure Optimize;
var     i, j    :longint;
        ans     :int64;
begin
        fillchar(h, sizeof(h),0);
        ans:=0;
        for i:=1 to m do
                begin
                        for j:=1 to n do
                                begin
                                        if a[i,j]=1 then begin
                                        l[j]:=j;
                                        h[j]:=h[j]+1;
                                        while h[l[j]-1]>h[j] do
                                                l[j]:=l[l[j]-1];
                                        dem[j]:=h[j]*(j-l[j]+1)+dem[l[j]-1];
                                        ans:=ans+dem[j];
                                        //writeln(ans,'==');
                                        //if (i=3) and (j=2) then writeln(dem[1]);
                                        end
                                        else begin
                                                dem[j]:=0;
                                                l[j]:=0;
                                                h[j]:=0;
                                        end;
 
                                end;
 
                end;
        writeln(ans);
end;
 
procedure run;
var     i, j, tg    :longint;
        s       :ansistring;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                        readln(s);
                        for j:=1 to n do
                                        val(s[j],a[i,j]);
                end;
        Optimize;
        close(input);close(output);
 
end;
 
begin
        run;
end.

C++:

using namespace std;
#include<bits/stdc++.h>
 
#define BG begin()
#define ED end()
#define st first
#define nd second
#define PB push_back
#define PF push_front
#define FOR(i,a,b) for (long long i=a;i<b;i++)
#define FORE(i,a,b) for (long long i=a;i<=b;i++)
#define FORD(i,a,b) for (long long i=a;i>=b; i--)
#define ri(n)({
    int neg=0;
    n=0;
    char ch;
    for(ch=getchar(); ch<'0' || ch>'9'; ch=getchar()) if (ch=='-') neg=1-neg;
    n=ch-48;
    for(ch=getchar(); ch>='0' && ch<='9'; ch=getchar()) n=(n<<3)+(n<<1)+ch-48;
    if (neg) n=-n;
})
 
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> II;
typedef pair<ll,ll> LL;
const ll INF=1000000000+7;
const double esp=1e-13;
const double pi=3.141592653589;
 
 
ll m, n, a[1001][1001], H[1001], dem[1001], L[1001];
 
int main()
{
    //freopen("CREC01.inp", "r", stdin);
    //freopen("CREC01.out", "w", stdout);
    cin>>m>>n;
    char ch;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            cin>>ch;
            a[i][j] = ch - '0';
        }
    memset(H, 0, sizeof(H));
    memset(L, 0, sizeof(L));
    memset(dem, 0, sizeof(dem));
    long long ans = 0;
    FORE(i, 1, m)
        FORE(j, 1, n) {
            //cout<<i<<" "<<j<<" "<<a[i][j]<<endl;
            if (a[i][j] == 1) {
                H[j]++;
                int k = j;
                while ( (k > 1) && (a[i][k-1] == 1) && (H[ k - 1 ] >= H[j]) ) k = L[k - 1];
                L[j] = k;
                dem[j] = H[j]*(j - L[j] + 1) + dem[L[j] - 1];
                ans += dem[j];
                //cout<<i<<"=="<<j<<"=="<<"=="<<H[j]<<"=="<<ans<<endl;
            }
            else
            {
                H[j] = 0;
                dem[j]= 0;
                L[j] = 0;
            }
        }
    cout<<ans;
}
Chủ đề: SPOJ Mức độ: