Archives for Tháng Năm 2016

VMKEY – SPOJ

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

Thuật toán:

  • (đang cập nhập)

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
int d[100][100];
int w[100][100];
string s;
typedef pair<int, int> ii;
int x[101];
ii p[110];
vector< ii > v;
int pos[11];
int dist[100][100];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("vao.inp", "r", stdin);
    freopen("ra.out", "w", stdout);
    #endif //MIKELHPDATKE
   // cout<<"wtf"<<endl;
    FORE(i, 1, 9) x[i] = i;
    x[10] = 0;
    cin >> s;
    //cout<<s<<endl;
    FOR(i, 0, s.size() - 1){
        d[s[i] - '0'][s[i + 1] - '0']++;
        if (d[s[i] - '0'][s[i + 1] - '0'] == 1) v.push_back(ii(s[i] - '0', s[i + 1] - '0'));
    }
 
    p[1].first = 1; p[1].second = 1;
    p[2].first = 1; p[2].second = 2;
    p[3].first = 1; p[3].second = 3;
    p[4].first = 2; p[4].second = 1;
    p[5].first = 2; p[5].second = 2;
    p[6].first = 2; p[6].second = 3;
    p[7].first = 3; p[7].second = 1;
    p[8].first = 3; p[8].second = 2;
    p[9].first = 3; p[9].second = 3;
    p[10].first = 4; p[10].second = 1;
    FORE(u, 1, 10) FORE(v, 1, 10) dist[u][v] = abs(p[u].first - p[v].first) + abs(p[u].second - p[v].second);
    int ans = INF;
    //FOR(i, 0, s.size() - 1) ans += dist[s[i] - '0'][s[i + 1] - '0'] * d[s[i] - '0'][s[i + 1] - '0'];
    while (next_permutation(x + 1, x + 11)){
        int sum = 0;
        FORE(i, 1, 10) pos[x[i]] = i;
        FOR(i, 0, v.size()){
            int u = v[i].first, vv = v[i].second;
            sum += dist[pos[u]][pos[vv]] * d[u][vv];
        }
        ans = min(ans, sum);
    }
    cout << ans;
    return 0;
}

NKCITY – SPOJ

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

Thuật toán:

  • Giải bài này có thể sử dụng thuật toán Prim hoặc thuật toán Kruskal đều được.
  • Các bạn có thể tham khảo cả 2 cách làm ở bên dưới.

Code:

Kruskal

uses    math;
const   fi      ='';
        fo      ='';
        maxn    =1000;
        maxm    =10000;
 
type    data    =record
                u, v, c :longint;
                end;
 
var     f       :Text;
        n, m    :longint;
        Edges   :array[1..maxm] of Data;
        b       :Array[1..maxm] of longint;
        Father  :Array[1..maxn] of longint;
        res     :longint;
procedure nhap;
var     i, u, v, c :longint;
begin
        assign(f, fi);
        reset(f);
        readln(f, n, m);
        for i:=1 to m do
                begin
                        readln(f, u, v, c);
                        Edges[i].u:=u;
                        Edges[i].v:=v;
                        Edges[i].c:=c;
                end;
        close(f);
end;
 
Procedure init;
var     i :longint;
begin
        for i:=1 to m do b[i]:=i;
        for i:=1 to n do father[i]:=-1;
        res:=-1;
end;
 
procedure QS(l,r:longint);
var     i, j, x, tg     :longint;
begin
        i:=l;
        j:=r;
        x:=edges[b[ (l+r) div 2] ].c;
        repeat
                while Edges[b[i]].c < x do inc(i);
                while Edges[b[j]].c > x do dec(j);
                if i<=j then
                        begin
                                tg:=b[i];
                                b[i]:=b[j];
                                b[j]:=tg;
                                inc(i);
                                dec(j);
                        end;
        until i>j;
        if l<j then QS(l,j);
        if i<r then QS(i,r);
end;
 
function find(i:longint):longint;
var     t       :longint;
begin
        t:=i;
        while father[t]>0 do t:=father[t];
        exit(t);
end;
 
procedure union(i, j:longint);
var     x :longint;
begin
        x:=father[i]+father[j];
        if father[i]>father[j] then
                begin
                        father[i]:=j;
                        father[j]:=x;
                end
        else    begin
                        father[j]:=i;
                        father[i]:=x;
                end;
end;
 
procedure Kruskal;
var     i, u,v, c, r1, r2 :longint;
begin
        init;
        QS(1,m);
        for i:=1 to m do
                begin
                        u:=Edges[b[i]].u;
                        v:=Edges[b[i]].v;
                        c:=Edges[b[i]].c;
                        r1:=find(u);
                        r2:=find(v);
                        if r1<>r2 then
                                begin
                                        union(r1,r2);
                                        res:=max(res,c);
                                end;
                end;
end;
 
procedure xuat;
begin
        assign(f, fo);
        rewrite(f);
        writeln(f, res);
        close(f);
end;
 
BEGIN
        nhap;
        Kruskal;
        xuat;
END.

Prim

const   fi='';
        fo='';
        maxn=1000;
        maxc=trunc(1e9);
var     d:array[1..maxn] of longint;
        i,j,n,m,res:longint;
        u,v,t:longint;
        cx:array[1..maxn] of boolean;
        c:array[1..maxn,1..maxn] of longint;
procedure init;
begin
    for i:=1 to n do d[i]:=maxc;
    d[1]:=0;
    fillchar(cx,sizeof(cx),true);
end;
procedure prim;
var     min,u:longint;
begin
        repeat
                min:=maxc;u:=0;
                for i:=1 to n do
                        if cx[i] then
                        if d[i]<min then
                                begin
                                    min:=d[i];
                                    u:=i;
                                end;
                if (u=0) then exit;
                cx[u]:=false;
                if d[u]>res then res:=d[u];
                for v:=1 to n do
                        if cx[v] then
                                if d[v]>c[u,v] then
                                        begin
                                            d[v]:=c[u,v];
                                        end;
        until false;
end;
begin
    assign(input,fi);reset(input);
    assign(output,fo);rewrite(output);
    readln(n,m);
    for i:=1 to n do
        for j:=1 to n do
                if i<>j then c[i,j]:=maxc else c[i,j]:=0;
    for i:=1 to m do
        begin
            readln(u,v,t);
            c[u,v]:=t;
            c[v,u]:=t;
        end;
    init;
    prim;
    writeln(res);
    close(input);close(output);
end.

VMRESTO – SPOJ

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

Thuật toán:

  • Thuật toán bài này khá đơn giản. Bạn có thể đọc code của mình bên dưới, mình viết code cũng khá dễ đọc.

Code:

const   fi='';
        fo='';
        maxn=100;
var     hang,cot:array[1..maxn] of int64;
        cheo,n,i,j,k:longint;
        a:array[1..maxn,1..maxn] of int64;
        res,hold:int64;
procedure nhap;
begin
    assign(input,fi);reset(input);
 
    readln(n);
    for i:=1 to n do
        for j:=1 to n do read(a[i,j]);
 
    close(input);
end;
procedure init;
begin
    for i:=1 to n do
        for j:=1 to n do
                begin
                        inc(hang[i],a[i,j]);
                        inc(cot[j],a[i,j]);
                end;
end;
procedure xuly;
begin
    hold:=0;
    for i:=2 to n do
      begin
        a[i,i]:=hang[1]-hang[i];
        inc(hold,a[i,i]);
      end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(Output);
    res:=(hang[1]-hold) div (n-1);
    for i:=1 to n  do
        begin
            for j:=1 to n do
                if i<>j then write(a[i,j],' ') else write(res+a[i,j],' ');
            writeln;
        end;
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    inkq;
end.

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.