Archives for Tháng Mười Hai 2016

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;
}

BCDIV – spoj

Đề bài:

Thuật toán:

Gọi f[i][j] là chia i số vào n nhóm.

  • f[i][j]=f[i-1][j-1]+f[i-1][j]*j.
  • Khởi tạo f[0][0]=1.

Giải thích công thức trên:

  • Nếu đã chia được (i-1) số vào (j-1) nhóm-> bắt buộc phải chia số thứ i vào nhóm thứ j-> có f[i-1][j-1] cách
  • Nếu ta đã chia được (i-1) số vào j nhóm->có j cách để cho số thứ i vào một nhóm bắt kì->có f[i-1][j]*j

Tổng cộng có f[i-1][j-1]+f[i-1][j]*j.

Code:

const   fi      ='';
        fo      ='';
var     n, k    :int64;
        f       :array[0..25,0..25] of int64;
        i, j    :longint;
        t       :longint;
begin
        fillchar(F, sizeof(f),0);
        f[0,0]:=1;
        for i:=1 to 25 do
                for j:=1 to 25 do
                        f[i,j]:=f[i-1,j-1]+f[i-1,j]*j;
        assign(input,fi);
        reset(input);
        assign(output,fo);
        rewrite(output);
        readln(t);
        for i:=1 to t do
                begin
                        readln(n,k);
                        writeln(f[n,k]);
                end;
        close(input);close(output);
end.

C11STAR – SPOJ

Đề bài:

Thuật toán:

+ 20% test đầu với m, n ≤100:

– Với dữ liệu nhỏ như thế này ta có thể làm cách thô thiển là duyệt tất cả hình thỏa mãn là ngôi sao rồi tăng kết quả lên.

– Độ phức tạp: O((m*n)^2)

+ 30% test tiếp theo có m≤600, n ≤150:  

– Ở đây ta có thể tiếp cận bài toán theo hướng khác: đếm hình chữ nhật xiên 45 độ.

– Giờ ta nghĩ đến phương pháp quay sao cho quy bài toán về đếm hình chữ nhật, để ý là các ô thuộc cùng đường chéo thì có tổng X=i+j và hiệu Y=i-j giống nhau, từ đó ta có 1 phép biến đổi:

+ biến ô (i,j) thành ô (i+j,i-j) trong bảng mới.

Bây giờ ta có 1 bảng mới với kích thước (m+n)*(m+n) :

+ Gọi f[i][j][‘char’] là số cặp ký tự ‘char’ trong 2 cột i và j.

+ Duyệt O((m+n)^3) để tính mảng f, sau đó dùng O((m+n)^2) để cập nhật kết quả

→ kết quả là Sum(f[i][j][‘char’]*(f[i][j][‘char’]-1)/2);

+ Để ý là các ô có (i+j) mod 2=0. và (i+j) mod 2=1 không liên quan tới nhau, do đó ta có thể đưa về 2 bảng để giảm độ phức tạp 1 tý để ăn được subtask này.

– Độ phức tạp O((m+n)^3)

+ 50% test cuối có m≤3000, n ≤200:

– Ta có các nhận xét sau:

+ Bảng có tối đa (m+n) đường chéo

+ Hình ngôi sao to nhất cũng chỉ nằm trong phạm vi min(m,n)^2

Từ đó ta có cách giải:

+ Gọi f[i][j][‘char’] số cặp ký tự ‘char’ nằm trên 2 đường chéo i và j.

+ Duyệt m*n ô của bảng

+ Với mỗi ô ta duyệt min(m,n) ô cùng đường chéo với nó trở lên, nếu cùng ký tự:

→ tăng kết quả lên f[i][j][‘char’]

→ cập nhật f[i][j][‘char’]=f[i][j][‘char’]+1

– Độ phức tạp O(m*n*min(m,n))

Code:

const   fi      ='';
        fo      ='';
        maxM    =3000;
        maxN    =200;
 
var     f       :array['a'..'z',1..maxM+maxN,1..maxM+maxN] of integer;
        m, n    :longint;
        a       :array[0..maxM,0..maxN] of char;
 
procedure Optimize;
var     i, j,i1,j1    :longint;
        ans     :longint;
begin
        fillchar(f,sizeof(f),0);
        ans:=0;
        for i:=1 to m do
                for j:=1 to n do
                        if a[i,j]<>'.' then
                                begin
                                        i1:=i;j1:=j;
                                        while (i1<m) and (j1<n) do
                                                begin
                                                        inc(i1);inc(j1);
                                                        if a[i1,j1]=a[i,j] then
                                                                begin
                                                                        ans:=ans+f[a[i,j],i+j,i1+j1];
                                                                        inc(f[a[i,j],i+j,i1+j1]);
                                                                end;
                                                end;
                                end;
        writeln(ans);
end;
 
procedure run;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                for j:=1 to n do read(a[i,j]);
                readln;
                end;
        Optimize;
        close(input);close(output);
end;
 
begin
        run;
end.

KVIP – spoj

Đề bài:

Thuật toán:

Giả sử người 1 (VIP) ngồi ở vị trí k1 thì:

– Người 2,3,…,k1-1 sẽ ngồi đúng vị trí của mình: 2,3,…,k1-1

– Người k1 có 2 cách chọn vị trí ngồi:

— Chọn ngồi ở vị trí 1: những người k1+1,k1+2,…,n sẽ ngồi đúng vị trí của mình

— Chọn ngồi ở vị trí k2>k1: người k1+1,k1+2,…,k2-1 sẽ ngồi đúng vị trí

— Người k2 có 2 cách chọn vị trí ngồi:

——– Chọn ngồi ở vị trí 1: những người k1+1,k1+2,…,n sẽ ngồi đúng vị trí của mình

——– Chọn ngồi ở vị trí k3: người k2+1,k2+2,…,k3-1 sẽ ngồi đúng vị trí

……

 

Đề bài quy về chọn 1 dãy các phần tử: k1,k2,k3,…,kx,1 ( với k1<k2<k3…<kx )

Tức là:

– Người 1 ngồi vị trí k1

– Người k1 ngồi vị trí k2

– Người k2 ngồi vị trí k3

– Người kx-1 ngồi vị trí kx

– Người kx ngồi vị trí 1

– Những người còn lại ngồi đúng vị trí của mình

 

Kết quả của dãy đã chọn là:

A[1,1] + A[2,2] + … + A[n,n] – A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1]

Đặt S=A[1,1] + A[2,2] + … + A[n,n], S không đổi

=> Cần tìm dãy sao cho:

(- A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1]) đạt giá trị lớn nhất

Gọi F[i] là tổng lớn nhất của dãy {k1,k2,…,i,1} ( người i ngồi vị trí 1 )

  • F[i] = – A[1,1] + A[1,k1] – A[k1,k1] + A[k1,k2] – … – A[kx,kx] + A[kx,1] ( với kx=i )
  • F[i] = max ( F[i], F[j] – A[j,1] + A[j,j] + A[i,1] – A[i,i] ) với ( i>j )

Kết quả bài toán: S + F (max)

Code:

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;
 
var     a       :Array[1..maxN,1..maxN] of longint;
        f       :Array[1..maxN] of int64;
        n       :longint;
 
procedure Optimize;
var     i , j   :longint;
        ans :int64;
        maxF    :int64;
begin
        f[1]:=0;
        for i:=1 to n do f[1]:=f[1]+a[i,i];
        for i:=2 to n do
                begin
                        f[i]:=low(int64);
                        for j:=i-1 downto 1 do
                                f[i]:=max(f[i],f[j]-a[j,1]+a[j,i]-a[i,i]+a[i,1]);
                end;
        maxF:=f[1];
        for i:=2 to n do maxF:=max(maxF,f[i]);
        writeln(maxF);
end;
 
procedure run;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(n);
        for i:=1 to n do
                for j:=1 to n do read(a[i,j]);
        Optimize;
        close(input);close(output);
end;
 
begin
        run;
end.

DIFFSTR – spoj

Đề bài:

Thuật toán:

Solution ăn 60%:

Xét xâu S và dãy x[1..n] thỏa mãn 1 <= x[i] <= length(S) và x[i] > x[i – 1]. Với mỗi dãy x, ta thu được 1 xâu con của S: S[x[1]] S[x[2]] S[x[3]]… S[x[n]]

Để tạo ra được các xâu con phân biệt của S mà 2 phần tử liền kề khác nhau, ta chỉ xét đến những dãy x thỏa mãn điều kiện sau:

  1. S[x[i]] != S[x[i – 1]]
  2. Không tồn tại số k thỏa mãn x[i] < k < x[i + 1] và S[k] == S[x[i + 1]] (nói nôm na là nếu chọn ký tự ch nào đó để cho vào xâu con thì luôn chọn ký tự có chỉ số nhỏ nhất)

(cái đoạn in nghiêng này hình như không cần thiết :)))

 Gọi g[i][j] là số cách chọn dãy x[] có i phần tử mà x[i] = j.

 g[i][j] sẽ cập nhật cho g[i + 1][k] mà k là những giá trị mà khi thêm x[i + 1] = k thì vẫn đảm bảo điều kiện của dãy x[] ở trên (nhận xét là sẽ có không quá 26 giá trị của k)

g[i + 1][k] += g[i][j]

Cuối cùng, để tính kết quả bài toán:

Gọi:

  • f[i][j][0] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con bằng với xâu b[1..i]
  • f[i][j][1] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con lớn hơn xâu b

Với mỗi f[i][j][t], tìm các giá trị k thỏa mãn thêm x[i + 1] = k vẫn đảm bảo thỏa mãn điều kiện của x[]:

– Nếu t = 1 thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] = b[i + 1] thì f[i + 1][k][0] += f[i][j]

– Nếu t = 0, S[x[k]] > b[i + 1] thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] < b[i + 1] thì không làm gì hết

Kết quả bài toán = tổng f[i][j][1] + tổng f[length(b)][j][0]

Đpt ít hơn O(n * n * log(n)) n * n là mảng f, log(n) để tìm k, thực chất là không cần tính hết mảng f nên đpt sẽ nhỏ hơn khá nhiều

Solution ăn 100%:

QHĐ tương tự như trên, ta có thể tính được số xâu con của S[i..n] bắt đầu bằng ký tự ch bất kỳ mà thỏa mãn 2 ký tự liền kề khác nhau trong O(1)

Duyệt i từ đầu đến cuối xâu b, đến bước thứ i, đếm số xâu con trong S có dạng b[1..i – 1] + x với x là 1 xâu < S[i..m]. Số lượng xâu x = (số xâu con trong S[k..n] (k là vị trí kết thúc đầu tiên của xâu con b[1..i – 1] trong xâu S) bắt đầu bằng các ký tự < b[i]) + 1 (xâu rỗng)

Kết quả bài toán là tổng của các xâu trên – 1 (xâu rỗng)

Lưu ý là trong khi duyệt, nếu xâu b[1..i] không thỏa mãn điều kiện  2 ký tự liền kề khác nhau thì phải dừng duyệt ngay lập tức.

Solution O(N): của anh Nguyễn Tấn Sỹ Nguyên ( flash_mt )

Gọi F[i] là số cách chọn 1 subsequence ko có 2 phần tử kề nhau bằng nhau với S[i] là phần tử đầu tiên. Có thể tính F[] trong O(26N).

Sau đó ta đếm số lượng subsequence A thỏa A[1..k] = B[1..k] và A[k + 1] > B[k + 1]. Với mỗi giá trị k, xét A[k + 1] = c với c > B[k + 1], tìm vị trí u đầu tiên trong đoạn còn lại thỏa S[u] = c và tăng kết quả lên f[u]. Độ phức tạp của bước này là O(26(M + N)).

Code:

  • (đang cập nhập)

NKPANO – spoj

Đề bài:

Thuật toán:

  • Sắp xếp các công nhân tăng dần theo S
  • Gọi F[i] là tổng tiền công lớn nhất nếu sơn đến vạch i.
    Với mỗi công nhân thứ k: F[i]=max(F[i],F[j-1]+(i-j+1)*P[k]), trong đó: S[k]<=i<=S[k]+L[k]-1, i-L[k]+1<=j<=S[k]

Code:

#include <bits/stdc++.h>
#define maxn 16010
using namespace std;
int n,k,l;
int f[maxn+1],maxf[maxn+1],maxr[maxn+1];
struct  te{
    int l,p,s;
};
te a[102];
template <typename T> inline void read(T &x){
	x = 0; char c;
	while (!isdigit(c = getchar())) {}
	do x = x * 10 + c - '0'; while (isdigit(c = getchar()));
}
template <typename T> inline void write(T x){
	if (x > 9) write(x / 10);
	putchar(x % 10 + 48);
}
void    docdl(){
    read(n); read(k);
    for(int i=1;i<=k;i++){
        read(a[i].l);
        read(a[i].p);
        read(a[i].s);
    }
}
bool    cmp(te a,te b){
    return (a.s<=b.s);
}
void    xuli(){
    sort(a+1,a+k+1,cmp);
    for(int i=1;i<=k;i++){
        maxr[a[i].s+1]=-1000000000;
        for(int j=a[i].s;j>=max(a[i].s-a[i].l+1,1);j--) maxr[j]=max(maxr[j+1],maxf[j-1]-(int)j*a[i].p);
        for(int j=a[i].s;j<=min(a[i].s+a[i].l-1,n);j++){
            f[j]=max(f[j],maxr[max(j-a[i].l+1,1)]+(int)(j+1)*a[i].p);
            maxf[j]=max(f[j],maxf[j-1]);
        }
        for(int j=1;j<=n;j++) maxf[j]=max(maxf[j],maxf[j-1]);
    }
    int res=0;
    for(int i=1;i<=n;i++) res=max(res,f[i]);
    write(res);
}
int     main(){
    docdl();
    xuli();
}

CASTLE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập thuật toán)

Code:

uses math;
const
    tfi='';//castle.inp';
    tfo='';//castle.out';
 
var
    fi,fo:text;
    n,top1,top2,top3,dem:longint;
    tg,kq1,kq2,kq11,kq22:int64;
    p,q,a,b:array[0..5001] of longint;
    st:array[0..5001] of int64;
procedure nhap;
    var i,j:longint;
    begin
        read(fi,n);
        for i:=1 to n do read(fi,a[i],b[i]);
        kq2:=high(int64);
    end;
 
procedure swap(var x,y:longint);
    var tg:longint;
    begin
        tg:=x;
        x:=y;
        y:=tg;
    end;
 
procedure sort(l,r:longint);
    var i,j,k,k1,k2:longint;
    begin
        i:=l;
        j:=r;
        k:=l+random(r-l+1);
        k1:=a[k];
        k2:=b[k];
        repeat
            while (a[i]<k1) or ((a[i]=k1) and (b[i]<k2)) do inc(i);
            while (a[j]>k1) or ((a[j]=k1) and (b[j]>k2)) do dec(j);
            if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    inc(I);
                    dec(j);
                end;
        until i>j;
        if i<r then sort(i,r);
        if l<j then sort(l,j);
    end;
 
procedure lam(u,v:int64);
    var i,j:longint;
    begin
        top3:=0;
        j:=1;
        for i:=1 to top1 do
            begin
                while (j<=top2)and ( p[j]<=q[i]) do
                    begin
                        if p[j]=q[i] then
                            begin
                                inc(top3);
                                st[top3]:=p[j];
                            end;
                        inc(j);
                    end;
            end;
        dem:=dem+int64(top3)*(top3-1) DIV 2;
        if top3>=2 then
        begin
        tg:=int64(st[top3]-st[1])*(v-u);
        if tg=kq1 then inc(kq11);
        if tg>kq1 then
            begin
                kq1:=tg;
                kq11:=1;
            end;
        end;
        for i:=2 to top3 do
            begin
                tg:=int64(st[i]-st[i-1])*(v-u);
                if tg=kq2 then inc(kq22);
                if tg<kq2 then
                    begin
                        kq2:=tg;
                        kq22:=1;
                    end;
            end;
    end;
 
procedure xuli;
    var i,j,k,k1:longint;
    begin
        sort(1,n);
        i:=1;
        a[n+1]:=-maxlongint;
        while i<n do
            begin
                top1:=0;
                for j:=i to n+1 do
                    if a[j]<>a[i] then break
                    else
                        begin
                            inc(top1);
                            q[top1]:=b[j];
                        end;
                if j>n then break;
                k:=j;
                while k<=n do
                    begin
                        top2:=0;
                        for k1:=k to n+1 do
                            if a[k1]<>a[k] then break
                            else
                                begin
                                    inc(top2);
                                    p[top2]:=b[k1];
                                end;
                        lam(a[i],a[k]);
                        k:=k1;
                    end;
                i:=j;
            end;
        writeln(fo,dem);
        if dem>0 then
            begin
                writeln(fo,kq1,' ',kq11);
                writeln(fo,kq2,' ',kq22);
            end;
    end;
 
begin
    assign(fi,tfi);
    assign(fo,tfo);
    reset(fi);
    rewrite(fo);
    nhap;
    xuli;
    close(fo);
end.