Đề bài:

• http://vn.spoj.com/problems/BONUS13/

Thuật toán:

• Xem

Code:

• Pascal
• C++

uses    math;
const   fi='';
        fo='';
        maxn=80;
        n=8;
        hx:array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);
        hy:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2);
type    point=record
                x,y:byte;
                end;
var     cx,dx:array[1..maxn] of point;
        a:array[1..8,1..8] of boolean;
        c:array[1..maxn] of longint;
        i,j,k:longint;
        top1,top2:longint;
        hau,xe,ma,tuong:array[1..maxn,1..maxn] of boolean;
        m,t,x,h : longint;
        res:int64;
procedure nhap;
var     u,v:byte;
        w:longint;
begin
    assign(input,fi);reset(input);
    readln(k);
    for i:=1 to k do
        begin
            readln(u,v,w);
            a[u,v]:=true;
            inc(top1); dx[top1].x:=u; dx[top1].y:=v; c[top1]:=w;
        end;
    close(input);
end;
procedure init;
begin
    res:=0;
    for i:=1 to 8 do
        for j:=1 to 8 do
                if a[i,j]=false then
                        begin
                               inc(top2);
                               cx[top2].x:=i;
                               cx[top2].y:=j;
                        end;
end;
function chau(i,j:longint):boolean;
begin
    if cx[i].x=dx[j].x then exit(true);
    if cx[i].y=dx[j].y then exit(true);
    if (cx[i].x+cx[i].y)=(dx[j].x+dx[j].y) then exit(true);
    if (cx[i].x-cx[i].y)=(dx[j].x-dx[j].y) then exit(true);
    exit(false);
end;
function cxe(i,j:longint):boolean;
begin
    if cx[i].x=dx[j].x then exit(true);
    if cx[i].y=dx[j].y then exit(true);
    exit(false);
end;
function ctuong(i,j:longint):boolean;
begin
    if (cx[i].x+cx[i].y)=(dx[j].x+dx[j].y) then exit(true);
    if (cx[i].x-cx[i].y)=(dx[j].x-dx[j].y) then exit(true);
    exit(false);
end;
function cma(i,j:longint):boolean;
var     k,u,v:integer;
begin
    for k:=1 to 8 do
        begin
            u:=cx[i].x+hx[k];
            v:=cx[i].y+hy[k];
            if (u=dx[j].x) and (v=dx[j].y) then exit(true);
        end;
    exit(false);
end;
procedure xuly;
var     i,j:longint;
begin
    for i:=1 to top2 do
        for j:=1 to top1 do
         begin
          if chau(i,j) then hau[i,j]:=true;
          if cxe(i,j) then xe[i,j]:=true;
          if cma(i,j) then ma[i,j]:=true;
          if ctuong(i,j) then tuong[i,j]:=true;
         end;
end;
procedure main;
var     tam:int64;
begin
    for h:=1 to top2 do
        for x:=1 to top2 do
                if h<>x then
                        for m:=1 to top2 do
                                if (m<>h) and (m<>x) then
                                        for t:=1 to top2 do
                                                if (m<>t) and (t<>x) and (t<>h) then
                                                  begin
                                                        tam:=0;
                                                        for i:=1 to top1 do
                                                                if hau[h,i] or xe[x,i] or ma[m,i] or tuong[t,i] then tam := tam + c[i];
                                                        res:=max(res,tam);
                                                  end;

end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    main;
    inkq;
end.

#include 
#include 
using namespace std;
#define LL long long
#define rep(i, a, b) for (int i=a; i& a) {
    LL res = 0;
    for (auto &x: a) {
        if (state & 1) res += x.w;
        state >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m; cin >> m;
    vector a(m);
    vector frei(64, true);
    for (auto &a: a) {
        cin >> a.x >> a.y >> a.w;
        a.x--, a.y--;
        frei[a.x*8+a.y] = false;
    }
    vector xe(64, 0), tuong(64, 0), ma(64, 0), hau(64, 0);
    int c = 0;
    rep(i, 0, 8) rep(j, 0, 8) if (frei[c]) {
        rep(k, 0, m) {
            int x = a[k].x, y = a[k].y;
            if (x==i || y==j) xe[c] |= 1ll<

Đề bài:

• http://vn.spoj.com/problems/C11CAVE/

Thuật toán:

• Chỉ cần duyệt từ 1 đến h rồi kiểm tra, bạn đọc code bên dưới sẽ hiểu.

Code:

• Pascal

    const           fi      = '';
                    fo      = '';
                    maxn    = 1000000;

    var
                    n , h   : longint;
                    m       : longint;
                    d , c   : array[ 0..maxn ] of longint;

    procedure   enter;
        var
                i           : longint;
                u , v       : longint;
        begin
                read( n , h );
                m := n div 2;
                for i := 1 to m do
                  begin
                    read( u , v );
                    inc( d[ u ] );
                    inc( c[ v ] );
                  end;
        end;

    procedure   prepair;
        var
                i           : longint;
        begin
                for i := 1 to h do
                  begin
                    d[ i ] := d[ i-1 ] + d[ i ];
                    c[ i ] := c[ i-1 ] + c[ i ];
                  end;
        end;


    procedure   solve;
        var
                res , num   : longint;
                i , tmp     : longint;
        begin
                res := n+1;
                num := 0;
                for i := 1 to h do
                  begin
                    tmp := d[ h ] - d[ i-1 ] + c[ h ] - c[ h-i ];
                    if res > tmp then
                      begin
                        res := tmp;
                        num := 1;
                      end
                    else
                      if res = tmp then inc( num );
                  end;
                writeln( res , ' ' , num );
        end;



    BEGIN

                assign( input , fi ); reset( input );
                assign( output , fo ); rewrite( output );

                enter;
                prepair;
                solve;

                close( input ); close( output );

    END.