STONE1 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi='';//stone1.inp';
  fo='';//stone1.out';
  maxn=403;
  maxm=403;
type
  arr1 = array[1..maxn] of longint;
var
  link,head,ke : array[-maxm..maxm] of longint;
  f,deg : array[1..maxn] of longint;
  i,j,n,m,k : longint;
  st : array[1..maxn,1..maxn] of longint;
  top : array[1..maxn] of longint;
  a : array[1..maxn,1..maxn] of boolean;
  cx : array[1..maxn] of boolean;
procedure add(i,u,v : longint);
  begin
    link[i] := head[u];
    head[u] := i;
    ke[i] := v;
  end;
procedure enter;
  var u,v,i : longint;
  begin
    assign(input,fi);reset(input);
    read(n);
    for i := 1 to n do
      begin
        read(u,k);
        for j:=1 to k do
          begin
            read(v);
            if a[u,v] = false then
              begin
                a[u,v] := true;
                inc(deg[u]);
              end;
            if a[v,u] = false then
              begin
                a[v,u] := true;
                inc(deg[v]);
              end;
          end;
      end;
    close(input);
  end;
procedure push(i,x : longint);
  begin
    inc(top[i]);
    st[i,top[i]] := x;
  end;
procedure swap(var x,y : longint);
  var tg : longint;
  begin
    tg:=x;x:=y;y:=tg;
  end;
procedure qs(l,r : longint; var a : arr1);
  var i,j,x : longint;
  begin
    i :=l;j:=r;
    x := a[(l+r) div 2];
    repeat
      while a[i] > x do inc(i);
      while a[j] < x do dec(j);
      if i<=j then
        begin
          swap(a[i],a[j]);
          inc(i);dec(j);
        end;
    until i>j;
    if i<r then qs(i,r,a);
    if j>l then qs(l,j,a);
  end;
procedure dfs(u : longint);
  var i,v,s : longint;
  begin
    cx[u] := false;
    if deg[u] <= 1 then begin f[u] := 1; exit; end;
    for v := 1 to n do
      if a[u,v] then
      if cx[v] then
        begin
          dfs(v);
          push(u,f[v]);
        end;
    qs(1,top[u],st[u]);
    s := st[u,1];
    v := st[u,1]-1;
    for i:= 2 to top[u] do
      if v < st[u,i] then
      begin
        s := s + (st[u,i]-v);
        v := v + (st[u,i]-v);
        v := v - 1;
      end else v := v-1;
    f[u] := s;
  end;
procedure process;
  begin
    fillchar(cx,sizeof(cx),true);
    dfs(1);
  end;
procedure print;
  begin
    assign(output,fo);rewrite(output);
    writeln(f[1]);
    close(output);
  end;
begin
  enter;
  process;
  print;
end.

C11STAR – SPOJ

Đề bài:

Thuật toán:

+ 20% test đầu với m, n ≤100:

– Với dữ liệu nhỏ như thế này ta có thể làm cách thô thiển là duyệt tất cả hình thỏa mãn là ngôi sao rồi tăng kết quả lên.

– Độ phức tạp: O((m*n)^2)

+ 30% test tiếp theo có m≤600, n ≤150:  

– Ở đây ta có thể tiếp cận bài toán theo hướng khác: đếm hình chữ nhật xiên 45 độ.

– Giờ ta nghĩ đến phương pháp quay sao cho quy bài toán về đếm hình chữ nhật, để ý là các ô thuộc cùng đường chéo thì có tổng X=i+j và hiệu Y=i-j giống nhau, từ đó ta có 1 phép biến đổi:

+ biến ô (i,j) thành ô (i+j,i-j) trong bảng mới.

Bây giờ ta có 1 bảng mới với kích thước (m+n)*(m+n) :

+ Gọi f[i][j][‘char’] là số cặp ký tự ‘char’ trong 2 cột i và j.

+ Duyệt O((m+n)^3) để tính mảng f, sau đó dùng O((m+n)^2) để cập nhật kết quả

→ kết quả là Sum(f[i][j][‘char’]*(f[i][j][‘char’]-1)/2);

+ Để ý là các ô có (i+j) mod 2=0. và (i+j) mod 2=1 không liên quan tới nhau, do đó ta có thể đưa về 2 bảng để giảm độ phức tạp 1 tý để ăn được subtask này.

– Độ phức tạp O((m+n)^3)

+ 50% test cuối có m≤3000, n ≤200:

– Ta có các nhận xét sau:

+ Bảng có tối đa (m+n) đường chéo

+ Hình ngôi sao to nhất cũng chỉ nằm trong phạm vi min(m,n)^2

Từ đó ta có cách giải:

+ Gọi f[i][j][‘char’] số cặp ký tự ‘char’ nằm trên 2 đường chéo i và j.

+ Duyệt m*n ô của bảng

+ Với mỗi ô ta duyệt min(m,n) ô cùng đường chéo với nó trở lên, nếu cùng ký tự:

→ tăng kết quả lên f[i][j][‘char’]

→ cập nhật f[i][j][‘char’]=f[i][j][‘char’]+1

– Độ phức tạp O(m*n*min(m,n))

Code:

const   fi      ='';
        fo      ='';
        maxM    =3000;
        maxN    =200;
 
var     f       :array['a'..'z',1..maxM+maxN,1..maxM+maxN] of integer;
        m, n    :longint;
        a       :array[0..maxM,0..maxN] of char;
 
procedure Optimize;
var     i, j,i1,j1    :longint;
        ans     :longint;
begin
        fillchar(f,sizeof(f),0);
        ans:=0;
        for i:=1 to m do
                for j:=1 to n do
                        if a[i,j]<>'.' then
                                begin
                                        i1:=i;j1:=j;
                                        while (i1<m) and (j1<n) do
                                                begin
                                                        inc(i1);inc(j1);
                                                        if a[i1,j1]=a[i,j] then
                                                                begin
                                                                        ans:=ans+f[a[i,j],i+j,i1+j1];
                                                                        inc(f[a[i,j],i+j,i1+j1]);
                                                                end;
                                                end;
                                end;
        writeln(ans);
end;
 
procedure run;
var     i, j    :longint;
begin
        assign(input,fi);assign(output,fo);
        reset(input);rewrite(output);
        readln(m, n);
        for i:=1 to m do
                begin
                for j:=1 to n do read(a[i,j]);
                readln;
                end;
        Optimize;
        close(input);close(output);
end;
 
begin
        run;
end.

DIFFSTR – spoj

Đề bài:

Thuật toán:

Solution ăn 60%:

Xét xâu S và dãy x[1..n] thỏa mãn 1 <= x[i] <= length(S) và x[i] > x[i – 1]. Với mỗi dãy x, ta thu được 1 xâu con của S: S[x[1]] S[x[2]] S[x[3]]… S[x[n]]

Để tạo ra được các xâu con phân biệt của S mà 2 phần tử liền kề khác nhau, ta chỉ xét đến những dãy x thỏa mãn điều kiện sau:

  1. S[x[i]] != S[x[i – 1]]
  2. Không tồn tại số k thỏa mãn x[i] < k < x[i + 1] và S[k] == S[x[i + 1]] (nói nôm na là nếu chọn ký tự ch nào đó để cho vào xâu con thì luôn chọn ký tự có chỉ số nhỏ nhất)

(cái đoạn in nghiêng này hình như không cần thiết :)))

 Gọi g[i][j] là số cách chọn dãy x[] có i phần tử mà x[i] = j.

 g[i][j] sẽ cập nhật cho g[i + 1][k] mà k là những giá trị mà khi thêm x[i + 1] = k thì vẫn đảm bảo điều kiện của dãy x[] ở trên (nhận xét là sẽ có không quá 26 giá trị của k)

g[i + 1][k] += g[i][j]

Cuối cùng, để tính kết quả bài toán:

Gọi:

  • f[i][j][0] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con bằng với xâu b[1..i]
  • f[i][j][1] là số cách chọn dãy x[] có i phần tử mà x[i] = j và dãy x này tạo ra 1 xâu con lớn hơn xâu b

Với mỗi f[i][j][t], tìm các giá trị k thỏa mãn thêm x[i + 1] = k vẫn đảm bảo thỏa mãn điều kiện của x[]:

– Nếu t = 1 thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] = b[i + 1] thì f[i + 1][k][0] += f[i][j]

– Nếu t = 0, S[x[k]] > b[i + 1] thì f[i + 1][k][1] += f[i][j]

– Nếu t = 0, S[x[k]] < b[i + 1] thì không làm gì hết

Kết quả bài toán = tổng f[i][j][1] + tổng f[length(b)][j][0]

Đpt ít hơn O(n * n * log(n)) n * n là mảng f, log(n) để tìm k, thực chất là không cần tính hết mảng f nên đpt sẽ nhỏ hơn khá nhiều

Solution ăn 100%:

QHĐ tương tự như trên, ta có thể tính được số xâu con của S[i..n] bắt đầu bằng ký tự ch bất kỳ mà thỏa mãn 2 ký tự liền kề khác nhau trong O(1)

Duyệt i từ đầu đến cuối xâu b, đến bước thứ i, đếm số xâu con trong S có dạng b[1..i – 1] + x với x là 1 xâu < S[i..m]. Số lượng xâu x = (số xâu con trong S[k..n] (k là vị trí kết thúc đầu tiên của xâu con b[1..i – 1] trong xâu S) bắt đầu bằng các ký tự < b[i]) + 1 (xâu rỗng)

Kết quả bài toán là tổng của các xâu trên – 1 (xâu rỗng)

Lưu ý là trong khi duyệt, nếu xâu b[1..i] không thỏa mãn điều kiện  2 ký tự liền kề khác nhau thì phải dừng duyệt ngay lập tức.

Solution O(N): của anh Nguyễn Tấn Sỹ Nguyên ( flash_mt )

Gọi F[i] là số cách chọn 1 subsequence ko có 2 phần tử kề nhau bằng nhau với S[i] là phần tử đầu tiên. Có thể tính F[] trong O(26N).

Sau đó ta đếm số lượng subsequence A thỏa A[1..k] = B[1..k] và A[k + 1] > B[k + 1]. Với mỗi giá trị k, xét A[k + 1] = c với c > B[k + 1], tìm vị trí u đầu tiên trong đoạn còn lại thỏa S[u] = c và tăng kết quả lên f[u]. Độ phức tạp của bước này là O(26(M + N)).

Code:

  • (đang cập nhập)

CASTLE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập thuật toán)

Code:

uses math;
const
    tfi='';//castle.inp';
    tfo='';//castle.out';
 
var
    fi,fo:text;
    n,top1,top2,top3,dem:longint;
    tg,kq1,kq2,kq11,kq22:int64;
    p,q,a,b:array[0..5001] of longint;
    st:array[0..5001] of int64;
procedure nhap;
    var i,j:longint;
    begin
        read(fi,n);
        for i:=1 to n do read(fi,a[i],b[i]);
        kq2:=high(int64);
    end;
 
procedure swap(var x,y:longint);
    var tg:longint;
    begin
        tg:=x;
        x:=y;
        y:=tg;
    end;
 
procedure sort(l,r:longint);
    var i,j,k,k1,k2:longint;
    begin
        i:=l;
        j:=r;
        k:=l+random(r-l+1);
        k1:=a[k];
        k2:=b[k];
        repeat
            while (a[i]<k1) or ((a[i]=k1) and (b[i]<k2)) do inc(i);
            while (a[j]>k1) or ((a[j]=k1) and (b[j]>k2)) do dec(j);
            if i<=j then
                begin
                    swap(a[i],a[j]);
                    swap(b[i],b[j]);
                    inc(I);
                    dec(j);
                end;
        until i>j;
        if i<r then sort(i,r);
        if l<j then sort(l,j);
    end;
 
procedure lam(u,v:int64);
    var i,j:longint;
    begin
        top3:=0;
        j:=1;
        for i:=1 to top1 do
            begin
                while (j<=top2)and ( p[j]<=q[i]) do
                    begin
                        if p[j]=q[i] then
                            begin
                                inc(top3);
                                st[top3]:=p[j];
                            end;
                        inc(j);
                    end;
            end;
        dem:=dem+int64(top3)*(top3-1) DIV 2;
        if top3>=2 then
        begin
        tg:=int64(st[top3]-st[1])*(v-u);
        if tg=kq1 then inc(kq11);
        if tg>kq1 then
            begin
                kq1:=tg;
                kq11:=1;
            end;
        end;
        for i:=2 to top3 do
            begin
                tg:=int64(st[i]-st[i-1])*(v-u);
                if tg=kq2 then inc(kq22);
                if tg<kq2 then
                    begin
                        kq2:=tg;
                        kq22:=1;
                    end;
            end;
    end;
 
procedure xuli;
    var i,j,k,k1:longint;
    begin
        sort(1,n);
        i:=1;
        a[n+1]:=-maxlongint;
        while i<n do
            begin
                top1:=0;
                for j:=i to n+1 do
                    if a[j]<>a[i] then break
                    else
                        begin
                            inc(top1);
                            q[top1]:=b[j];
                        end;
                if j>n then break;
                k:=j;
                while k<=n do
                    begin
                        top2:=0;
                        for k1:=k to n+1 do
                            if a[k1]<>a[k] then break
                            else
                                begin
                                    inc(top2);
                                    p[top2]:=b[k1];
                                end;
                        lam(a[i],a[k]);
                        k:=k1;
                    end;
                i:=j;
            end;
        writeln(fo,dem);
        if dem>0 then
            begin
                writeln(fo,kq1,' ',kq11);
                writeln(fo,kq2,' ',kq22);
            end;
    end;
 
begin
    assign(fi,tfi);
    assign(fo,tfo);
    reset(fi);
    rewrite(fo);
    nhap;
    xuli;
    close(fo);
end.

PVOI14_6 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include <bits/stdc++.h>
 
using namespace std;
 
int factorial(int n, long long MOD) {
    int ret = 1;
    for(int i = 1; i <= n; i++) ret = ((long long)(ret) * i) % MOD;
    return ret;
}
 
int power(int x, int k, long long MOD) {
    if (k == 0) return 1;
    long long t = power(x, k / 2, MOD);
    t = (t * t) % MOD;
    if (k % 2 == 1) t = (t * x) % MOD;
    return t;
}
 
int count_in_grid(int m, int n, int s) {
    return max(0, min(max(0, s - 1), m) - max(max(0, s - n), 1) + 1);
}
 
int calc(int m, int n, long long MOD) {
    int x = 1;
    for(int i = 1; i < m + m; i++) {
        int j = m + m + 1 - i;
        int k = count_in_grid(m - n, m - n, j) + 2 * count_in_grid(n, m - n, j - m);
        x = ((long long)(x) * power(i, k, MOD)) % MOD;
    }
    int ret = ((long long)(factorial((long long)(m) * m - (long long)(n) * n, MOD)) * power(x, MOD - 2, MOD)) % MOD;
    return ret;
}
 
int main()
{
    //freopen("L.inp","r",stdin);
    //freopen("L.out","w",stdout);
	int m, n ;
	long long MOD;
    cin >> m >> n >> MOD;
    cout << calc(m, n, MOD);
}

PVOI14_3 – spoj

Đề bài:


Thuật toán:


Ta có 1 công thức sau:

Gọi k là chi phí nhỏ nhất cần tìm.

Nếu tồn tại một chuyến đi để mất chi phí là k thì

(S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp) = k

⇔ S1 + S2 + … + Sp – k * (T1 + T2 + … + Tp) = 0

⇔ (S1 – k * T1) + (S2 – k * T2) + … + (Sp – k * Tp) = 0.

 

Giả sử tồn tại 1 chuyến đi có chi phí km < k khi đó ta có:

kmin < k = (S1 + S2 + .. + Sp) / (T1 + T2 + … + Tp)

⇔ (S1 – kmin * T1) + (S2 – kmin * T2) + … + (Sp – kmin * Tp) > 0

 

Từ đây ta có nghĩ ra 1 thuật toán như sau.

  • Chặt nhị phân chi phí nhỏ nhất(x), với mỗi chi phí Mình tạo trọng số mỗi cho mỗi cạnh (s ,t) -> (s – x * t)
  • Nếu tồn tại 1 chu trình âm với trọng số mới -> không thể tạo ra chi phí là x.
  • Ngược lại nếu không tồn tại 1 chu trình âm nào thì kết quả cần tìm sẽ <=x
    => Chúng ta có thể sử dụng thuật toán FordBellman để tìm chu trình âm

Code:


#include <bits/stdc++.h>
 
using namespace std;
 
#define N 1010
#define M 10010
const double esp = 1e-5;
 
int n, m,  trace[N], u[M], v[M], c[M];
double d[N];
 
bool Ok(int x, int y) {
    while (x != 1){
        x = trace[x];
        if (x == 0) return false;
        if (x == y) return true;
    }
    return false;
}
bool FordBellman(double mid) {
    for (int i = 1; i<=n; i++) d[i] = 1e18;
    d[1] = 0;
    memset(trace, 0, sizeof trace);
    for (int i = 0; i<n; i++) {
        for (int j = 0; j<m; j++) {
            int x = u[j]; int y = v[j];
            if (d[y] > d[x] + c[j] - mid) {
                d[y] = d[x] + c[j] - mid;
                if (Ok(x, y)) {
                    return true;
                }
                trace[y] = x;
            }
        }
    }
    return false;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin>>n>>m;
    for (int i = 0; i<m; i++) {
        cin>>u[i]>>v[i]>>c[i];
    }
    double l = 0;
    double r = 1e10;
    double cur = 0;
    while (r - l >= esp) {
        double mid = (l + r) / 2;
        if (!FordBellman(mid)) {
            cur = mid;
            l = mid;
        }else r = mid;
    }
    if (abs (cur - 1e10) <=esp) {
        cout<<"NO TOUR";
    }else
    cout<<fixed<<setprecision(2)<<cur;
}
{$MODE OBJFPC}
program SmartDogContest;
const
  InputFile  = '';
  OutputFile = '';
  maxN = 1000;
  maxM = 10000;
  maxW = 1000000000;
  maxD = (maxN + 1) * maxW;
type
  TEdge = record
    u, v, c: Integer;
  end;
var
  fi, fo: TextFile;
  e: array[1..maxM] of TEdge;
  d: array[1..maxN + 1, 1..maxN] of Int64;
  n, m: Integer;
  BestMiu: Extended;
 
procedure Enter;
var
  i: Integer;
begin
  ReadLn(fi, n, m);
  for i := 1 to m do
    with e[i] do
      ReadLn(fi, u, v, c);
end;
 
procedure Init;
var
  i: Integer;
begin
  FillQWord(d, SizeOf(d) div 8, maxD);
  for i := 1 to n do
    d[1, i] := 0;
end;
 
procedure Minimize(var target: Int64; value: Int64); inline;
begin
  if target > value then target := value;
end;
 
procedure Optimize;
var
  k, i: Integer;
begin
  for k := 2 to n + 1 do //Tinh d[k, v] qua cac d[k - 1, u]
    for i := 1 to m do
      with e[i] do
        Minimize(d[k, v], d[k - 1, u] + c);
end;
 
procedure GetBest;
var
  v, k: Integer;
  min, max, trial: Extended;
begin
  min := maxD;
  for v := 1 to n do
    if d[n + 1, v] < maxD then
      begin
        max := -maxD;
        for k := 1 to n do
          if d[k, v] < maxD then
            begin
              trial := (d[n + 1, v] - d[k, v]) / (n - k + 1);
              if max < trial then max := trial;
            end;
        if max < min then
          min := max;
      end;
  BestMiu := min;
end;
 
begin
  AssignFile(fi, InputFile); Reset(fi);
  AssignFile(fo, OutputFile); Rewrite(fo);
  try
    Enter;
    Init;
    Optimize;
    GetBest;
    if BestMiu = maxD then
      Write(fo, 'NO TOUR')
    else
      Write(fo, BestMiu:0:2);
  finally
    CloseFile(fi); CloseFile(fo);
  end;
end.

PVOI14_2 – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

using namespace std;
#include<bits/stdc++.h>
#define FOR(i, a, b) for (int i = a; i < b; i++)
#define FORE(i, a, b) for (int i = a; i <= b; i++)
#define FORD(i, a, b) for (int i = a; i >= b; i--)
const int MAXN = 5*1e6;
const int INF = 1e9 + 7;
typedef pair<int, int> ii;
 
int p[MAXN], a[1001][1001];
vector < ii > adj[MAXN];
int n, maxa;
 
int get(int i, int j)
{
    return (i - 1) * n + j;
}
 
int pa(int x)
{
    while (p[x] > 0) x = p[x];
    return x;
}
 
int Union(int r1, int r2)
{
    int tmp = p[r1] + p[r2];
    if (p[r1] < p[r2]){
        p[r2] = r1;
        p[r1] = tmp;
    } else{
        p[r1] = r2;
        p[r2] = tmp;
    }
    return -tmp;
}
 
int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
//	freopen("RSELECT.inp", "r", stdin);
  //  freopen("RSELECT.out", "w", stdout);
    cin >> n;
    FORE(i, 1, n) FORE(j, 1, n) {
        cin >> a[i][j];
        maxa = max(maxa, a[i][j]);
    }
    FORE(i, 1, n) FORE(j, 1, n){
        int u = get(i, j);
        if (i < n) adj[abs(a[i][j] - a[i + 1][j])].push_back(ii(u, get(i + 1, j)));
        if (j < n) adj[abs(a[i][j] - a[i][j + 1])].push_back(ii(u, get(i, j + 1)));
    }
    memset(p, -1, sizeof(p));
    int ans = 0;
    FORE(ll, 0, maxa){
        FOR(i, 0, adj[ll].size()) {
            p[adj[ll][i].first] = -1;
            p[adj[ll][i].second] = -1;
           // cout<<ll<<" "<<adj[ll][i].first<<" "<<adj[ll][i].second<<endl;
        }
        FOR(i, 0, adj[ll].size()){
            int u = adj[ll][i].first, v = adj[ll][i].second;
            int r1 = pa(u), r2 = pa(v);
            if (r1 != r2) ans = max(ans, Union(r1, r2));
        }
    }
    cout<<ans<<endl;
	return 0;
}