NKLUCK – spoj

Đề bài:

Thuật toán:

    Để giải bài toán này, ta giải bài toán trung gian khác như sau
    Gọi

    • A là số đoạn nhận X là phần tử trung vị
    • B là số đoạn nhận X + 1 là phần tử trung vị

    => Result = (A – B) / (n * (n + 1) / 2) ;

    Để tính số đoạn nhận X là phần tử trung vị ta chuyển đổi mảng A về, nếu A[i] >= X => A[i] = 1 ngược lại A[i] = 0.

    Một đoạn nhận X là trung vị khi và chỉ khi tổng của đoạn đó ko âm. Đến đây, ta dùng cây BIT để tính toán .

Code:

#include <bits/stdc++.h>
using namespace std;
 
#define FOR(i, a, b) for (int i = a; i <= b; ++i)
#define long long long
 
const int N = 1e6+10;
 
class FenwickTree {
private:
    long t[N][2];
public:
    void update(int x, int type) {
        for (; x <= N; x += x & -x)
            t[x][type]++;
    }
    long get(int x, int type) {
        long res = 0;
        for (; x > 0; x -= x & -x)
            res += t[x][type];
        return res;
    }
} BIT;
 
int n, m, k;
int a[N], f[N], b[N];
 
void Enter() {
    scanf("%d%d", &n, &k);
    FOR(i, 1, n) scanf("%d", &a[i]);
}
 
long calc(int x, int type) {
    m = 0;
    for (int i = 1; i <= n; ++i) {
        f[i] = f[i-1] + (a[i] >= x);
        b[++m] = 2 * f[i] - i - 1;
        b[++m] = 2 * f[i-1] - i;
    }
 
    sort(b + 1, b + m + 1);
 
    long res = 0;
    FOR(i, 1, n) {
        int cur = lower_bound(b + 1, b + m + 1, 2 * f[i - 1] - i) - b;
        BIT.update(cur, type);
        cur = lower_bound(b + 1, b + m + 1, 2 * f[i] - i - 1) - b;
        res += BIT.get(cur, type);
    }
    return res;
}
 
void Process() {
    long res = calc(k, 0) - calc(k + 1, 1);
    double ans = 1ll * n * (n + 1) / 2;
    ans = res / ans;
    printf("%.6lf", ans);
}
 
int main() {
 //   freopen("input.in", "r", stdin);
 
    Enter();
    Process();
 
    return 0;
}

LATGACH4 – spoj

Đề bài:

Thuật toán:

    Gọi f[i] là số cách xếp gạch
    dùng viên gạch 1×2 => f[i] = f[i – 2];
    dùng viên gạch 2×2 => f[i] = f[i – 1];
    => f[i] = f[i – 1] + f[i – 2];
    Do n quá lớn nên mình có thể dùng nhân ma trận tốn O(log2(n))

Code:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
const int mod = 111539786;
 
map <ll, ll> f;
 
ll get(ll n)
{
    if (f.count(n)) return f[n];
    ll k=n / 2;
    if (!(n % 2))
        return f[n]=(get(k)*get(k) + get(k-1)*get(k-1)) % mod;
    else
        return f[n]=(get(k)*get(k+1) + get(k-1)*get(k)) % mod;
}
main()
{
    int t, n;
    cin>>t;
    while (t--)
    {
        cin>>n;
        f[0]=f[1]=1;
        cout<<get(n)<<endl;
    }
}

QHROAD – spoj

Đề bài:

Thuật toán:

  • Kruskal những đoạn đường không bị phá.
  • Duyệt các truy vấn từ Q về 1. Nếu join thì giảm số tplt

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<int,int> 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 = 1E5+3;
const ll oo = 1e18+3;
 
struct  edge {
	int u,v;
} e[MAXN];
int n, m, q, pa[MAXN], u , v, x, a[MAXN], tplt, ans[MAXN];
bool dt[MAXN];
 
int find(int u) {
	if (pa[u]!=u) pa[u] = find(pa[u]);
	return pa[u];
}
 
bool join(int u, int v) {
	int i = find(u);
	int j = find(v);
	if (i==j) return 0;
	else
	pa[i] = j;
	return 1;
}
 
int main() {
	cin >> n >> m >> q;
	FOR(i,1,m) {
		cin >> e[i].u >> e[i].v;
	}
	FOR(i,1,q) {
		cin >> x;
		dt[x] = 1;
		a[i] = x;
	}
	tplt = n;
	FOR(i,1,n) pa[i] = i;
	FOR(i,1,m)
	if (!dt[i]) {
		if (join(e[i].u,e[i].v)) tplt--;
	}
	FORD(i,q,1) {
		ans[i] = tplt;
		int id = a[i];
		if (join(e[id].u,e[id].v)) tplt--;
	}
	FOR(i,1,q) cout << ans[i] << endl;
   	return 0;
}

Hàm atoi trong C/C++ – chuyển xâu thành số nguyên

Mô tả

Chuyển chuỗi kí tự thành số nguyên

Khai báo

int atoi(const char *str)

  • str là chuỗi ký tự cần chuyển sang số nguyên. VD: str=”5678123″

Ví dụ:

  • atoi(“101”);
  • atoi(‘5’);

Cần khai báo thư viện stdlib.h trước khi sử dụng.

Giá trị trả về

Trả về số nguyên kiểu int. Nếu xâu không có dạng số nguyên thì trả về giá trị 0

Ví dụ

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
int main () {
   int val;
   char str[20];
 
   strcpy(str, "98993489");
   val = atoi(str);
   printf("String value = %s, Int value = %d\n", str, val);
 
   strcpy(str, "tutorialspoint.com");
   val = atoi(str);
   printf("String value = %s, Int value = %d\n", str, val);
 
   return(0);
}

Kết quả:

String value = 98993489, Int value = 98993489
String value = tutorialspoint.com, Int value = 0

Học toán rời rạc để làm gì?

Toán rời rạc đa phần là lý thuyết nên nhiều bạn thường đặt ra câu hỏi học toán rời rạc thì để làm gì.

Vậy học toán rời rạc để làm gì?

  • Lý thuyết tập hợp (ánh xạ tập hợp giao hợp, quan hệ) giúp ta xây dựng hệ quản trị cơ sở dữ liệu.
  • Lý thuyết đồ thị giúp bạn xấy dựng các mạng lướti truyền tin. Giải được các bài toàn về đồ thị. Như giải thuật BFS thường được dùng trong các rounter để tìm đường đi ngắn nhất.
  • Cây thì nhờ đó có thuật giải huffman giúp nén thông tin. hoặc giúp làm cây quyết định, xây dựng chiến thuật min-max dùng trong trí tuệ nhân tạo để giải quyết các bài toàn về chơi cờ, nim. Xây dựng cây tiền tố, hậu tố để máy tính có thể hiểu và tính toán đc các phép tính thông thường của con người.
  • Học về độ tăng của hàm giúp ta đánh giá thuật toán từ đó chọn thuật toán thích hợp cho mỗi bài toán đề ra.
  • Lý thuyết số có vài ứng dụng trong Cryptography. Ví dụ như lý thuyết đồng dư của TRR.
  • Xác xuất thống kê được ứng dụng trong AI.
  • Ngoài ra rời rạc còn giúp ta hiểu cách máy tính biểu diễn các số như thế nào.

 

PCIRCLE – spoj

Đề bài:

Thuật toán:

  • Duyệt cấu hình tổ hợp

Code:

uses    math;
 
const   fi='';
        fo='';
        maxn=10;
 
type    data=longint;
 
var     x       :array[1..2*maxn] of longint;
        i,j,n,m :longint;
        st      :array[1..2*maxn] of longint;
        kq      :array[1..10001,1..2*maxn] of longint;
        res     :int64;
        cx      :array[1..2*maxn] of boolean;
 
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);
        close(input);
end;
 
function ngto(x : longint) : boolean;
var     i       :longint;
begin
        for i:=2 to trunc(sqrt(x)) do
                if x mod i = 0 then exit(false);
        exit(true);
end;
 
procedure cnkl;
begin
        if ngto(x[2*n]+x[1]) then
                begin
                        inc(res);
                        if res<=10000 then
                        kq[res] := x;
                end;
end;
 
procedure try(i : longint);
var     j :longint;
begin
        for j:= 1 to 2*n do
                if cx[j] then
                        if ngto(j+x[i-1]) then
                        begin
                                x[i] := j;
                                cx[j] := false;
                                if i=2*n then cnkl else try(i+1);
                                cx[j] := true;
                        end;
end;
procedure process;
begin
        {for i:=2 to 2*n do
                if ngto(i) then
                        begin
                                inc(m);
                                st[m] := i;
                        end;     }
        fillchar(cx,sizeof(cx),true);
        cx[1] := false;
        x[1] := 1;
        try(2);
end;
 
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        for i:=1 to min(res,10000) do
                begin
                        for j:=1 to 2*n do write(kq[i,j],' ');
                        writeln;
                end;
        close(output);
end;
 
begin
        enter;
        process;
        print;
end.

QBSCHOOL – spoj

Đề bài:

Thuật toán:

  • Gọi Gọi f[i] và d[i] lần lượt là độ dài và số đường đi ngắn nhất từ đỉnh 1 đến đỉnh i.
  • Để tính d[i] ta sử dụng thuật toán Dijkstra
  • Để tính số lượng đường đi ngắn nhất giữa hai đỉnh ta tính như sau
  • Nếu d[v]>d[u]+c(u,v), ta gán d[v]=d[u]+c(u,v) và f[v]=f[u]

    Nếu d[v]=d[u]+c(u,v) thì gán f[v]=f[v]+f[u].

    (có thể xem rõ hơn ở code bên dưới)

Code:

const   fi      ='';
        fo      ='';
        maxn    =30000+3;
        maxc    =trunc(1e9)+3;
        maxm    =trunc(1e5);
type    arrd    =array[1..maxn] of longint;
        arrf    =array[1..maxn] of int64;
        arrk    =array[-maxm..maxm] of longint;
        arrh    =array[1..maxn] of longint;
var     d1,dn,d   :arrd;
        f1,fn,f   :arrf;
        n,i,j,m   :longint;
        res     :longint;
        ans     :arrd;
        head :array[1..maxn] of longint;
        link,ts,ke    :arrk;
        // dijkstra heap;
        h,p     :array[1..maxn] of longint;
        nh      :longint;
procedure add(i,u,v,w:longint);
begin
        link[i]:=head[u];
        head[u]:=i;
        ke[i]:=v;
        ts[i]:=w;
end;
procedure enter;
var     u,v,w,k:longint;
begin
        assign(input,fi);reset(input);
        readln(n,m);
        for i:=1 to m do
                begin
                        read(k,u,v,w);
                        add(i,u,v,w);
                        if k=2 then add(-i,v,u,w);
                end;
        close(input);
end;
procedure swap(var x,y:longint);
var     tg:longint;
begin
        tg:=x;x:=y;y:=tg;
end;
procedure upheap(i:longint);
var     j:longint;
begin
        j:=i div 2;
        if i>1 then
        if d[h[i]] < d[h[j]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        upheap(j);
                end;
end;
procedure downheap(i:longint);
var     j:longint;
begin
        j:=i + i;
        if j>nh then exit;
        if (j<nh) and (d[h[j]] > d[h[j+1]]) then inc(j);
        if d[h[j]] < d[h[i]] then
                begin
                        swap(h[i],h[j]);
                        swap(p[h[i]],p[h[j]]);
                        downheap(j);
                end;
end;
procedure push(i:longint);
begin
        inc(nh);
        h[nh]:=i;
        p[i]:=nh;
        upheap(nh);
end;
function pop:longint;
begin
        pop:=h[1];
        h[1]:=h[nh];
        p[h[1]]:=1;
        dec(nh);
        downheap(1);
end;
procedure update(i:longint);
begin
        if p[i]=0 then push(i) else upheap(p[i]);
end;
procedure dijkstra(s:longint);
var     u,v,i:longint;
begin
        fillchar(h,sizeof(f),0);
        fillchar(p,sizeof(p),0);
        nh:=0;
        fillchar(f,sizeof(f),0);
        for i:=1 to n do d[i]:=maxc;
        d[s]:=0;
        f[s]:=1;
        push(s);
        repeat
                u:=pop;
                i:=head[u];
                while i<>0 do
                        begin
                                v:=ke[i];
                                if d[v]>d[u]+ts[i] then
                                        begin
                                                d[v]:=d[u]+ts[i];
                                                f[v]:=f[u];
                                                update(v);
                                        end
                                        else
                                if d[v]=d[u]+ts[i] then
                                        begin
                                                f[v]:=f[u]+f[v];
                                        end;
                                i:=link[i];
                        end;
        until nh=0;
end;
procedure process;
begin
        dijkstra(1);
        f1:=f;
        d1:=d;
        dijkstra(n);
        fn:=f;
        dn:=d;
        for i:=1 to n do
                if (d1[i]+dn[i]<>d1[n])
                or (f1[i]*fn[i]<>f1[n]) then
                        begin
                                inc(res);
                                ans[res]:=i;
                        end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(d1[n],' ',f1[n]);
        close(output);
end;
begin
        enter;
        process;
        print;
end.
#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
 
using namespace std;
 
typedef pair<long long, int> lli;
 
const long long oo = ((1 << 30)-1)*2-1;
const int max_n = 5000+1;
 
int n, m;
long long min_d, dist = 0, f[max_n];
vector<lli> adj[max_n];
 
inline void load_map()
{
    cin >> n >> m;
    int type, u, v, w;
    while (m--)
    {
        cin >> type >> u >> v >> w;
        adj[u].push_back(lli(w, v));
        if (type==2) adj[v].push_back(lli(w, u));
    }
}
 
inline void dijkstra()
{
    vector<lli>::iterator it;
    long long cuv, du, d[max_n];
    int u, v;
    priority_queue<lli, vector<lli>, greater<lli> > heap;
    for (u=1; u <= n; u++) d[u] = +oo;
    memset(f, 0, sizeof(f));
    d[1] = 0; f[1] = 1;
    heap.push(lli(0, 1));
    while (heap.size())
    {
        du = heap.top().first; u = heap.top().second;
        heap.pop();
        if (du != d[u]) continue;
        if (u == n) break;
        for (it=adj[u].begin(); it != adj[u].end(); it++)
        {
            cuv = it->first; v = it->second;
            if (d[v]==d[u]+cuv) f[v] += f[u];
            if (d[v] > d[u]+cuv)
            {
                d[v] = d[u]+cuv;
                f[v] = f[u];
                heap.push(lli(d[v], v));
            }
        }
    }
    min_d = d[n];
}
 
main()
{
    load_map();
    dijkstra();
    cout << min_d << " " << f[n];
}