Đề bài:

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

Thuật toán:

• Quy hoạch động!

Code:

• (xem code)

uses    math;
const   fi = '';
        fo = '';
var     n,m,i,j,maxf : integer;
        a,f : array[0..301,0..301] of integer;

begin
        assign(input,fi);
        reset(input);
        assign(output,fo);
        rewrite(output);
        readln(m,n);
        for i := 1 to m do
                for j := 1 to n do
                        read(a[i,j]);
        for j := 0 to n+1 do begin
                f[0,j] := -maxint;
                f[m+1,j] := -maxint;
        end;
        for i := 1 to m do f[i,1] := a[i,1];
        for j := 2 to n do
                for i := 1 to m do
                        f[i,j] := max(f[i-1,j-1],max(f[i,j-1],
                                       f[i+1,j-1])) + a[i,j];
        maxf := -maxint;
        for i := 1 to m do
                maxf := max(maxf,f[i,n]);
        writeln(maxf);
        close(input);
        close(output);
end.

Đề bài:

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

Thuật toán:

• Bạn chỉ cần tạo 1 xâu st[] với thứ tự các số tự nhiên như đề bài nhé.
• Các bạn xem code của mình để dễ hiểu hơn nhé

Code:

• (xem code)

Var
  n :Int64;

  function Solve :Int64;
  var
    S,T,X :AnsiString;
    i :Int64;
  begin
    S:=''; Str(n,X); i:=1;
    while i<=n do
      begin
        Str(i,T); S:=S+T; Inc(i);
      end;
    Solve:=Pos(X,S);
  end;

Begin
  Assign(Input,''); Reset(Input);
  Assign(Output,''); Rewrite(Output);
  ReadLn(n);
  Write(Solve);
  Close(Input); Close(Output);
End.

Đề bài:

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

Thuật toán:

• Sắp xếp các kí tự trong xâu S tăng dần theo thứ tự bảng chữ cái Alphabet.
• Quay lui liệt kê các hoán vị của xâu S, với mỗi hoán vị mới sinh ra kiểm tra xem có trùng với xâu vừa viết ra hay không.

Code:

• (xem code)

Const
  maxN =9;
  maxSL =362880;
Var
  n,m :LongInt;
  S,X :String[9];
  D :Array['A'..'Z'] of ShortInt;
  A :Array[0..maxSL] of String[9];
  Free :Array[1..maxN] of Boolean;

  procedure QSort(l,r :LongInt);
  var
    i,j :LongInt;
    Key,Tmp :Char;
  begin
    if (l>=r) then Exit;
    i:=l; j:=r; Key:=S[(l+r) div 2];
    repeat
      while (S[i]Key) do Dec(j);
      if (i<=j) then
        begin
          if (ij);
    QSort(l,j); QSort(i,r);
  end;

  function Factorial(i :LongInt) :LongInt;
  var
    j,tmp :LongInt;
  begin
    if (i=0) then Exit(1);
    tmp:=1;
    for j:=2 to i do tmp:=tmp*j;
    Exit(tmp);
  end;

  procedure Enter;
  var
    i,tmp :LongInt;
    ch :Char;
  begin
    ReadLn(S); n:=Length(S); QSort(1,n);
    FillChar(D,SizeOf(D),0);
    FillChar(Free,SizeOf(Free),true);
    for i:=1 to n do Inc(D[S[i]]);
    X:='';
    for i:=1 to n do X:=X+' ';
    tmp:=1;
    for ch:='A' to 'Z' do tmp:=tmp*Factorial(D[ch]);
    WriteLn(Factorial(n) div tmp);
    A[0]:='';
    m:=0;
  end;

  procedure Back(i :LongInt);
  var
    j :LongInt;
  begin
    for j:=1 to n do
      if (Free[j]) then
        begin
          X[i]:=S[j];
          Free[j]:=false;
          if (i=n) and (X>A[m]) then
            begin
              WriteLn(X); Inc(m); A[m]:=X;
            end
          else Back(i+1);
          Free[j]:=true;
        end;
  end;

Begin
  Assign(Input,''); Reset(Input);
  Assign(Output,''); Rewrite(Output);
  Enter;
  Back(1);
  Close(Input); Close(Output);
End.

Đề bài:

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

Thuật toán:

• bạn chỉ cần tạo hàm kiểm tra số nguyên tố thôi nhé.
• hàm mình tạo ở dưới code này. Các bạn đọc để dễ hiểu hơn nhé.

Code:

• (xem code)

#include
using namespace std;
int a,b;
int kt(int n)
{
    if(n<2) return 0;
    for (int i=2;i<=sqrt(n);i++)
      if (n%i==0)
           return 0;
return 1;
}
 int main()
{ cin>>a>>b;
    for (int j=a;j<=b;j++)
    {
        if(kt(j)) cout<
 Phần int kt(int n) chính là hàm kiểm tra số nguyên tố mà mình đã nói ở trên nhé ^_^

Đề bài:

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

Thuật toán:

• Ta xét tổng các số từ l -> r thì ta cần tìm l , r sao cho :l + (l+1) + … + (r-1) + r = n

  ⇒ (r+l)(r-l+1)/2 = n

  ⇒ (l+r)(r-l+1) = 2n

  Giải phương trình nghiệm nguyên đơn giản này

  Ta xét phần (l+r). Đương nhiên l + r >= 2 vì l >= 1, r >= l;

  Do l <= r nên ta chỉ cần xét (l + r) từ 2 -> sqrt(2n) thôi vì phần còn lại sẽ tạo ra bộ nghiệm tương tự phần ta xét

  Cho i = 2 -> sqrt(2n) :

  Nếu (2n) chia hết cho i thì ta bắt đầu :

  l + r = i và r – l + 1 = 2n/i hay r – l = 2n/i -1

  ⇒ 2r = i + 2n/i -1 mà r nguyên

  ⇒ (i + 2n/i – 1) chẵn

  ⇒ l cũng nguyên do r nguyên

  Vậy điều kiện để có một nghiệm cho bài toán là

  (2n) chia hết cho i và (i + 2n / i – 1) chẵn

  Nhận xét thời gian thực thi thuật toán là :

  O(100*sqrt(2*10^9))

Code:

• (xem code)

Program COUNTCBG;
Var
  n,res :LongInt;

  procedure Solve;
  var
    i :LongInt;
  begin
    res:=0;
    for i:=2 to Trunc(Sqrt(2*n)) do
      if (2*n mod i=0) then
        if ((i+2*n div i-1) mod 2=0) then Inc(res);
  end;

Begin
  Assign(Input,''); Reset(Input);
  Assign(Output,''); Rewrite(Output);
  while not EoF do
    begin
      ReadLn(n);
      Solve;
      WriteLn(res);
    end;
  Close(Input); Close(Output);
End.

Đề bài:

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

Thuật toán:

• Chuyển n về hệ nhị phân
• Các bạn có thể tham khảo code sau

Code:

• (xem code)

#include
using namespace std;
int main()
{
    long long  a[10000005], n,dem=0,k;
    cin>>n>>k;
    while(n>0)
    {
               a[dem] = n%2;
               n = n/2;
               dem++;
    }
    for(long long  i=dem-1; i>=0;i--)
    cout<

Đề bài:

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

Thuật toán:

• Dùng mảng f[i] đánh dấu giá trị lớn nhất <= i trong dãy A.
• Vậy nên các cặp 3 số là a[i], a[j], f[m-a[i]-a[j]].
• Chú ý đề bài cho dãy A đôi một khác nhau nhé.

Code:

• C++ (xem)

#include 

using namespace std;

const int oo = 500001;
const int MAXN = 10001;
int i, j, n, m, a[MAXN], tmp, res, f[oo];

int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i];
    sort(a+1,a+n+1);
    tmp = 0;
    for (int i = a[1]; i <= m; i++) {
        if ((tmp < n) && (i >= a[tmp+1])) tmp++;
        f[i] = a[tmp];
    }
    for (int i = 1; i<= n-2; i++) {
        for (int j = i+1; j <= n-1; j++) {
            tmp = m - a[i] - a[j];
            if (tmp < 1) continue;
            tmp = f[tmp];
            if (tmp <= a[j]) continue;
            res = max(res, a[i] + a[j] + tmp);
        }
    }
    cout << res;
    return 0;
}

• Pascal (xem)

CONST fin='';
     fout='';
VAR res, i, j, n, m, x, min: longint;
    a, ok: array[1..1000000] of longint;
    f: text;
BEGIN
  Assign(f,fin);
  Reset(f);
  Readln(f,n,m);
  min:=maxlongint-1;
  For i:=1 to n do
    Begin
      Read(f,a[i]);
      ok[a[i]]:=a[i];
      If a[i]0 then
          Begin
            If (ok[x]<>a[i]) and (ok[x]<>a[j]) and (ok[i]<>0) then
              If a[i]+a[j]+ok[x]>res then res:=a[i]+a[j]+ok[x];
          End;
      End;
  Assign(f,fout);
  Rewrite(f);
  Writeln(f,res);
  Close(f);
END.