CBUYING – spoj

Đề bài:

Thuật toán:

  • Chọn số những sô cô la có giá rẻ nhất

Code:

#include <bits/stdc++.h>
using namespace std;
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define FORD(i,b,a) for (int i=(b),_a=(a);i>=_a;i=i-1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define FORE(i,v) for (__typeof((v).begin()) i=(v).begin();i!=(v).end();i++)
#define ALL(v) (v).begin(),(v).end()
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
#define double db
typedef long long ll;
typedef pair<ll,ll> PII;
const ll mod=1000000007;
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
const int MAXN = 1E6+3;
const int oo = 1e9+3;
 
int n;
ll ans, b;
PII a[MAXN];
 
bool cmp(PII a, PII b) {
    return (a.fi < b.fi);
}
 
int main() {
    cin >> n >> b;
    FOR(i,1,n) cin >> a[i].fi >> a[i].se;
    sort(a+1,a+n+1,cmp);
    FOR(i,1,n) {
        if (b < a[i].fi) break;
        ll tmp = b / a[i].fi;
        b -= min(tmp,a[i].se) * a[i].fi;
        ans += min(tmp,a[i].se);
    }
    cout << ans;
	return 0;
}

COLOREC – spoj

Đề bài:

Thuật toán:

Với bài này ta gán mỗi màu cho một bit từ 0 đến 3, sau đó có thể quy hoạch động để đếm như sau:

Cố định 2 dòng i và j, ta đếm số hình chữ nhật 4 màu có cạnh nằm trên dòng i và j như sau:

Gọi F(c) là số cặp đỉnh có màu là c (c là tổng màu của 2 đỉnh đó) thì số hình chữ nhật 4 màu nhận được từ 2 đỉnh đó là F(15 – c).

Từ đó ta có thể dùng 3 vòng for để tính như trong code.

Code:

#include <iostream>
#include <vector>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n; cin >> n;
    vector< vector<int> > a(401, vector<int>(401, 0));
    while (n--) {
        int u, v, c; cin >> u >> v >> c;
        a[u + 200][v + 200] = 1 << (c - 1);
    }
#define rep(i, a, b) for (int i=a; i<=b; i++)
#define LL long long
    LL res = 0;
    rep(i, 0, 400) rep(j, 0, i) {
        vector<LL> f(16, 0);
        rep(k, 0, 400) if (a[i][k] && a[j][k] && a[i][k] != a[j][k]) {
            int c = a[i][k] | a[j][k];
            res += f[15 - c];
            f[c]++;
        }
    }
    cout << res;
    return 0;
}

CROSS12 – spoj

Đề bài:


Thuật toán:


Đầu tiên ta cần tính thời gian qua cầu của mỗi người (khi đi một mình). Có thể tính bằng tham lam như cách được sử dụng trong code ở trên hoặc kết hợp quy hoạch động với deque để tìm min trên đoạn tịnh tiến.

Độ phức tạp khi tính là $O(m)$ cho mỗi người, vì $r$ chỉ dao động từ 1 đến 100 nên ta dùng một mảng phụ để cache giá trị đã tính lại.

Sau khi tính xong, gọi thời gian qua cầu của $n$ người là $A(n)$, ta sắp xếp $A$ tăng dần.

Gọi $F(i)$ là thời gian ít nhất để những người từ 1 đến i qua cầu, ta có công thức:

$ F(1) = A(1) \ F(2) = A(2) \ F(i) = min \begin{cases} F(i-2) + A(1) + 2A(2) + A(i) & \quad (1)\ F(i-1) + A(1) + A(i) & \quad (2)\ \end{cases} $

Trong trường hợp $(1)$, ta cho $A(2)$ quay về, sau đó $A(i)$ và $A(i-1)$ qua cầu, sau đó $A(1)$ từ bên kia cầu quay về, $A(1)$ và $A(2)$ cùng qua cầu.

Trong trường hợp $(2)$, $A(1)$ quay về sau đó cùng $A(i)$ qua cầu.

Code:


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int time(int r, int m, const char *bridge) {
    int i = 0, res = 1;
    while (i + r <= m) {
        res++;
        i += r;
        while (bridge[i] == '1') i--;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (auto &x: a) cin >> x;
    string bridge; cin >> bridge;
    bridge = '0' + bridge + '0';
    vector<int> cache(101, 0);
    for (auto &x: a) {
        if (!cache[x]) x = cache[x] = time(x, m, bridge.data());
        else x = cache[x];
    }
    sort(a.begin(), a.end());
    if (n == 1) cout << a[0];
    else if (n == 2) cout << a[1];
    else {
        int f0 = a[0], f1 = a[1];
        for (int i=2; i<n; i++) {
            int f2 = min(f0 + a[0] + 2*a[1] + a[i], f1 + a[0] + a[i]);
            f0 = f1, f1 = f2;
        }
        cout << f1;
    }
    return 0;
}

NKTICK – spoj

Đề bài:


Thuật toán:


  • Quy hoạch động

Code:


const   fi='';
        fo='';
        max=30000;
var n,i:longint;
t:array[1..60000] of integer;
f:array[-1..60000] of longint;
r:array[0..59999] of integer;
w:text;
function min(x,y:longint):longint;
begin
    if x>y then min:=y else min:=x;
end;
procedure nhap;
begin
    assign(w,fi);
    reset(w);
    readln(w,n);
    for i:=1 to n do read(w,t[i]);
    for i:=1 to n-1 do read(w,r[i]);
    close(w);
end;
procedure xuly;
begin
        f[0]:=0; f[-1]:=0; r[0]:=max;
        for i:=1 to n do
        f[i]:=min(f[i-1]+t[i],f[i-2]+r[i-1]);
end;
procedure inkq;
begin
        assign(w,fo);
        rewrite(w);
        writeln(w,f[n]);
        close(w);
end;
begin
    nhap;
    xuly;
    inkq;
end.

P152SUMI – ptit

Đề bài:


Thuật toán:


Tạo một mảng quy hoạch có dạng
xau[i]==xau[i+1]? arr[i+1]=arr[i]+1 : arr[i+1]=arr[i];
với arr[0]=0;
VD: #..###
ta có;
arr[0] = 0;
arr[1] = 0; (#.)
arr[2] = 1; #(..)
arr[3] = 1; #.(.#)
arr[4] = 2; #..(##)
arr[5] = 3; #..#(##)

arr[i+1] = số cặp kí tự giống nhau từ xâu[0 -> i];
-> Với mỗi truy vấn ta có:
Số cặp giống nhau từ l->r = arr[r-1] – arr[l-1];

Code:


#include <iostream>
#include <string>
using namespace std;
 
int main ()
{
	string xau;
	cin>>xau;
	int arr[100005];
	arr[0]=0;
	for (int i=0; i<xau.size()-1; i++)
	{
		if (xau[i]==xau[i+1])
			arr[i+1]=arr[i]+1;
		else
			arr[i+1]=arr[i];
	}
	int m;
	cin>>m;
	for (int i=1; i<=m; i++)
	{
		int l, r;
		cin>>l>>r;
		cout<<arr[r-1]-arr[l-1]<<endl;
	}
	return 0;
}

NKPATH – spoj

Đề bài:


Thuật toán:


Với mỗi ô (i,j) với  $i=1..m; j=1..n-1;$ kiểm tra xem ô (ii,jj) với $ii=1..i-1; jj=1..j;$ có đi được đến ô (i,j) không

  • Nếu có
    l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
    

Kết quả: $\sum_{i=1}^{m}L[i][n]$

Code:


const   fi='';
        fo='';
        maxn=100;
        base=1000000000;
type    arra=array[1..maxn,1..maxn] of integer;
        arrl=array[1..maxn,1..maxn] of longint;
var     a:arra;
        i,j,m,n:byte;
        l:arrl;
        f:text;
        res:int64;
procedure nhap;
begin
    assign(f,fi);
    reset(f);
    readln(f,m,n);
    for i:=1 to m do
        for j:=1 to n do read(f,a[i,j]);
    close(f);
end;
procedure init;
begin
    for i:=1 to m do l[i,1]:=1;
 
    res:=0;
end;
function kt(x,y:longint):boolean;
var     tmp:longint;
begin
        while y>0 do
        begin
            x:=x mod y;
            tmp:=x;
            x:=y;
            y:=tmp;
        end;
        if x=1 then exit(false) else exit(true);
end;
procedure xuly;
var     ii,jj:byte;
begin
    for i:=1 to m do
        for j:=1 to n-1 do
        begin
            for ii:=i-1 downto 1 do
                for jj:=j downto 1 do
                        if kt(a[i,j],a[ii,jj]) then l[i,j]:=(l[i,j]+l[ii,jj]) mod base;
            for jj:=j-1 downto 1 do
                if kt(a[i,j],a[i,jj]) then l[i,j]:=(l[i,j]+l[i,jj]) mod base;
        end;
 
    for i:=1 to m do
        for ii:=i downto 1 do
                for jj:=n-1 downto 1 do
                if kt(a[i,n],a[ii,jj]) then res:=(res+l[ii,jj]) mod base;
end;
procedure xuat;
begin
    assign(f,fo);
    rewrite(f);
    writeln(f,res);
    close(f);
end;
begin
    nhap;
    init;
    xuly;
    xuat;
end.

C11BC1 – spoj

Đề bài:


Thuật toán:


  • (đang cập nhập)

Code:


uses math;
const
  fi='';
  fo='';
  maxn=trunc(1e5);
  maxk=50;
  base=790972;
var
  f : array[0..maxn,0..maxk] of int64;
  i,j,n,k,m : longint;
  kq : int64;
  a,b : array[1..maxn] of longint;
procedure enter;
begin
  assign(input,fi);reset(input);
  readln(n,k);
  for i:=1 to n do read(a[i],b[i]);
  close(input);
end;
procedure swap(var x,y: longint);
var tg : longint;
begin
  tg:=x;x:=y;y:=tg;
end;
procedure qs(l,r : longint);
  var i,j,x : longint;
  begin
    i:=l;j:=r;
    x:=b[(l+r) div 2];
    repeat
      while x>b[i] do inc(i);
      while x<b[j] do dec(j);
      if i<=j then
        begin
          swap(b[i],b[j]);
          swap(a[i],a[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 muk(x : longint) : int64;
  var i : longint;
  begin
    muk := 1;
    for i:=1 to k do muk:=muk*x;
  end;
function cnk(n,k : longint) : int64;
  begin
    cnk := 1;
    for i:=n-k+1 to n do cnk := cnk*i;
    for i:=1 to k do cnk := cnk div i;
  end;
function tinh : int64;
begin
  fillchar(f,sizeof(f),0);
  for i:=0 to m do f[i,0] := 1;
  for i:=1 to m do
    for j:=1 to min(k,i) do
      f[i,j] := (f[i-1,j] + f[i-1,j-1]*a[i]) mod base;
  exit(f[m,k]);
end;
procedure process;
var i,j,dem : longint;
    dau,cuoi : longint;
begin
  qs(1,n);
  m := n;
  kq := tinh;
  dau := 1;
  while (dau<=n) do
  begin
    cuoi := dau+1;
    m := 1; a[1] := a[dau];
    while (cuoi<=n) and (b[cuoi]=b[dau]) do
      begin
        m := m+1;
        a[m] := a[cuoi];
        inc(cuoi);
      end;
    if cuoi-dau>=k then
      kq := (kq - tinh + base + base) mod base;
    dau := cuoi;
  end;
end;
procedure print;
begin
  assign(output,fo);rewrite(output);
  writeln(kq);
  close(output);
end;
begin
  enter;
  process;
  print;
end.