BGBOARD – SPOJ

Đề bài: http://vn.spoj.com/problems/SKPV15_5/

Thuật toán:

  • (đang cập nhập)

Code:

#include <iostream>
#include <fstream>
#include <string.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
#include <cassert>
#include <list>
#include <iomanip>
#include <math.h>
#include <deque>
#include <utility>
#include <map>
#include <set>
#include <bitset>
#include <numeric>
#include <climits>
#include <cctype>
#include <cmath>
#include <cstdlib>
#include <ctime>
#include <functional>
#include <sstream>
 
using namespace std;
 
#define mpr make_pair
typedef unsigned int ui;
typedef unsigned long long ull;
typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
typedef pair <double, double> pdd;
typedef vector <int> vi;
typedef vector <ll> vll;
typedef vector <double> vd;
typedef vector <string> vs;
typedef map <string, int> mpsi;
typedef map <double, int> mpdi;
typedef map <int, int> mpii;
 
const double pi = acos(0.0) * 2.0;
const double eps = 1e-12;
const int step[8][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}, {1, 1}, {1, -1}, {-1, 1}, {-1, -1}};
 
template <class T> inline T abs1(T a) {return a < 0 ? -a : a;}
 
template <class T> inline T max1(T a, T b) { return a > b ? a : b; }
template <class T> inline T max1(T a, T b, T c) { return max1(max1(a, b), c); }
template <class T> inline T max1(T a, T b, T c, T d) { return max1(max1(a, b, c), d); }
template <class T> inline T max1(T a, T b, T c, T d, T e) { return max1(max1(a, b, c, d), e); }
template <class T> inline T min1(T a, T b) { return a < b ? a : b; }
template <class T> inline T min1(T a, T b, T c) { return min1(min1(a, b), c); }
template <class T> inline T min1(T a, T b, T c, T d) { return min1(min1(a, b, c), d); }
template <class T> inline T min1(T a, T b, T c, T d, T e) { return min1(min1(a, b, c, d), e); }
 
inline int jud(double a, double b){
	if(abs(a) < eps && abs(b) < eps) return 0;
	else if(abs1(a - b) / abs1(a) < eps) return 0;
	if(a < b) return -1;
	return 1;
}
template <typename t> inline int jud(t a, t b){
	if(a < b) return -1;
	if(a == b) return 0;
	return 1;
}
 
// f_lb == 1��?����ͬ��һ������߽磬f_small == 1��?�����û��Ѱ�ҵ�ֵ����С����
template <typename it, typename t1>
inline int find(t1 val, it a, int na, bool f_small = 1, bool f_lb = 1){
	int be = 0, en = na - 1;
	if(*a <= *(a + na - 1)){
		if(f_lb == 0) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != 1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != -1) en = mid;
			else be = mid + 1;
		}
		if(f_small && jud(*(a + be), val) == 1) be--;
		if(!f_small && jud(*(a + be), val) == -1) be++;
	} else {
		if(f_lb) while(be < en){
			int mid = (be + en + 1) / 2;
			if(jud(*(a + mid), val) != -1) be = mid;
			else en = mid - 1;
		}else while(be < en){
			int mid = (be + en) / 2;
			if(jud(*(a + mid), val) != 1) en = mid;
			else be = mid + 1;
		}
		if(!f_small && jud(*(a + be), val) == -1) be--;
		if(f_small && jud(*(a + be), val) == 1) be++;
	}
	return be;
}
 
 
 
template <class T> inline T lowb(T num) {return num & (-num); }
inline int bitnum(ui nValue) { return __builtin_popcount(nValue); }
inline int bitnum(int nValue) { return __builtin_popcount(nValue); }
inline int bitnum(ull nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitnum(ll nValue) { return __builtin_popcount(nValue) + __builtin_popcount(nValue >> 32); }
inline int bitmaxl(ui a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(int a) { if(a == 0) return 0; return 32 - __builtin_clz(a); }
inline int bitmaxl(ull a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
inline int bitmaxl(ll a) { int temp = a >> 32; if(temp) return 32 - __builtin_clz(temp) + 32; return bitmaxl(int(a)); }
 
long long pow(long long n, long long m, long long mod = 0){
	if(m < 0) return 0;
	long long ans = 1;
	long long k = n;
	while(m){
		if(m & 1) {
			ans *= k;
			if(mod) ans %= mod;
		}
		k *= k;
		if(mod) k %= mod;
		m >>= 1;
	}
	return ans;
}
 
//#define debug
//.........................��.......��.......��.......��.......��.......ֹ.......hack...............................................
 
const int maxn = 5000;
int dp[maxn][maxn];
int arr[maxn][maxn];
mpii biao[maxn * maxn];
int n, m;
 
int main(){
    ios_base::sync_with_stdio(0);
	#ifdef debug //......................................................................................................
	freopen("input.txt", "r", stdin);
	#endif //...........................................................................................................
	scanf("%d%d", &n, &m);
	for(int i = 0; i < n; i++) for(int j = 0; j < m; j++)
		scanf("%d", arr[i] + j);
	int ans = 0;
	for(int i = 0; i < n; i++) {
		 for(int j = 0; j < m; j++) {
			 mpii :: iterator it;
			 it = biao[arr[i][j]].begin();
			 for(; it != biao[arr[i][j]].end(); it++) {
				 int a = it->first, b = j;
				 if(a > b) swap(a, b);
				 dp[a][b] = max(it->second, dp[a][b]);
			 }
			 biao[arr[i][j]][j] = i + 1;
		 }
		 for(int j = 1; j < m; j++) for(int k = 0; k < m - j; k++)
			 dp[k][k + j] = max1(dp[k][k + j], dp[k][k + j - 1], dp[k + 1][k + j]);
		 for(int j = 0; j < m; j++) for(int k = j; k < m; k++) {
			 ans = max1(ans, (i - dp[j][k] + 1) * (k - j + 1));
		 }
	}
	cout << ans << endl;
    return 0;
}

QBSEQ – SPOJ

Đề bài:

Thuật toán:

  • Gọi F[i][j] là độ dài dãy con dài nhất của dãy A[1..i] có tổng các phần tử chia k dư j.

Các bạn có thể tham khảo thuật toán chi tiết ở trang 162 quyển “Giải thuật và lập trình” của thầy Lê Minh Hoàng.

Code:

uses math;
const
  fi='';
  fo='';
  maxn=1000;
  maxk=50;
var
  f : array[0..maxn,0..maxk] of longint;
  a : array[1..maxn] of longint;
  i,j,n,k : longint;
procedure enter;
  begin
    assign(input,fI);reset(input);
    readln(n,k);
    for i:=1 to n do read(a[i]);
    close(input);
  end;
function calc ( x,y : longint) : longint;
  var tg : longint;
  begin
    tg := (x-y) mod k ;
    if tg<0 then tg := tg+k;
    exit(tg);
  end;
procedure solve;
  begin
    for i:=0 to n do
      for j:=0 to k-1 do
        f[i,j] := -maxn*maxn;
    f[0,0] := 0;
    for i:=1 to n do
      for j:=0 to k-1 do
        f[i,j] := max(f[i-1,j],f[i-1,calc(j,a[i])] +1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[n,0]);
    close(output);
  end;
begin
  enter;
  solve;
  print;
end.

LIQ và LIS sử dụng phương pháp quy hoạch động – SPOJ

Đề bài:

Thuật toán:

  • Gọi L[i] là độ dài dãy con tăng dài nhất bắt đầu bằng phần tử thứ i trong dãy
  • L[i] = L[j] + 1 với j=i+1..n và a[j] > a[i]
  • Sử dụng tìm kiếm nhị phân để tính nhanh mảng L[]

Bạn hãy tham khảo cụ thể thuật toán bài này ở trang 143 quyển “Giải thuật và lập trình” – thầy Lê Minh Hoàng. Theo mình đánh giá thì đây là thuật + code chi tiết nhất, rất phù hợp cho các bạn newbie. Nếu đã hiểu rồi thì code sẽ ngắn hơn thầy nhiều 🙂

Code:

program LongestSubSequence;
const
  InputFile  = 'INCSEQ.INP';
  OutputFile = 'INCSEQ.OUT';
const
  max = 5000;
var
  a, L, T, StartOf: array[0..max + 1] of Integer;
  n, m: Integer;
 
procedure Enter;
var
  i: Word;
  f: Text;
begin
  Assign(f, InputFile); Reset(f);
  ReadLn(f, n);
  for i := 1 to n do Read(f, a[i]);
  Close(f);
end;
 
procedure Init;
begin
  a[0] := -32768;
  a[n + 1] := 32767;
  m := 1;
  L[n + 1] := 1;
  StartOf[1] := n + 1;
end;
 
function Find(i: Integer): Integer;
var
  inf, sup, median, j: Integer;
begin
  inf := 1; sup := m + 1;
  repeat
    median := (inf + sup) div 2;
    j := StartOf[median];
    if a[j] > a[i] then inf := median
    else sup := median;
  until inf + 1 = sup;
  Find := StartOf[inf];
end;
 
procedure Optimize;
var
  i, j, k: Integer;
begin
  for i := n downto 0 do
    begin
      j := Find(i);
      k := L[j] + 1;
      if k > m then
        begin
          m := k;
          StartOf[k] := i;
        end
      else
        if a[StartOf[k]] < a[i] then
          StartOf[k] := i;
      L[i] := k;
      T[i] := j;
    end;
end;
 
procedure Result;
var
  f: Text;
  i: Integer;
begin
  Assign(f, OutputFile); Rewrite(f);
  Writeln(f, m - 2);
  i := T[0];
  while i <> n + 1 do
    begin
      Writeln(f, 'a[', i, '] = ', a[i]);
      i := T[i];
    end;
  Close(f);
end;
 
begin
  Enter;
  Init;
  Optimize;
  Result;
end.

CTNOWN – SPOJ

Đề bài: http://vn.spoj.com/problems/CTNOWN/

Thuật toán:

  • (đang cập nhập)

Code:

uses    math;
const   fi='';
        fo='';
        maxn=350;
var     n,i,j   :longint;
        dem     :longint;
        nto     :array[1..maxn] of longint;
        cx      :array[1..maxn] of boolean;
        f       :array[0..maxn,0..maxn] of qword;
        t,tt,k    :longint;
        res,tam     :qword;
procedure sangnto;
var     i,j     :longint;
begin
        for i:=2 to trunc(sqrt(maxn)) do
                if cx[i]=false then
                        begin
                                j := i*i;
                                while (j<=maxn) do
                                        begin
                                                cx[j]:=true;
                                                j := j+i;
                                        end;
                        end;
        for i:=2 to maxn do
                if cx[i]=false then
                        begin
                                inc(dem);
                                nto[dem] := i;
                        end;
end;
function max(x,y : qword) : qword;
  var tg : qword;
  begin
    if x>y then exit(x) else exit(y);
  end;
procedure main;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
        sangnto;
        read(t);
                for i:=0 to dem do
                  for j:=0 to maxn do f[i,j] := 1;
                        for i:=1 to dem do
                                begin
                                        for j:=1 to maxn do
                                        begin
                                        f[i,j] := f[i-1,j];
                                        tam:=1;
                                        while tam*nto[i]<=j do
                                                begin
                                                        tam := tam * nto[i];
                                                        f[i,j] := max(f[i,j], f[i-1,j-tam]*tam );
                                                end;
                                        end;
                                end;
        for tt := 1 to t do
                begin
                        read(n);
                        writeln(f[dem,n]);
                end;
        close(input);close(output);
end;
procedure __;
begin
end;
begin
  __ ;
  main;
  __ ;
end.

NKPALIN – SPOJ

Đề bài: http://vn.spoj.com/problems/NKPALIN/

Thuật toán:

Gọi F[i][j] là độ dài xâu đối xứng dài nhất trong đoạn S[i..j]. Khi đó:

  1. F[i,j] = F[i+1,j-1]+2 nếu S[i] = S[j]
  2. F[i,j] = max(F[i+1,j],F[i,j-1]) nếu S[i] <> S[j]

Bạn có thể đọc code bên dưới để hiểu hơn.

Code:

Program Xaucon;
Var s,st,st1:ansistring;
    i,j:integer;
    F: Array[1..2000,1..2000] Of Integer;
 
Procedure nhap;
 Begin
  Readln(s);
  For i:=1 to length(s) do F[i,i]:=1;
  Writeln;Writeln;
 end;
 
Function max(a,b:integer):integer;
 Begin
  If a>b then exit(a) else exit(b);
 End;
 
 
Procedure Solve;
 Begin
  For i:=length(s) downto 1 do
   For j:=i+1 to length(s) do
     If s[i]=s[j] then
         F[i,j]:=F[i+1,j-1]+2
     else F[i,j]:= max(F[i+1,j],F[i,j-1]);
   End;
 
Procedure PrintResult;
 Begin
  i:=1;
  j:=length(s);
    While (i<=j) do
    Begin
     If s[i]=s[j] then
       Begin
         st:=st+s[i];
         st1:=s[j]+st1;
         inc(i);
         dec(j);
       end
     Else
       If F[i+1,j]=F[i,j] then inc(i) else dec(j);
    End;
     If F[1,length(s)] mod 2 =1 then delete(st1,1,1);
    st:=st+st1;
  Writeln(st);
  end;
 
 Begin
 nhap;
 Solve;
 PrintResult;
readln
end.

VODIVIDE – SPOJ

Đề bài:

Thuật toán:

Bài này có thể giải bằng phương pháp Quy hoạch động hoặc CTDL Heap. Ở đây giải theo phương pháp Quy hoạch động.

  • Gọi F[i,j] là tổng số tiền lớn nhất mà Sơn nhận được khi xét i đồng và Sơn được j đồng
  • F[i,j]:=max(F[i-1,j],F[i-1,j-1]+b[i]);

Code:

uses    math;
const   fi='';
        fo='';
        maxn=5000+2;
var     f:array[0..maxn,0..maxn] of longint;
        a,b,cs:array[1..maxn] of longint;
        res:array[1..maxn] of longint;
        dem,n,i,j:Longint;
        free:array[1..maxn] of boolean;
procedure nhap;
begin
    assign(input,fi);reset(Input);
    readln(n);
    for i:=1 to n do read(a[i]);
    for i:=1 to n do read(b[i]);
    close(input);
end;
procedure init;
begin
    for i:=1 to n do cs[i]:=i;
end;
procedure swap(var x,y:longint);
var     w:longint;
begin
    w:=x;x:=y;y:=w;
end;
procedure qs(l,r:longint);
var     i,j,x:longint;
begin
    i:=l;j:=r;
    x:=a[(l+r) div 2];
    repeat
        while x<a[i] do inc(i);
        while x>a[j] do dec(j);
        if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    swap(cs[i],cs[j]);
                    inc(i);dec(j);
                end;
    until i>j;
    if i<r then qs(i,r);
    if j>l then qs(l,j);
end;
procedure xuly;
begin
    {f[1,0]:=b[1];}
    qs(1,n);
    for i:=2 to n do
        for j:=1 to i div 2 do
                begin
                    f[i,j]:=max(f[i-1,j],f[i-1,j-1]+b[i]);
                end;
end;
procedure trace;
begin
    i:=n; j:=n div 2;
    while (i<>0) and (j<>0) do
        begin
            if f[i,j]=f[i-1,j-1]+b[i] then
                begin
                        inc(dem);
                        res[dem]:=i;
                        free[i]:=true;
                        dec(i);dec(j);
                end else dec(i);
        end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(f[n,n div 2]);
    for i:=1 to dem do
        begin
 
            for j:=res[i]-1 downto 1 do
                if free[j]=false then
                        begin
                            write(cs[j],' ');
                            free[j]:=true;
                            break;
                        end;
            write(cs[res[i]],' ');
            writeln;
        end;
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    trace;
    inkq;
end.

SPOJ – DHLOCO

Đề bài: http://vn.spoj.com/problems/DHLOCO/

Thuật toán:

  • Sub2: QHĐ f[i] = f[i-1]+f[i-2]+f[i-3];
  • Sub3: Nhân ma trận

Code:

const
  fi='dhloco.inp';
  fo='dhloco.out';
  mt1 : array[1..3,1..3] of int64=((0,0,1) , (1,0,1) , (0,1,1));
  mt2 : array[1..3,1..3] of int64=((1,2,4) , (0,0,0) , (0,0,0));
type
  matrix = array[1..3,1..3] of int64;
var
  n : int64;
  i,j,k,m : longint;
function mul(a,b :matrix) : matrix;
  var c : matrix;
      i,j,k : longint;
  begin
    for i := 1 to 3 do
      for j := 1 to 3 do
        begin
          c[i,j] := 0 ;
          for k := 1 to 3 do
            c[i,j] := (c[i,j] + a[i,k] * b[k,j]) mod m;
        end;
    exit(c);
  end;
function power(a : matrix; y : int64) : matrix;
  var tg : matrix;
  begin
    if y = 1 then exit(a);
    tg := power(a,y shr 1);
    if y mod 2 = 0 then exit(mul(tg , tg)) else exit(mul(mul(tg,tg),a));
  end;
procedure main;
var a,b,c : matrix;
begin
 // assign(input,fi);reset(input);
 // assign(output,fo);rewrite(output);
  read(n,m);
  if n=1 then begin writeln(1 mod m); exit; end;
 
  if n=2 then begin writeln(2 mod m); exit; end;
 
  if n=3 then begin writeln(4 mod m); exit; end;
  a := mt1;
  b := mt2;
  a := power(a , n-3);
  c := mul(b,a);
  writeln(c[1,3]);
  //close(input);close(output);
end;
begin
  main;
end.