IOIBIN – spoj

Đề bài:

Thuật toán:

Code:

const   fi = '';
        fo = '';
        maxn = trunc(1e4)+3;
var     p : array[1..maxn] of longint;
        i,j,n,m : longint;
        x,u,v : longint;
procedure chuanbi;
begin
        for i:=1 to maxn do p[i]:=i;
end;
function find(i:longint):longint;
begin
        while p[i]<>i do i:=p[i];
        exit(i);
end;
procedure lam1;
var     i,j : longint;
begin
        i:=find(u);
        j:=find(v);
        if i<>j then
        if i<j then p[j]:=p[i] else p[i]:=p[j];
end;
procedure main;
var     i:longint;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);
        readln(m);
        chuanbi;
 
        for i:=1 to m do
                begin
                        readln(u,v,x);
                        if x=1 then lam1 else
                                if find(u)=find(v) then writeln(1) else writeln(0);
                end;
        close(input);
        close(output);
end;
begin
        main;
end.

Thuật toán sắp xếp tuần tự

Bài toán đặt ra

Cho mảng A gồm n phần tử. Sắp xếp lại dãy A theo chiều giảm dần

Nhập vào: số nguyên dương n và dãy A.

8
9 7 6 15 16 5 10 11
Xuất ra: dãy A sau khi đã được sắp xếp
5 6 7 9 10 11 15 16

Ý tưởng

Tư duy đơn giản như cách chúng ta xếp bài

sap-xep-1-yeulaptrinhHình trên là thao tác xếp cây bài 7 bằng cách rút nó ra và đặt vào vị trí của phù hợp.

Giải sử bài trên tay đang là:

2 5 7 10 4

ta thấy dãy 2,5,7,10 đã tăng dần chỉ còn cây 4 đứng chưa đúng chỗ nên ta đẩy 4 lên trước 10, rồi lên trước 7 cứ như vậy đến khi gặp cây 2 đứng trước. 2 < 4 suy ra thì dừng. Dãy trở thành

2 4 5 7 10

Dãy đã được sắp xếp.

Ý tưởng: duyệt lần lượt từng cây bài, nếu cây bài nhỏ thì ta đẩy dần lên đầu đến khi nào không chuyển lên được nữa

Ví dụ khác:

sap-xep-yeulaptrinh.pwCode:

#include <bits/stdc++.h>

using namespace std;

int n, a[10000];

void doi_cho(int *x, int *y) {
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

int main() {
    cin >> n;
    for (int i=1; i<=n; i++) cin >> a[i];
    for (int i=1; i<=n; i++)
    {
        for (int j=1; j<i; j++)
            if (a[j] > a[i])
            {
                doi_cho(&a[i], &a[j]);
            }
    }
    for (int i=1; i<=n; i++) cout << a[i] << " ";
    return 0;
}
Ví dụ:

Với dãy A = {12, 11, 13, 5, 6}

Cho i chạy từ 1 đến 4

i=1. không làm gì cả

12, 11, 13, 5, 6

i = 2. Vì 11 nhỏ hơn 12 nên chuyển 11 lên trước 12
11, 12, 13, 5, 6

i = 3. 13 không cần chuyển lên đầu nữa
11, 12, 13, 5, 6

i = 4. 5 được chuyển chỗ với 13 rồi chuyển chố tiếp lần lượt với 12, 11.
5, 11, 12, 13, 6

i = 5. 6 cũng giông như 5 được chuyển dần lên đến khi gặp 5 nhỏ hơn thì dừng lại
5, 6, 11, 12, 13

Độ phức tạp:

  • O(n^2)

 

Quý bạn đọc có ý kiến, thắc mắc xin comment bên dưới <3

QBRECT – spoj

Đề bài:

Thuật toán:

Sau đây là cách tìm hình chữ nhật lớn nhất trong thời gian O(n^2):

Với mỗi ô j trên hàng i, ta tìm f(j) là số ô 1 liên tiếp trên cột j, tính từ hàng i trở lên. Sau đó, với mỗi cột j, ta tiếp tục tìm ô gần nhất bên trái và ô gần nhất bên phải có f nhỏ hơn f(j), sau đó tính diện tích hình chữ nhật ở cột j là S=f(j)×(r−l−1) với l,r là chỉ số 2 ô bên trái và bên phải nói trên.
Hình minh hoạ khi tính f(4):
deque-yeulaptrinh.pw
Để tìm l,r nhanh, ta dùng kĩ thuật sử dụng Deque tìm Min/Max trên đoạn tịnh tiến.

Code:

uses    math;
const   fi='';
        fo='';
        maxn=1000;
var     a:array[1..maxn,1..maxn] of byte;
        i,j,m,n,res,top:longint;
        h,s,left,right:array[1..maxn] of integer;
procedure nhap;
begin
    assign(input,fi);reset(input);
    readln(m,n);
    for i:=1 to m do
        for j:=1 to n do read(a[i,j]);
    close(input);
end;
procedure push(x:integer);
begin
    inc(top);
    s[top]:=x;
end;
function get:integer;
begin
    exit(s[top]);
end;
procedure pop;
begin
    dec(top);
end;
procedure xuly;
begin
    for i:=1 to m do
     begin
        for j:=1 to n do
           if a[i,j]=1 then
                begin
                    h[j]:=h[j]+1;
                end else h[j]:=0;
        top:=0;
        for j:=1 to n do
            begin
                while (top<>0) and (h[j]<=h[get]) do pop;
                if top=0 then left[j]:=0 else left[j]:=get;
                push(j);
            end;
        top:=0;
        for j:=n downto 1 do
                begin
                    while (top<>0) and (h[j]<=h[get]) do pop;
                    if top=0 then right[j]:=n+1 else right[j]:=get;
                    push(j);
                end;
        for j:=1 to n do
                begin
                    res:=max(res,h[j]*(right[j]-left[j]-1));
                end;
     end;
end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    xuly;
    inkq;
end.

[Discrete Mathematics] Sets and Funtions

1. Sets

  • A set is an unordered collection of objects, called elements or members of the set.
  • A set is said to contain its elements
  • $ a \in A $ if a is element of A
  • $ a \notin A $ if a is not element of A
  • Ways to describe set
    • List all the members of a set (Roster method). E.g $ A = \{a, b, c, d\} $ (Roster method)
    • Use set builder notation: $ X = \{ x \mid P(x) \} $$$ E.g \ \ O=\{x \mid x \ is \ odd\} $$
  • A is a subset of B if and only if every element of A is also an element of B.$$ A \subseteq B \Leftrightarrow \forall x (x \in A \rightarrow x \in B) $$
  • Two sets are equal if and only if they have the same elements.$$ A = B \Leftrightarrow \forall x (x \in A \leftrightarrow x \in B) $$$$ A = B \Leftrightarrow A \subseteq B \land B \subseteq A $$
  • The empty set$\emptyset$$$ For \ every \ set \ \emptyset \subseteq S, S \subseteq S $$
  • Given a set $S$, the power set of $S$ is the set of all subsets of the set S. The power set of S is denoted by $\mathcal{P}(S)$

2. Set operations

  • The union of the sets A and B is the set that contains those elements that are either in A or in B, or in both.$$ A \cup B = \{x \mid x \in A \lor x \in B \} $$
  • The intersection of the sets A and B is the set containing those elements in both A and B.$$ A \cap B = \{x \mid x \in A \land x \in B \} $$
  • The difference of A and B is the set containing those elements that are in A but not in B. The difference of A and B is also called the complement of B with respect to A.$$ A \setminus B = \{ x \mid x \in A \land x \notin B \} $$

Table set identies

To be done

3. Cartesian product

  • The ordered n-tuple (a1, a2, . . . , an) is the ordered collection that has a1 as its first element, a2 as its second element, . . . , and an an as its nth element.
  • The Cartesian product of the sets A1, A2, . . . , An, denoted by A1 x A2 x · · · x An, is the set of ordered n-tuples (a1, a2, . . . , an), where ai belongs to Ai for i = 1, 2, . . . , n.$$A_1 × A_2 × · · · × A_n = \{ \ (a_1, a_2, . . . , a_n) \mid a_i ∈ A_i, i = 1, 2, . . . , n \ \} $$

4. Function

  • Let X and Y be nonempty sets. A function f from X to Y is an assignment of exactly one element of X to each element of Y$$ f : X \to Y $$
  • A function f is said to be one-to-one, or an injunction, if and only if f(a) = f (b) implies that a = b for all a and b in the domain of f (Injunctive)$$ \forall a \forall b (a \neq b \rightarrow f(a) \neq f(b)) $$
  • A function f from X to Y is called onto, or a surjection, if and only if for every element y ∈ Y there is an element x ∈ X with f(x) = y (Surjective)$$ \forall y \in Y, \exists x \in X : f(x) = y $$
  • A function f is a one-to-one correspondence, or a bijection, if it is both one-to-one and onto. (Bijective)$$ \forall y \in Y, \exists ! x \in X : f(x) = y $$
  • Let f be a function from the set X to the set Y and let g be a function from the set y to the set C. The composition of the functions g and f, is defined by is defined by (f ◦ g)(a) = f (g(a)).

5. Cardinality of Sets

Definition

The sets A and B have the same cardinality if and only if there is a one-to-one correspondence from A to B. When A and B have the same cardinality, we write |A| = |B|.

To be done

References

  • Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen
  • Đại số tuyến tính, Nguyễn Hữu Việt Hưng

[Discrete Mathematics] Logic and Proof

I. Logic and Proof

 

1. Propositional Logic

A proposition is a declarative sentence (that is, a sentence that declares a fact) that is either true or false, but not both.

Name Meaning Notation
negation not p $\lnot p$
disjunction p or q $p \lor q$
conjunction p and q $p \land q$
conditional if p, then q $p \rightarrow q$
biconditional p if and only if q $p \leftrightarrow q$

2. Propositional Equivalences

A compound proposition that is always true, no matter what the truth values of the propositional variables that occur in it, is called a tautology.

A compound proposition that is always false is called a contradiction.

A compound proposition that is neither a tautology nor a contradiction is called a contingency.

The compound propositions p and q are called logically equivalent if $p \leftrightarrow q $ is a tautology. ($p \equiv q$)

Equivalence Name
$$ p \lor F \equiv p $$

$$ p \land T \equiv p $$

Identity laws
$$ p \lor T \equiv T $$

$$ p \land F \equiv F $$

Domination laws
$$ p \lor p \equiv p $$

$$ p \land p \equiv p $$

Idempotent laws
$$ \lnot(\lnot p)) \equiv p $$ Double negation law
$$ p \lor q \equiv q \lor p $$

$$ p \land q \equiv q \land p $$

Commutative laws
$$ (p \lor q) \lor r \equiv p\lor(q\lor r) $$

$$ (p \land q) \land r \equiv p \land (q \land r) $$

Associative laws
$$ p \lor (q \land r) \equiv (p \lor q) \land (p \lor r) $$

$$ p \land (q \lor r) \equiv (p \land q) \lor (p \land r) $$

Distributive laws
$$ \lnot (p \land q) \equiv \lnot p \lor \lnot q $$

$$ \lnot (p \lor q) \equiv \lnot p \land \lnot q $$

De Morgan’s laws
$$ p \lor (p \land q) \equiv p $$

$$ p \land (p \lor q) \equiv p $$

Absorption laws
$$ p \lor \lnot p \equiv T $$

$$ p \land \lnot p \equiv F $$

Negation laws
Table of common Logical equivalence

3. Predicates and Quantifiers

To be done

References

Discrete Mathematics and Its Applications 7th Edition, Kenneth H. Rosen

Nhập, xuất dữ liệu trong C++

Trong bài này, chúng ta sẽ học cách nhập vào từ bàn phím (stdin standard input device) và ghi ra màn hình (stdout standard output device).

Ta cũng cần dùng đến thư viện iostream namespace std để hỗ trợ nhập xuất. Khi muốn dùng lệnh nào nằm trong namespace std, ta có 2 cách:

  • Khai báo using namespace std ở đầu chương trình, sau đó có thể dùng các lệnh này bình thường.
  • Thêm std:: vào trước lệnh ta muốn dùng. Ví dụ như std::cin, std::endl.

Từ đây trở đi, khi gặp std:: trước một lệnh, chúng ta sẽ tự hiểu lệnh sau đó nằm trong namespace std và có 2 cách như trên để viết.

std::cin

Để nhập dữ liệu cho biến, ta dùng lệnh cin

cin >> biến;

Nếu có nhiều biến cần nhập vào, ta có thể viết liên tiếp như sau

cin >> biến 1 >> biến 2 >> … >> biến n;

Khi chạy đến lệnh cin, chương trình sẽ chờ người dùng nhập dữ liệu vào các biến tương ứng. Dữ liệu nhập vào được phân cách nhau bởi dấu cách hoặc tab hoặc enter, và luôn được hiển thị ra màn hình.

Ví dụ

int a, b;
cin >> a >> b;

Lệnh cin ở dòng 2 sẽ yêu cầu người dùng nhập vào 2 giá trị tương ứng với 2 biến số nguyên a và b.

Lưu ý

Khi nhập vào, các giá trị được phân tách nhau bởi space (dấu cách), tab (dấu tab) hay enter (dấu xuống dòng). Nếu không, mặc dù trong một số trường hợp chương trình vẫn chạy nhưng rất khó kiểm soát được giá trị các biến nhập vào.
Ví dụ: đoạn mã sau

int a,b,c;  
cin>>a>>b>>c;  
hoặc
int a,b,c;
cin>>a; cin>>b; cin>>c;
khi thực hiện, ta nhập dữ liệu từ bàn phím: 3 4 5<enter> hoặc nhập:
3<enter>
4<enter>
5<enter>
Sau khi nhập xong biến a=3, b=4 và c=5.

std::cout

Để in dữ liệu ra màn hình, ta dùng lệnh cout

cout << biểu thức;

Ta cũng có thể in hàng loạt nhiều biểu thức liên tiếp nhau

cout << biểu thức 1 << biểu thức 2 << … << biểu thức n;

Biểu thức ở đây có thể hiểu là biểu thức toán học chứa biến, hằng, hay kết quả trả về của một hàm, …

Ví dụ

int a, b;
cin >> a >> b;
cout << a << ” + ” << b << ” = ” << a + b;

Lệnh cout ở dòng 3 in ra lần lượt: giá trị biến a, chuỗi ” + “, giá trị biến b, chuỗi ” = ” và giá trị biểu thức a + b.

Một số ký tự điều khiển

  • \a’ : tiếng chuông
  • \b’ : lùi lại một bước
  • \n’ : xuống dòng
  • \t’ : dấu tab
  • \\’ : dấu \
  • \?’ : dấu ?
  • \”‘ : dấu “

Lưu ý

std::endl cũng có chức năng tương tự ‘\n’ nhưng ngoài ra endl còn làm rỗng bộ đệm đầu ra.

Ví dụ

cout << ‘\t’ << “Hello World !\n” << 0;

Kết quả:

Hello World!
0

Lưu ý

cin dùng toán tử >> còn cout dùng toán tử <<. Đừng nhầm lẫn!

cout, cin nằm trong thư viện iostream

Định dạng in

Để dùng những lệnh định sau, ngoài thư viện iostream, ta còn phải dùng thư viện iomanip để định dạng. Các định dạng này cần được cout mới có tác dụng.

std::setw(n): quy định khoảng không gian cho dữ liệu được in ra màn hình là n. Nếu dữ liệu chiếm ít không gian hơn, dữ liệu sẽ được căn  lề phải khi in ra. Ngược lại , lệnh này không có ảnh hưởng, tức dữ liệu vẫn in ra như bình thường.

std::setprecision(n): quy định số chữ số được làm tròn khi in ra là n. Số chữ số được tính từ trái qua phải.

std::fixed: lệnh này đi kèm với setprecision sẽ xác định chỉ làm tròn các chữ số ở phần thập phân.

Ví dụ

cout << 12.345 << ‘ ‘;
cout << setprecision(2) << 12.345 << ‘ ‘;
cout << fixed << setprecision(2) << 12.345;

Kết quả:

12.345 12 12.35

Một số hàm khác liên quan đến nhập xuất

std::cin.get(c): nhập 1 ký tự vào biến c.

std::cin.getline(s, n): nhập tối đa n – 1 ký tự vào xâu s (ký tự thứ n là NULL).
std::getline (cin,str): đọc xâu kí tự str, str kiểu dữ liệu string.
std::cin.ignore(n): xóa n ký tự trong bộ đệm đầu vào.

fflush(stdin): xóa toàn bộ bộ đệm đầu vào.

Có thể bạn thích:
Nhập, xuất dữ liệu từ file trong C++

Bài tập mẫu

Viết chương trình nhập vào 3 số a, b, c. In ra trung bình cộng của 3 số đó với giá trị làm tròn đến chữ số thập phân thứ 5.

Code:

#include <iostream>
#include <iomanip>
 
using namespace std;
 
int main()
{
     cout << "Nhap 3 so a, b, c: ";
     float a, b, c;
     cin >> a >> b >> c;
     float avr = (a + b + c) / 3;
     cout << fixed << setprecision(5) << avr << endl;
     system("pause"); // Tạm dừng màn hình chờ nhấn Enter
     return 0;
}

Set trong C++

Tổng quan

  • Set là một loại associative containers để lưu trữ các phần tử không bị trùng lặp (unique elements), và các phần tử này chính là các khóa (keys).
  • Khi duyệt set theo iterator từ begin đến end, các phần tử của set sẽ tăng dần theo phép toán so sánh.
  • Mặc định của set là sử dụng phép toán less, bạn cũng có thể viết lại hàm so sánh theo ý mình.
  • Set được thực hiện giống như cây tìm kiếm nhị phân (Binary search tree).

Khai báo:

#include <set> 
set <int> s;
set <int, greater<int> > s;
Hoặc viết class so sánh theo ý mình:
struct cmp{
bool operator() (int a,int b) {return a<b;}
};
set <int,cmp > myset ;

Capacity:

  • size : trả về kích thước hiện tại của set. ĐPT O(1)
  • empty : true nếu set rỗng, và ngược lại. ĐPT O(1).

Thay đổi:

  • insert : Chèn phần tử vào set. ĐPT O(logN).
  • erase : có 2 kiểu xóa: xóa theo iterator, hoặc là xóa theo khóa. ĐPT O(logN).
  • clear : xóa tất cả set. ĐPT O(n).
  • swap : đổi 2 set cho nhau. ĐPT O(n).

Truy cập phần tử:

  • find : trả về itarator trỏ đến phần tử cần tìm kiếm. Nếu không tìm thấy itarator trỏ về “end” của set. ĐPT O(logN).
  • lower_bound : trả về iterator đến vị trí phần tử bé nhất mà không bé hơn (lớn hơn hoặc bằng) khóa (dĩ nhiên là theo phép so sánh), nếu không tìm thấy trả về vị trí “end” của set. ĐPT O(logN).
  • upper_bound: trả về iterator đến vị trí phần tử bé nhất mà lớn hơn khóa, nếu không tìm thấy trả về vị trí “end” của set.. ĐPT O(logN).
  • count : trả về số lần xuất hiện của khóa trong container. Nhưng trong set, các phần tử chỉ xuất hiện một lần, nên hàm này có ý nghĩa là sẽ return 1 nếu khóa có trong container, và 0 nếu không có. ĐPT O(logN).

 

Chương trình Demo 1:

#include <iostream>
#include <set>
using namespace std; 
main() {
      set <int> s;
      set <int> ::iterator it; s.insert(9);  // s={9}
      s.insert(5);  // s={5,9} cout << *s.begin() << endl; //In ra 5 s.insert(1);  // s={1,5,9} cout << *s.begin() << endl; // In ra 1
 
      it=s.find(5);
      if (it==s.end()) cout << "Khong co trong container" << endl; else  cout << "Co trong container" << endl;

      s.erase(it);  // s={1,9}
      s.erase(1);  // s={9}

      s.insert(3);  // s={3,9}
      s.insert(4);  // s={3,4,9}

      it=s.lower_bound(4);
      if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 4" << endl; else cout << "Phan tu be nhat khong be hon 4 la " << *it << endl;  // In ra 4

      it=s.lower_bound(10);
      if (it==s.end()) cout << "Khong co phan tu nao trong set khong be hon 10" << endl; else cout << "Phan tu be nhat khong be hon 10 la " << *it << endl; // Khong co ptu nao           

      it=s.upper_bound(4);
      if (it==s.end()) cout << "Khong co phan tu nao trong set lon hon 4" << endl; else cout << "Phan tu be nhat lon hon 4 la " << *it << endl;  // In ra 9                

      /* Duyet set */

      for (it=s.begin();it!=s.end();it++) { cout << *it <<  " ";
      }
      // In ra 3 4 9

      cout << endl; system("pause");
}

Lưu ý: Nếu bạn muốn sử dụng hàm lower_bound hay upper_bound để tìm phần tử lớn nhất “bé hơn hoặc bằng” hoặc “bé hơn” bạn có thể thay đổi cách so sánh của set để tìm kiếm. Mời bạn xem chương trình sau để rõ hơn:

#include <iostream>
#include <set>
#include <vector> using namespace std;
main() {
      set <int, greater <int> > s;
      set <int, greater <int> > :: iterator it; // Phép toán so sánh là greater

      s.insert(1);  // s={1}
      s.insert(2);  // s={2,1}
      s.insert(4);  // s={4,2,1}
      s.insert(9);  // s={9,4,2,1}

      /* Tim phần tử lớn nhất bé hơn hoặc bằng 5 */ it=s.lower_bound(5);
      cout << *it << endl;  // In ra 4

      /* Tim phần tử lớn nhất bé hơn 4 */ it=s.upper_bound(4);
      cout << *it << endl;  // In ra 2

      system("pause");
}