Cài đặt SDL cho CodeBlocks

Tải về

  • Tải về: https://www.libsdl.org/projects/SDL_image/release/SDL2_image-devel-2.0.3-mingw.tar.gz
  • Giải nén ra thì thấy có 2 thư mục:
    • Bản 32bit: i686-w64-mingw32
    • Bản 64bit: x86_64-w64-mingw32
  • Ở đây ta dùng bản 32 bit (vì CodeBlock đang dùng mingw32),
  • Trong thư mục này có 4 thư mục bin, include, lib, share
  • Thư mục bin chứa SDL2.dll (liên kết khi chạy, copy file này vào thư mục
    mã nguồn project, cùng folder với main.cpp
    )
  • Thư mục include chứa các file .h (như stdio.h) khai báo các hàm của SDL. Cũng coppy vào thư mục project.
  • Thư mục lib chứa các thư viện (mã đối tượng) để liên kết chương trình. Tương tự như trên, cũng copy vào thư mục project

Cấu hình CodeBlocks

Settings / Compiler / Linker Settings / Other linker… 

Gõ thêm vào: -lmingw32 -lSDL2main -lSDL2

Làm như trên để khi biên dịch chương trình, Codeblocks sẽ biên dịch cả những thứ trong thư viện SDL

Tiếp theo, chọn tab Search directories / Compilers

Thêm vào đường dẫn đến thư mục SDL. Ví dụ: e:\myproject\SDL\

Chuyển sang tab Linker, thêm đường dẫn tới thư mục lib. Ví dụ: e:\myproject\lib

 

Queue (hàng đợi) trong C++

Queue là một loại cấu trúc dữ liệu và một loại container adaptor, được thiết kế để hoạt động theo kiểu FIFO (First – in first – out) (vào trước ra trước), tức là một kiểu danh sách mà việc bổ sung được thực hiển ở cuối danh sách và loại bỏ ở đầu danh sách.

Trong queue, có hai vị trí quan trọng là vị trí đầu danh sách (front), nơi phần tử được lấy ra, và vị trí cuối danh sách (back), nơi phần tử cuối cùng được thêm vào.

Khai báo: #include <queue>

Các hàm thành viên:

  • size : trả về kích thước hiện tại của queue. ĐPT O(1).
  • empty : true nếu queue rỗng, và ngược lại. ĐPT O(1).
  • push : đẩy vào cuối queue. ĐPT O(1).
  • pop: loại bỏ phần tử (ở đầu). ĐPT O(1).
  • front : trả về phần tử ở đầu. ĐPT O(1).
  • back: trả về phần tử ở cuối. ĐPT O(1).

Chương trình demo:

#include <iostream>

#include <queue>

using namespace std;

queue <int> q;

int i;

main() {
  for (i=1;i<=5;i++) q.push(i);
  // q={1,2,3,4,5}
  q.push(100);
  // q={1,2,3,4,5,100}
  cout << q.front() << endl;
  // In ra 1
  q.pop();
  // q={2,3,4,5,100}
  cout << q.back() << endl;
  // In ra 100
  cout << q.empty() << endl;
  // In ra 0
  cout << q.size() << endl;
  // In ra 5
  system("pause");
}

Stack (ngăn xếp) trong C++

Stack là một loại container adaptor, được thiết kế để hoạt động theo kiểu LIFO (Last – in first – out) (vào sau ra trước), tức là một kiểu danh sách mà việc bổ sung và loại bỏ một phần tử được thực hiển ở cuối danh sách. Vị trí cuối cùng của stack gọi là đỉnh (top) của ngăn xếp.

 

Khai báo: #include <stack>

 

Các hàm thành viên:

  • size : trả về kích thước hiện tại của stack. ĐPT O(1).
  • empty : true stack nếu rỗng, và ngược lại. ĐPT O(1).
  • push : đẩy phần tử vào stack. ĐPT O(1).
  • pop : loại bỏ phẩn tử ở đỉnh của stack. ĐPT O(1).
  • top : truy cập tới phần tử ở đỉnh stack. ĐPT O(1).

Chương trình demo:

#include <iostream>

#include <stack>

using namespace std;

stack <int> s;

int i;

main() {

  for (i=1;i<=5;i++) s.push(i); // s={1,2,3,4,5} 
  s.push(100); // s={1,2,3,4,5,100} 
  cout << s.top() << endl; // In ra 100 
  s.pop(); // s={1,2,3,4,5} 
  cout << s.empty() << endl; // In ra 0 
  cout << s.size() << endl; // In ra 5 system("pause");

}

List (danh sách liên kết) trong C++

  • List được thực hiện như danh sách nối kép (doubly-linked list). Mỗi phần tử trong danh sách nối kép có liên kết đến một phần tử trước đó và một phần tử sau nó.
  • Do đó, list có các ưu điểm như sau:
    1. Chèn và loại bỏ phần tử ở bất cứ vị trí nào trong container. O(1).
  • Điểm yếu của list là khả năng truy cập tới phần tử thông qua vị trí. O(n).
  • Khai báo: #include <list>

Các hàm thành viên:

Capacity:

  • size : trả về số lượng phần tử của list. ĐPT O(1).
  • empty : trả về true(1) nếu list rỗng, ngược lại là false(0). ĐPT O(1).

 

Truy cập phần tử:

  • front: trả về giá trị phần tử đầu tiên. ĐPT O(1).
  • back: trả về giá trị phần tử cuối cùng. ĐPT O(1).

 

Chỉnh sửa:

  • push_back : thêm phần tử vào ở cuối list. ĐPT O(1).
  • push_front : thêm phần tử vào đầu list. ĐPT O(1).
  • pop_back : loại bỏ phần tử ở cuối list. ĐPT O(1).
  • pop_front : loại bỏ phần tử ở đầu list. ĐPT O(1).
  • insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể là phần tử hay iterator của 1 đoạn phần tử…). ĐPT là số phần tử thêm vào.
  • erase : xóa phần tử ở vị trí iterator. ĐPT là số phần tử bị xóa đi.
  • swap : đổi 2 list cho nhau (ví dụ: first.swap(second);). ĐPT O(1).
  • clear: xóa list. ĐPT O(n).

 

Operations:

  • splice : di chuyển phần tử từ list này sang list khác. ĐPT O(n).
  • remove (const) : loại bỏ tất cả phần tử trong list bằng const. ĐPT O(n).
  • remove_if (function) : loại bỏ tất các phần tử trong list nếu hàm function return true . ĐPT O(n).
  • unique : loại bỏ các phần tử bị trùng lặp hoặc thỏa mãn hàm nào đó. ĐPT O(n). Lưu ý: Các phần tử trong list phải được sắp xếp.
  • sort : sắp xếp các phần tử của list. O(NlogN)
  • reverse : đảo ngược lại các phần tử của list. O(n).

Deque (hàng đợi hai đầu) trong C++

Deque hay còn được gọi là hàng đợi hai đầu

  • Deque (thuờng được phát âm giống như “deck”) là từ viết tắt của double-ended queue (hàng đợi hai đầu).
  • Deque có các ưu điểm như:
  1. Các phần tử có thể truy cập thông cua chỉ số vị trí của nó. O(1)
  2. Chèn hoặc xóa phần tử ở cuối hoặc đầu của dãy. O(1)

Khai báo: #include <deque>

 

Capacity:

  • size : trả về số lượng phần tử của deque. ĐPT O(1).
  • empty : trả về true(1) nếu deque rỗng, ngược lại là false(0). ĐPT O(1).

Truy cập phần tử:

  • operator [] : trả về giá trị phần tử thứ []. ĐPT O(1).
  • at : tương tự như trên. ĐPT O(1).
  • front: trả về giá trị phần tử đầu tiên. ĐPT O(1).
  • back: trả về giá trị phần tử cuối cùng. ĐPT O(1).

 

Chỉnh sửa:

  • push_back : thêm phần tử vào ở cuối deque. ĐPT O(1).
  • push_front : thêm phần tử vào đầu deque. ĐPT O(1).
  • pop_back : loại bỏ phần tử ở cuối deque. ĐPT O(1).
  • pop_front : loại bỏ phần tử ở đầu deque. ĐPT O(1).
  • insert (iterator,x): chèn “x” vào trước vị trí “iterator” ( x có thể là phần tử hay iterator của 1 đoạn phần tử…). ĐPT O(n).
  • erase : xóa phần tử ở vị trí iterator. ĐPT O(n).
  • swap : đổi 2 deque cho nhau (ví dụ: first.swap(second);). ĐPT O(n). clear: xóa vector. ĐPT O(1).

C11PAIRS – spoj

Đề bài

Thuật toán

-Đầu tiên ta khởi tạo một stack để lưu chiều cao của các bạn theo thứ tự không tăng (s[i]<=s[i-1])

-Đầu tiên ta cho a[n] vào stack, khởi tạo ds=0,sn=1(sn là số phần tử trong ngăn xếp);

-Duyệt i từ n-1 về 1, với mỗi i:

+Tìm vị trí cuối cùng trong stacks mà s[i]>a[i], giả sử ta gọi là vt.

+Nếu vt=0 nghĩa là người đứng ở vị trí i có thể nhìn thấy mọi người trong stack vì vậy ds+=sn;

+Nếu vt!=0 nghĩa là người đứng ở vị trí i có thể nhìn thấy từ người thứ vt đến người thứ sn trong stack vì vậy ds+=(sn-vt+1);

+Tiếp theo ta sẽ bỏ các s[i]<a[i] trong stack sau đó thêm a[i] vào stack.

-Kết quả của bài này chính là ds.

-Từ đó ta thu được thuật toán với đpt O(n*log(n)), mặc dù có thể giảm đpt xuống còn O(n) nhưng mình thấy thuật toán này khá đơn giản và dễ code, có thể là ngắn hơn. Đây là code của mình:

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 = 1E6+3;
const int oo = 1e9+3;
 
int n, i, j, a[MAXN], c[MAXN], s[MAXN], top, tmp;
ll ans;
 
int main() {
        ios_base::sync_with_stdio(0); cin.tie(0);
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif //yeulaptrinh.pw
    cin >> n;
    FOR(i,1,n) cin >> a[i];
 
    top = 0;
    FOR(i,1,n) {
        tmp = 1;
        while (top&&s[top]<=a[i]) {
            ans += c[top];
            if (s[top]==a[i]) tmp += c[top];
            c[top] = 0; top--;
        }
        if (top) ans++;
        // push
        top++;
        s[top] = a[i];
        c[top] = tmp;
    }
    cout << ans;
	return 0;
}

NKINV – spoj

Đề bài

Thuật toán

  • Interval Tree

Code

uses    math;
const   fi='';
        fo='';
        maxn = 60000+3;
var     t       :array[1..maxn*4] of longint;
        i,j,n   :longint;
        a       :ARRAY[1..maxn] of longint;
        ma      :longint;
        res     :int64;
procedure enter;
begin
        assign(input,fi);reset(input);
        readln(n);for i:=1 to n do read(a[i]);
        close(input);
end;
procedure update(k,l,r,i:longint);
var     m :longint;
begin
        if (i<l) or (i>r) then exit;
        if l=r then
                begin
                        inc(t[k]);
                        exit;
                end;
        m := (l+r) div 2;
        update(k*2,l,m,i);
        update(k*2+1,m+1,r,i);
        t[k] := t[k*2] + t[k*2+1];
end;
function get(k,l,r,i,j:longint):longint;
var     m,tam1,tam2     :longint;
begin
        if i>j then exit(0);
        if (i>r) or (j<l) then exit(0);
        if (i<=l) and (j>=r) then
                begin
                        exit(t[k]);
                end;
        m := (l+r) div 2;
        tam1 := get(k*2,l,m,i,j);
        tam2 := get(k*2+1,m+1,r,i,j);
        get:= tam1+tam2;
end;
procedure process;
var     i :longint;
begin
        for i:=1 to n do ma := max(ma,a[i]);
        res := 0;
        for i:=1 to n do
                begin
                        res := res + get(1,1,ma,a[i]+1,ma);
                        update(1,1,ma,a[i]);
                end;
end;
procedure print;
begin
        assign(output,fo);rewrite(output);
        writeln(res);
        close(output);
end;
begin
        enter;
        process;
        print;
end.