NKSGAME – spoj

Đề bài:

Thuật toán:

Bài yêu cầu với mỗi số \(b[i]\) tìm \(c[j]\) sao cho \(|b[i]+c[j]|\) nhỏ nhất. Suy ra chọn sao cho \(b[i]+c[j]\) có giá trị gần \(0\) nhất

Thuật toán sẽ là:

  1. Sắp xếp lại mảng \(c[]\).
  2. Với mỗi \(b[i]\) tìm kiếm nhị phân \(c[j]\) thỏa mãn \(b[i]+c[j]\) có giá trị gần \(0\) nhất.

Nếu chưa hiểu rõ bạn có thể xem code bên dưới.

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
const int maxn = 100009;
const int oo = 2000000009;
int i, j, n, ans, tmp, b[maxn], a[maxn];
 
bool cmp (int x, int y) {
     return(x < y);
}
 
int main() {
    cin >> n;
    for (i = 1; i <= n; i++) cin >> a[i];
    for (i = 1; i <= n; i++) cin >> b[i];
    sort (b+1, b+n+1, cmp);
    ans = oo;
    for (i = 1; i <= n; i++) {
        tmp = lower_bound(b+1,b+n+1,0-a[i]) - b;
        if (tmp > n) tmp = n;
        ans = min(ans, abs(a[i] + b[tmp]));
        if (tmp == 1) continue;
        ans = min(ans, abs(a[i] + b[tmp-1]));
    }
    cout << ans;
    return 0;
}

C11TRCNT – spoj

Đề bài:

Thuật toán:

  • Bài toán đưa về: kiểm tra 3 điểm có thẳng hàng hay không

Code:

const   fi='';
        fo='';
type    dinh=record
                x,y:longint;
                end;
var     i,j,k:integer;
        d,max,min:int64;
        kq,n:byte;
        p:array[1..200] of dinh;
        dem:array[1..200] of int64;
        f:text;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,n);
    for i:=1 to n do readln(f,p[i].x,p[i].y);
    close(f);
end;
function kt(x1,y1,x2,y2,x3,y3:longint):boolean;
begin
        if x1*y3-x1*y2+x2*y1-x2*y3+x3*y2-x3*y1=0
        then exit(false) else exit(true);
end;
procedure xuly;
begin
    d:=0; min:=1000000000000000;
    for i:=1 to n do
    begin
        for j:=1 to n do
        if i<>j then
                for k:=1 to n do
                if (i<>k) and (j<>k) then
                                if kt(p[i].x,p[i].y,p[j].x,p[j].y,p[k].x,p[k].y)  then
                                begin
                                        inc(dem[i]);
                                        if (i<j) and (k>j) then inc(d);
                                end;
        if dem[i]<min then begin min:=dem[i]; kq:=i; end;
    end;
end;
procedure inkq;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,d,' ',kq);
    close(f);
end;
begin
    nhap;
    xuly;
    inkq;
end.

LEM3 – spoj

Đề bài:

Thuật toán:

  • Đây là bài cơ bản của thuật toán quy hoạch động trạng thái.
  • Nếu giải bài này bằng duyệt sẽ không ăn được hết test.
  • Gọi F[i,state] là độ dài hành trình ngắn nhất khi đến được i và trạng thái thăm/chưa thăm các thành phố là state
    • state có dạng dãy bit 0,1. 1 là đã thăm, 0 là chưa thăm

Code:

Pascal (ideone)

uses    math;
const   fi='';
        fo='';
        maxn = 16;
        oo = 1 shl 16 -1;
var     f       :array[0..oo,1..maxn] of longint;
        i,j,n   :longint;
        c       :array[1..maxn,1..maxn] of longint;
        res     :longint;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        for i:=1 to n do
                for j:=1 to n do read(c[i,j]);
        close(input);
end;
function getbit( i,x :longint):byte;
begin
        getbit := (x shr (i-1)) and 1;
end;
function turnoff( i,x   :longint):longint;
begin
        turnoff := x and not (1 shl (i-1));
end;
procedure process;
var     i,j,k,t,state   :longint;
begin
        t := 1 shl n -1;
        for i:= 0 to t do
                for j:=1 to n do
                        f[i,j] := trunc(1e9);
        for i := 0 to t do
                for j := 1 to n do
                        if getbit(j,i)=1 then
                        begin
                                state := turnoff(j,i);
                                if state = 0 then begin f[i,j] := 0; break; end;
                                for k:=1 to n do
                                        if getbit(k,i)=1 then
                                                f[i,j] := min(f[i,j], f[state,k] + c[k,j]);
                        end;
        res := trunc(1e9);
        for i:=1 to n do
                res := min(res, f[t,i]);
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.

C++ (ideone)

#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--)
const int maxn = 1e5 ;
const int base = 1e9 + 7;
const int maxa = 1e6 * 5 + 1;
const int N = 50;
using namespace std;
int n,a[N][N],f[maxn][N],t[N],ans;
 
int get(int x,int i)
{
    return (x>>(i-1))&1;
}
 
int off(int x,int i)
{
    return x ^ (1<<(i-1));
}
 
int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    //freopen("trip.INP","r",stdin);
    //freopen("trip.OUT","w",stdout);
    cin>>n;
    fore(i,1,n)
    fore(j,1,n) cin>>a[i][j];
    int xx = (1<<n)-1;
    fore(x,1,xx)
    {
        int l = 0;
        fore(i,1,n)
        if (get(x,i)) t[++l] = i;
        if (l == 1) continue;
        fore(i,1,l)
        {
            int x1 = off(x,t[i]);
            f[x][t[i]] = base;
            fore(j,1,l)
            if (i != j && f[x][t[i]] > f[x1][t[j]] + a[t[j]][t[i]])
                f[x][t[i]] = f[x1][t[j]] + a[t[j]][t[i]];
            //if (x == 36)
                //cout<<t[i]<<' '<<f[x][t[i]]<<endl;
        }
    }
    ans = base;
    //cout<<get(36,1)<<endl;
    fore(i,1,n)
    ans = min(ans , f[xx][i]);
    cout<<ans;
    return 0;
}