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

MDOLLS – SPOJ

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

Thuật toán:

  • Sắp xếp tăng dần theo h[], nếu h[] bằng nhau thì xếp giảm dần theo w[]
  • Kết quả bài toán khi đó là độ dài dãy con tăng dài nhất của dãy w[n..1]

Code:

const   fi='';
        fo='';
        maxn=20003;
        oo=trunc(1e9);
var     w,h     :array[0..maxn] of longint;
        a,b     :array[0..maxn] of longint;
        i,j,n   :longint;
        res     :longint;
        t,tt    :longint;
procedure enter;
begin
        fillchar(a,sizeof(a),0);
        fillchar(b,sizeof(b),0);
        fillchar(w,sizeof(w),0);
        fillchar(h,sizeof(h),0);
        read(n);
        for i:=1 to n do read(w[i],h[i]);
end;
procedure swap(var x,y:longint);
var     tg      :longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r:longint);
var     x,y,i,j :longint;
begin
        i:=l;j:=r;
        x:=h[(l+r) div 2];
        y:=w[(l+r) div 2];
        repeat
                while (x>h[i]) or ((x=h[i]) and (y<w[i])) do inc(i);
                while (x<h[j]) or ((x=h[j]) and (y>w[j])) do dec(j);
                if i<=j then
                        begin
                                swap(h[i],h[j]);
                                swap(w[i],w[j]);
                                inc(i);dec(j);
                        end;
        until i>j;
        if i<r then qs(i,r);
        if j>l then qs(l,j);
end;
function tim(r,x:longint):longint;
var     d,c,g   :longint;
begin
        d:=0;c:=r;
        g:=(d+c) div 2;
        while (g<>d) and (g<>c) do
                begin
                        if b[g]>x then c:=g else d:=g;
                        g:= (d+c) div 2;
                end;
        for g:=c downto d do
                if x>=b[g] then exit(g);
end;
procedure process;
var     tam     :longint;
begin
        qs(1,n);
        a:=w;
        b[0] := -oo;
        b[1] := a[n];
        res :=1;
        for i:=n-1 downto 1 do
                begin
                        tam := tim(res,a[i]);
                        if tam+1>res then
                                begin
                                        res := res+1;
                                        b[res] := a[i];
                                end
                                else
                                if b[tam+1]>a[i] then b[tam+1]:=a[i];
                end;
end;
procedure print;
begin
        writeln(res);
end;
begin
assign(input,fi);reset(input);
assign(output,fo);rewrite(output);
  read(t);
  for tt :=1 to t do
  begin
        enter;
        process;
        print;
  end;
close(input);close(output);
end.

BALLGMVN – SPOJ

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

Thuật toán:

Với mỗi điểm[i] từ 1–>N:

  • Dời gốc tọa độ về điểm[i] nên xNew[j]=x[j]-x[i] và yNew[j]=y[j]-y[i] với mỗi 1<=j<=N.
  • Sắp xếp các điểm theo giá trị x/y.
  • Các điểm có cùng giá trị chính là các điểm trên cùng một đường thẳng. Xử lý và in kết quả.

Độ phức tạp O(N^2 log N).

Code:

const   fi='';
        fo='';
        maxn=1000;
type    point=record
                x,y:longint;
                end;
var     i,j,n:longint;
        p:array[1..2*maxn] of point;
        tmp:longint;
        hold:array[1..2*maxn] of real;
        cs:array[1..2*maxn] of integer;
procedure mo;
begin
    assign(input,fi); reset(input);
    assign(output,fo); rewrite(output);
end;
procedure doc;
begin
    read(n);
    for i:=1 to 2*n do read(p[i].x,p[i].y);
end;
procedure QS(l,r:longint);
Var     i,j:longint;
        x,w:real;
        tg:longint;
Begin
x:=hold[(l+r) div 2];
  i:=l;j:=r;
  Repeat
    While(hold[i]<x) do i:=i+1;
     While (x<hold[j]) do j:=j-1;
      If i<=j then
        Begin
          w:=hold[i];hold[i]:=hold[j];hold[j]:=w;
          tg:=cs[i];cs[i]:=cs[j];cs[j]:=tg;
          i:=i+1;j:=j-1;
        End;
 until i>j;
 If l<j then QS(l,j);
 If i<r then QS(i,r);
End;
procedure xuly;
var     a,b,k:longint;
begin
    for i:=1 to n do
    begin
        for j:=n+1 to 2*n do
                begin
                    a:=p[j].x-p[i].x;
                    b:=p[j].y-p[i].y;
                    if b=0 then hold[j]:=low(longint)
                        else hold[j]:=a/b;
                end;
        for j:=n+1 to 2*n do cs[j]:=j;
        qs(n+1,2*n);
         for j:=n+2 to 2*n do
                if hold[j]=hold[j-1] then
                        begin
                            write(i,' ');
                            for k:=j-1 to j do write(cs[k],' ');
                            halt;
                        end;
    end;
    for i:=n+1 to 2*n do
    begin
        for j:=1 to n do
                begin
                    a:=p[j].x-p[i].x;
                    b:=p[j].y-p[i].y;
                    if b=0 then hold[j]:=low(longint)
                        else hold[j]:=a/b;
                end;
        for j:=1 to n do cs[j]:=j;
        qs(1,n);
         for j:=2 to n do
                if hold[j]=hold[j-1] then
                begin
                    write(i,' ');
                    for k:=j-1 to j do write(cs[k],' ');
                    halt;
                end;
    end;
    writeln(-1);
    halt;
end;
begin
    mo;
    doc;
    xuly;
end.

100827E – Codeforces

Đề bài:

Thuật toán:

  • Bài này sử dụng phương pháp đệ quy có nhớ
  • Bạn có thể đọc code bên dưới để hiểu rõ hơn

Code:

uses math;
const
  fi='';
  fo='';
  maxn=80;
var
  f : array[0..maxn,0..9,false..true,false..true,false..true] of int64;
  res : int64;
  i,j,n,tt,t : longint;
  ss : array[1..maxn] of longint;
  s,st : string;
function ok(s : string) : boolean;
  begin
    if s[1]<=s[2] then
      begin
        for i:=1 to length(s)-1 do if s[i]>s[i+1] then break;
        if (i=length(s)-1) then exit(true);
        for j:=i to length(s)-1 do
          if s[j+1]>s[j] then exit(false);
        exit(true);
      end
      else
      begin
        for i:=1 to length(s)-1 do if s[i]<s[i+1] then exit(false);
        {if (i=length(s)-1) then exit(true);
        for j:=i to length(s)-1 do
          if s[j+1]<s[j] then exit(false);  }
        exit(true);
      end;
  end;
function nhohon(x,y : string):boolean;
  begin
    while length(x)<length(Y) do x := '0'+x;
    while length(x)>length(y) do y:='0'+y;
    if x<y then exit(true) else exit(false);
  end;
function tinh(i,tr : longint; tangdan,nhohon,bigger0 : boolean) : int64;
  var j,last : longint;
      sl : int64;
  begin
    if f[i,tr,tangdan,nhohon,bigger0]>-1 then exit(f[i,tr,tangdan,nhohon,bigger0]);
    if i>n then
      if {nhohon and} bigger0 then exit(1) else exit(0);
    sl := 0;
    if nhohon then last := 9 else last := ss[i];
    if tangdan then
      begin
        for j:=tr to last do
          sl := sl + tinh( i+1,j,tangdan,(nhohon) or (j<ss[i]),(bigger0) or (j>0) );
        if bigger0 then
          for j:= min(tr-1,last) downto 0 do
            sl := sl + tinh(i+1,j,false,nhohon or (j<ss[i]),bigger0 or (j>0));
      end
      else
      begin
        for j:=min(last,tr) downto 0 do
          sl := sl + tinh(i+1,j,false,nhohon or (j<ss[i]),bigger0 or (j>0));
      end;
    f[i,tr,tangdan,nhohon,bigger0] := sl;
    exit(sl);
  end;
procedure process;
  var i : longint;
  begin
    n := length(s);
    //for i:=1 to n do ss[i] := ord(s[i])-ord('0');
    for i:=1 to n do ss[i] := ord(s[i])-48;
    fillchar(f,sizeof(f),255);
    res := tinh(1,0,true,false,false);
  end;
begin
  assign(input,fi);reset(input);
  assign(output,fo);rewrite(output);
  readln(t);
  for tt:=1 to t  do
    begin
      readln(s);
      if not(ok(s)) then begin writeln(-1);continue; end;
      process;
      writeln(res);
    end;
  close(input);close(output);
end.

MATCH1 – SPOJ

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

Thuật toán:

Code:

const
  fi='';
  fo='';
  maxn=100;
var
  a : array[1..maxn,1..maxn] of boolean;
  match : array[1..maxn] of longint;
  i,j,n,m,res : longint;
procedure enter;
  var u,v : longint;
  begin
    assign(input,fi);reset(input);
    readln(n,m);
    while not eof(input) do
      begin
        readln(u,v);
        a[u,v] := true;
      end;
  end;
procedure process;
  var found : boolean;
      nlist,i,j,old : longint;
      list : array[1..maxn] of longint;
      cx : array[1..maxn] of boolean;
  procedure dfs(u : longint);
    var i,v : longint;
    begin
      for v:=1 to m do
        if a[u,v] then
          if cx[v] then
          begin
            cx[v] := false;
            if match[v]=0 then found := true else dfs(match[v]);
            if found then
              begin
                match[v] := u;
                exit;
              end;
          end;
    end;
  begin
    nlist := n;
    for i:=1 to n do list[i ] := i;
    repeat
      old := nlist;
      fillchar(cx,sizeof(cx),true);
      for i:=nlist downto 1 do
        begin
          found := false;
          dfs(list[i]);
          if found then
            begin
              list[i] := list[nlist];
              dec(nlist);
            end;
        end;
    until old = nlist;
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    for i:=1 to m do if match[i]<>0 then inc(res);
    writeln(res);
    for i:=1 to m do if match[i]<>0 then writeln(match[i],' ',i);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

Tổng hợp tài liệu về thuật toán cặp ghép

Tài liệu của thầy Lê Minh Hoàng: http://yeulaptrinh.pw/wp-content/uploads/2016/05/BipartiteMatching.pdf

 

PBCGANGS – SPOJ

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

Thuật toán:

  • Bài này thuật toán chỉ là DFS bình thường.
  • Đặc biệt là ở chỗ mình xây dựng đồ thị từ dữ liệu input. Các bạn có thể đọc code để hiểu hơn

Code:

Const
        fi      ='';
        fo      ='';
        maxn    =1001;
        maxm    =5001;
 
Type
        Arr1    =array[1..maxn] of longint;
        Arr2    =array[1..6*maxm] of longint;
        Arr3    =array[1..maxn] of boolean;
 
Var
        n,m     :longint;
        adj,link:arr2;
        head    :arr1;
        kt      :arr1;
        free    :Arr3;
        kq      :longint;
        dm      :longint;
        f       :text;
 
Procedure AE(u,v:longint);
begin
        inc(dm);
        adj[dm]:=v;
        link[dm]:=head[u];
        head[u]:=dm;
end;
 
Procedure Nhap;
var
        i,u,v   :longint;
        c,k     :char;
begin
        assign(f,fi);
        reset(f);
        readln(f,n);
        for i:=1 to n do
          begin
            kt[i]:=0;
            head[i]:=0;
            free[i]:=true;
          end;
        dm:=0;
        readln(f,m);
        for i:=1 to m do
          begin
            readln(f,c,u,v);
            if c='E' then
              begin
                if kt[u]=0 then kt[u]:=v
                  else
                    begin
                      ae(v,kt[u]);
                      ae(kt[u],v);
                    end;
                if kt[v]=0 then kt[v]:=u
                  else
                    begin
                      ae(u,kt[v]);
                      ae(kt[v],u);
                    end;
              end
            else
              begin
                ae(u,v);
                ae(v,u);
              end;
          end;
        close(f);
end;
 
Procedure DFS(u:longint);
var
        i,v     :longint;
begin
        free[u]:=false;
        i:=Head[u];
        while i<>0 do
          begin
            v:=adj[i];
            if free[v] then DFS(v);
            i:=link[i];
          end;
end;
 
Procedure Sol;
var
        u       :longint;
begin
        kq:=0;
        for u:=1 to n do
         if free[u] then
           begin
             inc(kq);
             DFS(u);
           end;
end;
 
Procedure Xuat;
begin
        assign(f,fo);
        rewrite(f);
        write(f,kq);
        close(f);
end;
 
begin
        Nhap;
        Sol;
        Xuat;
end.