Nguyên tắc viết ký hiệu toán học mà ai cũng phải biết

Nhiều bạn tưởng rằng ký hiệu $x$ là giống $\mathbf{x}$. Nhưng không phải, x không in đậm là chỉ biến còn x in đậm là ký hiệu của vector. Nó khác nhau một trời một vực đấy nhé!

Trong các bài viết của tôi, các số vô hướng được biểu diễn bởi các chữ cái viết ở dạng không in đậm, có thể viết hoa, ví dụ $x_1, N, y, k$. Các vector được biểu diễn bằng các chữ cái thường in đậm, ví dụ $\mathbf{y}, \mathbf{x}_1 $. Nếu không giải thích gì thêm, các vector được mặc định hiểu là các vector cột. Các ma trận được biểu diễn bởi các chữ viết hoa in đậm, ví dụ $\mathbf{X, Y, W} $.

Đối với vector, $\mathbf{x} = [x_1, x_2, \dots, x_n]$ được hiểu là một vector hàng. Trong khi $\mathbf{x} = [x_1; x_2; \dots; x_n] $ được hiểu là vector cột. Chú ý sự khác nhau giữa dầu phẩy (,) và dấu chấm phẩy (;). Đây chính là ký hiệu mà được Matlab sử dụng.

Tương tự, trong ma trận, $\mathbf{X} = [\mathbf{x}_1, \mathbf{x}_2, \dots, \mathbf{x}_n]$ được hiểu là các vector $\mathbf{x}_j$ được đặt cạnh nhau theo thứ tự từ trái qua phải để tạo ra ma trận $\mathbf{X}$. Trong khi $\mathbf{X} = [\mathbf{x}_1; \mathbf{x}_2; \dots; \mathbf{x}_m]$ được hiểu là các vector $\mathbf{x}_i$ được đặt chồng lên nhau theo thứ tự từ trên xuống dưới dể tạo ra ma trận $\mathbf{X}$. Các vector được ngầm hiểu là có kích thước phù hợp để có thể xếp cạnh hoặc xếp chồng lên nhau.

Cho một ma trận $\mathbf{W}$, nếu không giải thích gì thêm, chúng ta hiểu rằng $\mathbf{w}_i$ là vector cột thứ $i$ của ma trận đó. Chú ý sự tương ứng giữa ký tự viết hoa và viết thường.

Mình đã muốn viết bài này từ lâu rồi những đến giờ mới hoàn thành được. Mình mong các bạn có thể phân biết được các ký hiệu toán học, chứ không thì cứ nhầm tùm lum giữa các ký hiệu, dẫn đến hiểu sai lệch.

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.