Archives for Tháng Sáu 2017


QBMAX – spoj

Đề bài:

Thuật toán:

  • Quy hoạch động!

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.

LIS – SPOJ

Đề bài:

Thuật toán:

  • for lồng với chặt nhị phân mất tốc độ O(n)log(n)
  • các bạn xem code thắc mắc đâu thì hỏi thêm nha

Code:

program         LIS;
var     a,l:array[1..30000] of longint;
        d,i,dau,cuoi,mid,n:longint;
begin
        readln(n);
        for i:=1 to n do read(a[i]);
        d:=1;
        l[1]:=1;
        for i:=2 to n do
                begin
                        if a[i]>a[l[d]] then
                                begin
                                        inc(d);
                                        l[d]:=i;
                                end
                        else
                                begin
                                        dau:=1;
                                        cuoi:=d;
                                        while dau <= cuoi do
                                                begin
                                                        mid:=(dau+cuoi) div 2;
                                                        if a[i]>a[l[mid]] then dau:=mid+1
                                                        else cuoi:=mid-1; 
                                                end;
                                        l[dau]:=i;
                                end;
                end;
        write(d);
end.

LIQ – spoj

Đề bài:

Thuật toán:

  • for 2 vòng lồng nhau để kiểm tra điều kiện nếu thoả mãn thì tăng biến đếm lên nếu không thì giữ nguyên

Code:

program      LIQ;
var    n,res,i,j:longint;
a,f:array[1..1009] of longint;
begin
readln(n);
res:=0;
for i:=1 to n do
begin
read(a[i]);
f[i]:=1;
for j:=1 to i-1 do
if (a[i]>a[j]) and (f[j]+1>f[i]) then f[i]:=f[i]+1;
if f[i]>res then res:=f[i];
end;
writeln(res);
end.

MDIGITS2 – spoj

Đề bài:

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:

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.

QBHV – spoj

Đề bài:

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:

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 Inc(i); 
     while (S[j]>Key) do Dec(j);
      if (i<=j) then
        begin
          if (i<j) then begin Tmp:=S[i]; S[i]:=S[j]; S[j]:=Tmp; end; Inc(i); Dec(j); end; until (i>j);
    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.

PNUMBER- spoj

Đề bài:

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:

#include<bits/stdc++.h>
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<<j<<endl;
    }
    return 0;
 
}
  • 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é ^_^
  • COUNTCBG – spoj

    Đề bài:

    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:

    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.