Vector trong C++

August 11, 2017 by Leave a Comment

Khai báo vector:

Vector có thể hiểu là một mảng có trình tự, giống như với danh sách liên kết hay một chuỗi thông thường nhưng “vector” khác với chuỗi hoăc mảng thông thường là chúng ta có thể thay đổi kích thước của nó và cũng có thể truy cập trực tiếp đến các phần tử, điều này làm cho việc sử dụng “vector” linh hoạt hơn so với “list”…

#include 
...
/* Vector 1 chiều */

/* tạo vector rỗng kiểu dữ liệu int */ vector  first;

//tạo vector với 4 phần tử là 100 vector  second (4,100);

// lấy từ đầu đến cuối vector second
vector  third (second.begin(),second.end())

//copy từ vector third vector  four (third)

/*Vector 2 chiều*/

/* Tạo vector 2 chiều rỗng */ vector < vector  > v;

/* khai báo vector 5×10 */
vector < vector  > v (5, 10) ;

/* khai báo 5 vector 1 chiều rỗng	*/ vector < vector  > v (5) ;

//khai báo vector 5*10 với các phần tử khởi tạo giá trị là 1 vector < vector  > v (5, vector  (10,1) ) ;

Các bạn chú ý 2 dấu “ngoặc” không được viết liền nhau. Ví dụ như sau là sai:

/*Khai báo vector 2 chiều SAI*/
vector > v;

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

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

 

Truy cập tới 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 vào ở cuối vector. ĐPT O(1).
  • pop_back : loại bỏ phần tử ở cuối vector. Đ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 vector cho nhau (ví dụ: first.swap(second);). ĐPT O(1).
  • clear: xóa vector. ĐPT O(n).

 

Nhận xét:

  • Sử dụng vector sẽ tốt khi:
    • Truy cập đến phần tử riêng lẻ thông qua vị trí của nó O(1)
    • Chèn hay xóa ở vị trí cuối cùng O(1).
  • Vector làm việc giống như một “mảng động”.

 

Một vài ví dụ:

Ví dụ 1: Ví dụ này chủ yếu để làm quen sử dụng các hàm chứ không có đề bài cụ thể.

#include 
#include 
using namespace std;
vector  v; //Khai báo vector
vector ::iterator it;	//Khai báo iterator
vector ::reverse_iterator rit; //Khai báo iterator ngược int i;
main() {
      for (i=1;i<=5;i++) v.push_back(i); // v={1,2,3,4,5} cout << v.front() << endl;	// In ra 1
      cout << v.back() << endl;	// In ra 5

      cout << v.size() << endl;	// In ra 5

      v.push_back(9);	// v={1,2,3,4,5,9}
      cout << v.size() << endl;	// In ra 6

      v.clear();	// v={}
      cout << v.empty() << endl;	// In ra 1 (vector rỗng)

      for (i=1;i<=5;i++) v.push_back(i); // v={1,2,3,4,5} v.pop_back();	// v={1,2,3,4}
      cout << v.size() << endl;	// In ra 4

      v.erase(v.begin()+1);	// Xóa ptử thứ 1 v={1,3,4} v.erase(v.begin(),v.begin()+2);	// v={4}
      v.insert(v.begin(),100);	// v={100,4}
      v.insert(v.end(),5);	// v={100,4,5}

      /*Duyệt theo chỉ số phần tử*/
      for (i=0;i

Ví dụ 2: Cho đồ thị vô hướng G có n đỉnh (các đỉnh đánh số từ 1 đến n) và m cạnh và không có khuyên (đường đi từ 1 đỉnh tới chính đỉnh đó).


Cài đặt đồ thị bằng danh sách kề và in ra các cạnh kề đối với mỗi cạnh của đồ thị. Dữ liệu vào:


    

  • Dòng đầu chứa n và m cách nhau bởi dấu cách
    • 

  • M dòng sau, mỗi dòng chứa u và v cho biết có đường đi từ u tới Không có cặp đỉnh u,v nào chỉ cùng 1 đường đi.
    • 



Dữ liệu ra:


    

  • M dòng: Dòng thứ i chứa các đỉnh kề cạnh i theo thứ tự tăng dần và cách nhau bởi dấu cách.
    • 



Giới hạn: 1 <= n,m <= 10000 Ví dụ:






INPUT
OUTPUT




6 7
2 3 5 6




1 2
1 3 6




1 3
1 2 5




1 5
 




2 3
1 3




2 6
1 2




3 5
 




6 1
 






 


Chương trình mẫu:


#include 
#include  using namespace std;
vector < vector  > a (10001);

//Khai báo vector 2 chiều với 10001 vector 1 chiều rỗng int m,n,i,j,u,v;
main() {
      /*Input data*/ cin >> n >> m;
      for (i=1;i<=m;i++) { cin >> u >> v; a[u].push_back(v);
      a[v].push_back(u);
      }
      /*Sort cạnh kề*/ for (i=1;i<=m;i++)
      sort(a[i].begin(),a[i].end());
      /*Print Result*/
      for (i=1;i<=m;i++) {
      for (j=0;j
Chủ đề: C++, Ngôn ngữ lập trình

Một số kỹ thuật tối ưu hóa thuật toán quy hoạch động

August 10, 2017 by Leave a Comment

 

LỜI NÓI ĐẦU

 

Quy hoạch động (QHĐ) là một lớp thuật toán rất quan trọng và có nhiều ứng dụng trong ngành khoa học máy tính. Trong các cuộc thi Olympic tin học hiện đại, QHĐ luôn là một trong những chủ đề chính. Tuy vậy, theo tôi thấy, tài liệu nâng cao về QHĐ bằng tiếng Việt hiện còn cực kỳ khan hiếm, dẫn đến học sinh/sinh viên Việt Nam bị hạn chế khả năng tiếp cận với những kỹ thuật hiện đại. Trong bài viết này, tôi sẽ trình bày một vài kỹ thuật để tối ưu hóa độ phức tạp của một số thuật toán QHĐ.

 

Lê Anh Đức A2K42-PBC

  1. Đổi biến

Nhiều khi trong trạng thái QHĐ có một thành phần nào đấy với khoảng giá trị quá lớn, trong khi kết quả của hàm lại có khoảng giá trị nhỏ. Trong một vài trường hợp, ta có thể đảo nhãn để giảm số trạng thái.

 

Bài tập ví dụ

 

Longest Common Subsequence (bài toán cổ điển LCS)

(bộ test đi kèm)

 

Cho xâu A độ dài m, xâu B độ dài n. Hãy tìm độ dài xâu con chung dài nhất của hai xâu, chú ý là xâu con chung có thể không liên tiếp.

 

Giới hạn:

 

  • m <= 1 000 000
  • n <= 5 000
  • Các kí tự trong cả hai xâu là các chữ cái tiếng Anh in hoa ‘A’..’Z’

 

Input:

 

  • Dòng thứ nhất chứa xâu A
  • Dòng thứ hai chứa xâu B

 

Output:

 

  • Dòng duy nhất chứa kết quả

 

 

Ví dụ:

Input Output
ADBCC

ABCD

 3

 

Lời giải

Thuật toán đơn giản

Gọi F(i, j) là LCS của hai tiền tố A[1..i] và B[1..j].

Khi đó ta có thể maximize F(i, j) theo F(i-1, j) và F(i, j-1).

Nếu A[i] = B[j] thì ta có thể cập nhật F(i, j) theo F(i-1, j-1) + 1.

Kết quả bài toán là F(m, n).

Độ phức tạp của thuật toán này là O(m*n), không khả thi với giới hạn của đề bài.

 

Đổi biến

Đặt L = min(m, n);

Để ý rằng trong hàm QHĐ trên, các giá trị của F(i, j) sẽ không vượt quá L, trong khi đó chiều thứ hai của trạng thái có thể khá lớn (lên tới MAXM = 1 000 000).

Để tối ưu hóa, ta sẽ đổi biến. Gọi dp(i, j) là vị trí k nhỏ nhất sao cho LCS(A[1..i], B[1..k]) = j.

Để tính các giá trị của dp(), ta sẽ QHĐ theo kiểu cập nhật đi, thay vì đi tìm công thức trực tiếp cho các dp(i, j).

Gọi nextPos(i, c) = j > i nhỏ nhất mà a[j] = c (với c là một ký tự từ ‘A’ đến ‘Z’).

Mảng nextPos[][] có thể tính trong O(M*26).

Như vậy ta có thể tính các giá trị QHĐ như sau:

 

  • Ban đầu khởi tạo các giá trị dp(i, j) = vô cùng, dp(0, 0) = 0.
  • For i và j tăng dần, với mỗi giá trị dp(i, j) khác vô cùng:

 

    • Cập nhật dp(i+1, j) theo dp(i, j).
    • Gọi k là vị trí xuất hiện tiếp theo của b[i+1] trong xâu A bắt đầu từ vị trí dp(i, j), tức là k = nextPos(dp(i, j), b[i+1]).
    • Nếu tồn tại k, cập nhật dp(i+1, j+1) theo k.

Để tính kết quả, ta sẽ chỉ cần tìm j lớn nhất mà tồn tại dp(i, j) khác vô cùng.

 

#include <bits/stdc++.h>

 

using namespace std;

 

const int M = 1e6 + 6;

const int N = 5005;

 

int dp[N][N];

 

char a[M], b[N];

int nextPos[M][26];

int m, n;

 

void minimize(int &a, int b) {

if (a == -1 || a > b) a = b;

}

 

int main() {

cin >> a + 1 >> b + 1;

m = strlen(a + 1); n = strlen(b + 1);

for (int c = 0; c < 26; ++c)

for (int i = m – 1; i >= 0; –i)

nextPos[i][c] = (a[i + 1] – ‘A’ == c) ? i + 1 :                 nextPos[i + 1][c];

int maxLength = min(m, n);

memset(dp, -1, sizeof dp);

dp[0][0] = 0;

for (int i = 0; i < n; ++i) {

for (int j = 0; j <= i; ++j) if (dp[i][j] >= 0) {

minimize(dp[i + 1][j], dp[i][j]);

int new_value = nextPos[dp[i][j]][b[i + 1] – ‘A’];

if (new_value > 0)

minimize(dp[i + 1][j + 1], new_value);

}

}

int ans = 0;

for (int j = maxLength; j > 0; –j) {

for (int i = j; i <= n; ++i)

if (dp[i][j] >= 0) ans = j;

if (ans != 0) break;

}

cout << ans << endl;

return 0;

}

 

Bài tập ví dụ

COMPUTER (VNOI Marathon 2010)

Submit: vn.spoj.com/problems/COMPUTER/

 

Công ty phần mềm XYZ mới mua x máy tính để bàn và y máy tính xách tay. Giá một máy tính để bàn là a đồng còn giá một máy tính xách tay là b đồng. Để tránh sự thắc mắc giữa các phòng bàn, Tổng giám đốc đã đưa ra cách phân bố các máy tính này về n phòng ban như sau:

 

  • Sắp xếp n phòng ban theo thứ tự về mức độ quan trọng của các phòng ban.
  • Tiến hành phân bố các máy tính cho các phòng ban bảo đẩm nếu phòng ban i có mức độ quan trọng nhỏ hơn mức độ quan trọng của phòng ban j thì tổng giá trị máy tính được phân bố cho phòng ban i không được vượt quá tổng giá trị máy tính được phân bố cho phòng ban j.
  • Phòng ban nhận được tổng giá trị máy tính nhỏ nhất là lớn nhất.

 

Là một lập trình viên giỏi nhưng lại thuộc phòng ban có mức độ quan trọng nhỏ nhất, Thắng muốn chứng tỏ tay nghề của mình với đồng nghiệp nên đã lập trình tính ra ngay được tổng giá trị máy trình mà phòng ban mình nhận được rồi mời bạn tính lại thử xem!

 

Yêu cầu:

Cho x, a, y, b, n. Hãy tính tổng giá trị máy tính mà phòng Thắng nhận được.

 

Input:

Gồm hai bộ dữ liệu, mỗi bộ trên một dòng, mỗi dòng chứa 5 số nguyên dương x, a, y, b, n (các số có giá trị không vượt quá 1000).

Output:

Gồm hai dòng, mỗi dòng là đáp án tương ứng với bộ dữ liệu vào.

 

Ví dụ:

Input Output
3 300 2 500 2

4 300 3 500 2

 900

1300

 

Lời giải

Trước hết ta sẽ chặt nhị phân kết quả bài toán. Với mỗi giá trị chặt nhị phân, ta cần kiểm tra xem có tồn tại phương án thỏa mãn hay không.

 

Thuật toán sơ khai

Đặt giá trị cần kiểm tra là v.

Xét các phòng ban theo thứ tự tăng dần về mức độ quan trọng, đánh số từ 1.

Sử dụng một mảng đa chiều để đánh dấu các trạng thái có thể đạt tới. Các giá trị cần quản lí là: chỉ số của phòng ban, đã dùng số máy tính để bàn x, đã dùng số máy tính xách tay y, tổng giá trị máy tính của phòng ban trước đó.

Bắt đầu từ trạng thái (0, 0, 0, 0), ta sử dụng thuật toán loang (BFS). Cuối cùng nếu trạng thái (n, 0, 0, …) có thể đến được, thì ta sẽ có cách phân hoạch các máy tính vào các phòng ban ứng với giá trị cận dưới v.

Không cần tính toán cụ thể cũng có thể thấy thuật toán này không thể đáp ứng về mặt thời gian (và bộ nhớ) với giới hạn của đề bài.

 

Nâng cấp bằng nhận xét

Nhận xét rằng ta không cần quan tâm tới thứ tự về mức độ quan trọng của các phòng ban. Với một cách phân hoạch các máy tính sao cho mỗi phòng nhận được tổng giá trị không nhỏ hơn v, ta luôn có thể sắp xếp các bộ theo giá trị không giảm ứng với các phòng ban.

Ta có trạng thái QHĐ là F(i, x, y, value) = true nếu có thể phân bổ máy tính cho i phòng ban, đã dùng x máy tính để bàn và y máy tính xách tay, đã gom được tổng giá trị v cho phòng thứ i+1. Cách làm này số trạng thái vẫn như trước nhưng ta đã có thể chuyển trạng thái trong O(1). Cụ thể từ F(i, x, y, value) ta chuyển đến F(i, x+1, y, value+a) hoặc F(i, x, y+1, value+b), chú ý là chỉ có thể dùng thêm máy xách tay nếu x<X và dùng thêm máy để bàn nếu y<Y, đồng thời nếu giá trị value đủ lớn hơn hoặc bằng v thì ta chuyển sang trạng thái F(i+1, x, y, 0) luôn.

 

Đổi biến

Ở bài này, ta có thể dễ dàng đổi biến value ra làm hàm mục tiêu. Nhưng không chỉ có vậy, ta có thể đẩy cả i ra ngoài! Cụ thể, F(x, y) = một cặp số (i, value) lần lượt là số phòng phân bố được và số tiền gom được. Hàm mục tiêu của F(x, y) là một cặp số hoàn toàn có thể so sánh được, trong đó giá trị đầu (i) được ưu tiên so sánh trước.

Cách cập nhật các F(x, y) giống như phần trước, độ phức tạp vẫn là O(1) cho bước chuyển trạng thái, trong khi số trạng thái lúc này là đủ nhỏ đối với giới hạn của đề bài.

 

#include <bits/stdc++.h>

 

using namespace std;

 

const int N = 1010;

 

int x, y, a, b, n;

 

pair<int, int> F[N][N];

 

pair<int, int> newState(pair<int, int> s, int a, int v) {

s.second += a;

if (s.second >= v) {

++s.first;

s.second = 0;

}

return s;

}

 

bool dp(int value) {

for (int i = 0; i <= x; ++i) for (int j = 0; j <= y; ++j)

F[i][j] = make_pair(0, 0);

for (int i = 0; i <= x; ++i) for (int j = 0; j <= y; ++j) {

if (F[i][j].first == n) return 1;

if (i < x)

F[i + 1][j] = max(F[i + 1][j], newState(F[i][j], a, value));

if (j < y)

F[i][j + 1] = max(F[i][j + 1], newState(F[i][j], b, value));

}

return 0;

}

 

int solve() {

int l = 0, r = (a * x + b * y) / n;

int ans = 0;

while (l <= r) {

int mid = l + r >> 1;

if (dp(mid)) {

ans = mid;

l = mid + 1;

} else {

r = mid – 1;

}

}

return ans;

}

 

int main() {

cin >> x >> a >> y >> b >> n;

cout << solve() << endl;

cin >> x >> a >> y >> b >> n;

cout << solve() << endl;

return 0;

}

 

Bài luyện tập: http://vn.spoj.com/problems/BINPACK/

 

2. Chia để trị

Đây là kỹ thuật khá hiếm gặp, tuy nhiên lại cực kỳ mạnh.

 

Bài tập ví dụ

Hai nhà máy (CEOI 2004)

 

Có n cây cổ thụ được trồng trên một con đường từ đỉnh đổi đến chân đồi. Chính phủ địa phương quyết định cắt bỏ chúng. Để tránh hoang phí, mỗi cái cây cần được chuyển đến một nhà máy cưa.

 

Cây chỉ có thể được vận chuyển theo một chiều duy nhất: hướng về chân đồi. Có một nhà máy cưa ở cuối con đường. Hai nhà máy cưa có thể được xây dựng dọc theo con đường. Hãy xác định vị trí tối ưu để xây dựng chúng, để cực tiểu hóa chi phí vận chuyển. Chi phí vận chuyển 1kg gỗ đi 1 mét là 1 cent.

 

Yêu cầu

Viết chương trình:

 

  • đọc dữ liệu từ đầu vào chuẩn số lượng cây, khối lượng và vị trí của chúng,
  • tính toán chi phí vận chuyển tối ưu nhất,
  • xuất kết quả ra đầu ra chuẩn.

 

Input

Dòng đầu tiên chứa số n – số lượng cây (2 <= n <= 20000). Các cây được đánh số 1, 2, …, n, theo chiều từ đỉnh đồi đến chân đồi.

n dòng tiếp theo mỗi dòng chứa hai số nguyên dương cách nhau bởi dấu cách. Dòng thứ i + 1 chứa w(i) – khối lượng tính theo kg của cái cây thử i và d(i) – khoảng cách tính theo mét giữa cây thứ i và cây i + 1, 1 <= w(i) <= 10000, 0 <= d(i) <= 10000. Số cuối cùng, d(n) là khoảng cách từ cây thứ n đến chân đồi.

Dữ liệu vào đảm bảo kết quả của bài toán không vượt quá 2 000 000 000 cent.

 

Output

Một dòng duy nhất chứa một số là kết quả bài toán: chi phí vận chuyển nhỏ nhất.

 

Ví dụ

Input Output
9

1 2

2 1

3 3

1 1

3 2

1 6

2 1

1 2

1 1

 26

Hình vẽ trên minh họa cho test ví dụ. Các hình tròn được tô đen là các vị trí có nhà máy. Kết quả sẽ là:
1 * (2+1) + 2 * 1 + 1 * (1 + 2) + 3 * 2 + 2 * (1 + 2 + 1) + 1 * (2 + 1) + 1 * 1 = 26.

Lời giải

 

Trước hết ta sẽ giải quyết vấn đề tính chi phí vận chuyển nếu biết vị trí của hai nhà máy đặt thêm.

Nếu ta có thể tính được chi phí này trong O(1), bài toán sẽ có thể giải được trong O(N^2) – ta có thể for hết các cặp vị trí có thể đặt nhà máy.

Gọi:

 

  • sumW(i) = tổng của các w(j) với i <= j.
  • sumD(i) = tổng của các d(j) với i <= j.
  • sumWS(i) = tổng của các w(j) * sumD(j) với i <= j.

 

Khi đó cost(L, R) = chi phí vận chuyển các cây có chỉ số trong đoạn [L..R] đến nhà máy đặt ở R là: sumWS(L) – sumWS(R) – sumD(R) * (sumW(L) – sumW(R)).

Như vậy ta có thể xây dựng hàm eval(i, j) = chi phí nếu đặt thêm hai nhà máy ở i và j = cost(1, i) + cost(i + 1, j) + cost(j + 1, n + 1).

 

Tuy nhiên lời giải O(N^2) là chưa đủ tốt để có thể giải quyết trọn vẹn bài toán này.

Gọi best(i) = vị trí j > i tốt nhất nếu ta đã đặt một nhà máy ở i.

Như vậy kết quả của bài toán sẽ là min(eval(i, best(i)) với 1 <= i < n.

Nhận xét:

 

  • best(i) <= best(i + 1).
  • Ta có thể tính các best(i) theo thứ tự bất kỳ.

 

Như vậy ta có thuật toán sử dụng tư tưởng chia để trị như sau:

Hàm solve(L, R, from, to) sẽ đi tính các best(L..R), biết rằng chúng nằm trong đoạn [from..to].

 

void solve(int L, int R, int from, int to) {

if (L > R) return;

int mid = L + R >> 1;

best[mid] = from;

for (int i = from + 1; i <= to; ++i)

if (eval(mid + 1, best[mid]) > eval(mid + 1, i))

best[mid] = i;

solve(L, mid – 1, from, best[mid]);

solve(mid + 1, R, best[mid], to);

}

Đánh giá độ phức tạp thuật toán: vì mỗi lần gọi để quy khoảng L..R được chia đôi, nên sẽ có O(logN) tầng, mỗi tầng vòng for chỉ chạy qua O(N) phần tử, vì vậy độ phức tạp của thuật toán là O(NlogN).

 

Bài tập ví dụ

SEQPART

Submit: hackerrank.com

 

Cho dãy L số C[1..L], cần chia dãy này thành G đoạn liên tiếp. Với phần tử thứ i, ta định nghĩa chi phí của nó là tích của C[i] và số lượng số nằm cùng đoạn liên tiếp với nó. Chi phí của dãy số ứng với một cách phân hoạch là tổng các chi phí của các phần tử.

Hãy xác định cách phân hoạch dãy số để chi phí là nhỏ nhất.

 

Input:

 

  • Dòng đầu tiên chứa 2 số L và G.
  • L dòng tiếp theo, chứa giá trị của dãy C.

 

Output:

 

  • Một dòng duy nhất chứa chi phí nhỏ nhất.

 

Giới hạn:

 

  • 1 <= L <= 8000
  • 1 <= G <= 800
  • 1 <= C[i] <= 1 000 000 000

 

Ví dụ:

Input Output
6 3

11

11

11

24

26

100

 299

 

Giải thích: cách tối ưu là C[] = (11, 11, 11), (24, 26), (100). Chi phí là 11 * 3 + 11 * 3 + 11 * 3 + 24 * 2 + 26 * 2 + 100 * 1 = 299.

 

Lời giải

Đây là dạng bài toán phân hoạch dãy số có thể dễ dàng giải bài QHĐ. Gọi F(g, i) là chi phí nhỏ nhất nếu ta phân hoạch i phần tử đầu tiên thành g nhóm, khi đó kết quả bài toán sẽ là F(G, L).

Để tìm công thức truy hồi cho hàm F(g, i), ta sẽ quan tâm đến nhóm cuối cùng. Coi phần tử 0 là phần tử cầm canh ở trước phần tử thứ nhất, thì người cuối cùng không thuộc nhóm cuối có chỉ số trong đoạn [0..i]. Giả sử đó là người với chỉ số k, thì chi phí của cách phân hoạch sẽ là F(g-1, k) + Cost(k+1, i), với Cost(i, j) là chi phí nếu phân j-i+1 người có chỉ số [i..j] vào một nhóm. Như vậy:

F(g, i) = min[F(g-1, k) + Cost(k+1, l)] với 0 <= k <= i.

Chú ý là công thức này chỉ được áp dụng với g>1, nếu g=1, F(1, i) = Cost(1, i), đây là trường hợp cơ sở.

Việc cài đặt chỉ đơn giản là dựng mảng 2 chiều F[][], code như sau:

 

#include <iostream>

 

using namespace std;

 

const int MAXL = 8008;

const int MAXG = 808;

const long long INF = (long long)1e18;

 

long long C[MAXL];

long long sum[MAXL];

long long F[MAXG][MAXL];

 

long long cost(int i, int j) {

return (sum[j] – sum[i – 1]) * (j – i + 1);

}

 

int main() {

int G, L;

cin >> L >> G;

for (int i = 1; i <= L; ++i) {

cin >> C[i];

sum[i] = sum[i – 1] + C[i];

}

 

for (int g = 1; g <= G; ++g) {

for (int i = 0; i <= L; ++i) {

if (g == 1) {

F[g][i] = cost(1, i);

} else {

F[g][i] = INF;

for (int k = 0; k <= i; ++k) {

long long new_cost = F[g – 1][k] + cost(k + 1, i);

if (F[g][i] > new_cost) F[g][i] = new_cost;

}

}

}

}

cout << F[G][L] << endl;

return 0;

}

Chú ý là ta sử dụng mảng sum[] tiền xử lí O(L) để có thể truy vấn tổng một đoạn (dùng ở hàm cost()) trong O(1). Như vậy độ phức tạp của thuật toán này là O(G*L*L).

 

Thuật toán tối ưu hơn

Gọi P(g, i) là k nhỏ nhất để cực tiể hóa F(g, i), nói cách khác, P(g, i) là k nhỏ nhất mà F(g, i) = F(g-1, k) + Cost(k+1, i).

Tính chất quan trọng để có thể tối ưu thuật toán trên là dựa vào tính đơn điệu của P(g, i), cụ thể:

P(g, 0) <= P(g, 1) <= P(g, 2) <= … <= P(g, L-1) <= P(g, L)

Ta sẽ không chứng minh điều này ở đây, độc giả có thể tự thuyết phục rằng điều này là đúng.

 

Chia để trị

Để ý rằng để tính F(g, i), ta chỉ cần quan tâm tới hàng trước <F(g-1)> của ma trận:

F(g-1, 0), F(g-1, 1), … , F(g-1, L). Như vậy, ta có thể tính hàng F(g) theo thứ tự bất kỳ.

Ý tưởng là với hàng g, trước hết ta tính F(g, mid) và P(g, mid) với mid=L/2, sau đó sử dụng tính chất nêu trên P(g, i) <= P(g, mid) với i < mid và P(g, i) >= P(g, mid) với i > mid để đi gọi đệ quy đi tính hai nửa còn lại.

 

#include <iostream>

 

const int MAXL = 8008;

const int MAXG = 808;

const long long INF = (long long)1e18;

 

using namespace std;

 

long long F[MAXG][MAXL], sum[MAXL], C[MAXL];

int P[MAXG][MAXL];

 

long long cost(int i, int j) {

if (i > j) return 0;

return (sum[j] – sum[i – 1]) * (j – i + 1);

}

 

void solve(int g, int L, int R, int optL, int optR) {

if (L > R) return;

int mid = (L + R) / 2;

F[g][mid] = INF;

for (int i = optL; i <= optR; ++i) {

long long new_cost = F[g – 1][i] + cost(i + 1, mid);

if (F[g][mid] > new_cost) {

F[g][mid] = new_cost;

P[g][mid] = i;

}

}

solve(g, L, mid – 1, optL, P[g][mid]);

solve(g, mid + 1, R, P[g][mid], optR);

}

 

int main() {

int G, L;

cin >> L >> G;

for (int i = 1; i <= L; ++i) {

cin >> C[i];

sum[i] = sum[i – 1] + C[i];

}

for (int i = 1; i <= L; ++i) F[1][i] = cost(1, i);

for (int g = 2; g <= G; ++g) solve(g, 1, L, 1, L);

cout << F[G][L] << endl;

return 0;

}

Chú ý rằng ta không thể đảm bảo rằng P[g][mid] chia đôi đoạn [optL..optR], thực tế một vài hàm solve() sẽ chạy chậm hơn nhiều hàm solve() khác.

Tuy nhiên ta có thể chứng minh được, xét về tổng thế thuật toán này chạy đủ nhanh. Mỗi lần ta chia đôi đoạn [L..R], nên ta sẽ đảm bảo có tối đa O(log(L)) tầng đệ quy, như vậy với mỗi hàng g, ta chỉ mất O(L logL) để tính. Toàn bộ thuật toán có độ phức tạp là O(GLlogL).

 

Bài luyện tập: https://www.hackerrank.com/contests/world-codesprint-5/challenges/mining

 

Chủ đề: Phương pháp, Quy hoạch động

Toán tử trong C++

August 10, 2017 by Leave a Comment

Trong bài ta sẽ cùng tìm hiểu các vấn đề:

  • Toán tử quan hệ trong C++
  • Toán tử logic trong C++
  • Toán tử trên bit trong C++
  • Các toán tử hỗn hợp trong C++
  • Độ ưu tiên toán tử trong C++

Toán tử quan hệ trong C++ (Relational operators)

Toán tử quan hệ dùng để so sánh 2 toán hạng với nhau. Sẽ trả về 2 giá trị là 1 (true) hoặc 0 (false).

Bảng bên dưới mô tả các toán tử quan hệ trong C++, giả sử x = 6, y = 9:

Operator Symbol Form Operation Example
Greater than > x > y true if x is greater than y, false otherwise (x > y) is false
Less than < x < y true if x is less than y, false otherwise (x < y) is true
Greater than or equals >= x >= y true if x is greater than or equal to y, false otherwise (x >= y) is false
Less than or equals <= x <= y true if x is less than or equal to y, false otherwise (x <= y) is true
Equality == x == y true if x equals y, false otherwise (x == y) is false
Inequality != x != y true if x does not equal y, false otherwise (x != y) is true

Chú ý: Phân biệt toán tử gán bằng (=) và toán tử so sánh bằng (==).

Ví dụ:

#include <iostream> using namespace std; int sum(int a, int b) { return a + b; } int main() { cout << "Enter an integer: "; int x; cin >> x; cout << "Enter another integer: "; int y; cin >> y; if (x == y) cout << x << " == " << y << "\n"; if (x != y) cout << x << " != " << y << "\n"; if (x > y) cout << x << " > " << y << "\n"; if (x < y) cout << x << " < " << y << "\n"; if (x >= y) cout << x << " >= " << y << "\n"; if (x <= y) cout << x << " <= " << y << "\n"; return 0; }
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

Outputs:

Operators

 

Toán tử quan hệ và so sánh số chấm động?

Trong lập trình, việc so sánh trực tiếp 2 số chấm động là điều không nên và có thể cho ra những kết quả không mong muốn. Đó là do lỗi làm tròn của số chấm động, vấn đề này đã được giải thích trong bài Số tự nhiên và Số chấm động trong C++ (Integer, Floating point).

Ví dụ:

#include <iostream> #include <iomanip> // for std::setprecision() using namespace std; int main() { double d1{ 1.0 }; double d2{ 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 + 0.1 }; if (d1 == d2) cout << "d1 == d2" << "\n"; else if (d1 > d2) cout << "d1 > d2" << "\n"; else if (d1 < d2) cout << "d1 < d2" << "\n"; cout << std::setprecision(20); // show 20 digits cout << "d1 = " << d1 << endl; cout << "d2 = " << d2 << endl; return 0; }
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Outputs:

Operators

 

Trong chương trình trên, trong toán học thì 2 biến d1 == d2, nhưng trong lập trình biến d1 > d2 vì lỗi làm tròn số dấu chấm động.

Tương tự, bạn hãy thử với trường hợp 0.1 + 0.7 == 0.8 ?

Chú ý: Không bao giờ so sánh hai giá trị dấu chấm động bằng nhau hay không. Hầu như luôn luôn có sự khác biệt nhỏ giữa hai số chấm động. Cách phổ biến để so sánh 2 số chấm động là tính khoảng cách giữa 2 số đó, nếu khoảng cách đó là rất nhỏ thì ta cho là bằng nhau. Giá trị dùng để so sánh với khoảng cách đó thường được gọi là epsilon.

Toán tử logic trong C++ (Logical operators)

Nếu chỉ sử dụng toán tử quan hệ để so sánh biểu thức quan hệ đúng hay sai, bạn chỉ có thể kiểm tra một điều kiện tại một thời điểm. Nhưng thực tế, có lúc bạn sẽ cần kiểm tra nhiều điều kiện cùng lúc.

Ví dụ: để trở thành một soái ca thì bạn phải có nhiều điều kiện như cầm, kỳ, thi, họa. Lúc này không chỉ đơn giản 1 điều kiện nữa.

Toán tử logic (Logical operators) sẽ kiểm tra nhiều điều kiện cùng lúc giúp bạn. Có 3 toán tử logic trong C++:

Operator Symbol Form Operation
Logical NOT ! !x true if x is false, or false if x is true
Logical AND && x && y true if both x and y are true, false otherwise
Logical OR || x || y true if either x or y are true, false otherwise

Chú ý: Luôn sử dụng dấu ngoặc đơn () khi thực hiện với các mệnh đề quan hệ để thể hiện rõ ràng ý nghĩa dòng lệnh và hạn chế sai sót. Với cách này, bạn thậm chí không cần nhớ nhiều về độ ưu tiên toán tử.

Ví dụ:

#include <iostream> #include <iomanip> // for std::setprecision() using namespace std; int main() { cout << "Enter a number: "; int value; cin >> value; if (!value) cout << value << " is false" << endl; else cout << value << " is true" << endl; if ((value > 1) && (value < 100)) cout << value << " is between 1 and 100" << endl; else cout << value << " is not between 1 and 100" << endl; if ((value == 1) || (value == 100)) cout << value << " == 1 or "<< value <<" == 100" << endl; else cout << value << " != 1 or " << value << " != 100" << endl; return 0; }
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

Outputs:

Operators

 

Toán tử trên bit trong C++ (Bitwise operators)

Toán tử trên bit dùng để thao tác với các bit trên một biến.

Tại sao cần thao tác trên bit? Trong quá khứ, bộ nhớ máy tính chưa phát triển, vấn đề về quản lý bộ nhớ là rất quan trọng. Vì vậy, người lập trình cần tận dụng tối đa các bit trong bộ nhớ.

Ví dụ: Các biến được lưu trong bộ nhớ ở một địa chỉ duy nhất, những địa chỉ này được xác định với đơn vị nhỏ nhất là byte. Xét kiểu dữ liệu bool, nó chỉ nắm giữ 2 giá trị true (1) hoặc false (0). Kiểu bool chỉ cần 1 bit để lưu trữ dữ liệu, nhưng nó lại chiếm giữ 1 byte trong bộ nhớ, vậy 7 bit còn lại sẽ là lãng phí. Sử dụng toán tử trên bit giúp bạn có thể chứa 8 biến kiểu bool vào 1 byte duy nhất, và tiết kiệm bộ nhớ đáng kể.

Trong quá khứ, sử dụng toán tử trên bit rất được ưu chuộng. Ngày nay, bộ nhớ máy tính đã phát triển và rẻ hơn, lập trình viên thường quan tâm đến tính dễ hiểu và dễ nâng cấp của mã nguồn. Do đó, việc thao tác trên bit không còn được ưu chuộng, ngoại trừ những trường hợp cần tối ưu tối đa tốc độ, bộ nhớ (những chương trình thao tác big data, những game lớn, lập trình nhúng …).

Vì các toán tử trên bit ít gặp nên mình chỉ giới thiệu qua cho các bạn tham khảo, bạn có thể tự tìm hiểu thêm nếu muốn chuyên sâu hơn.

Bảng bên dưới gồm 6 toán tử thao tác trên bit:

Operator Symbol Form Operation
left shift << x << y all bits in x shifted left y bits
right shift >> x >> y all bits in x shifted right y bits
bitwise NOT ~ ~x all bits in x flipped
bitwise AND & x & y each bit in x AND each bit in y
bitwise OR | x | y each bit in x OR each bit in y
bitwise XOR ^ x ^ y each bit in x XOR each bit in y

Bảng bên dưới gồm 5 toán tử gán trên bit:

Operator Symbol Form Operation
Left shift assignment <<= x <<= y Shift x left by y bits
Right shift assignment >>= x >>= y Shift x right by y bits
Bitwise OR assignment |= x |= y Assign x | y to x
Bitwise AND assignment &= x &= y Assign x & y to x
Bitwise XOR assignment ^= x ^= y Assign x ^ y to x

Các toán tử hỗn hợp trong C++ (Misc Operators)

Sizeof operator

Operator Symbol Form Operation
Sizeof sizeof sizeof(type)
sizeof(variable)		 Returns size of type or variable in bytes

Để xác định kích thước của một kiểu dữ liệu trên một máy tính cụ thể, C++ cung cấp cho bạn toán tử sizeof. Toán tử sizeof là toán tử một ngôi, nhận vào một kiểu dữ liệu hoặc một biến, và trả về kích thước (byte) của kiểu dữ liệu hoặc biến đó. Toán tử này sizeof đã được giải thích chi tiết trong bài Số tự nhiên và Số chấm động trong C++ (Integer, Floating point).

Comma operator

Operator Symbol Form Operation
Comma , x, y Evaluate x then y, returns value of y

Các biểu thức đặt cách nhau bằng dấu phẩy (,), các biểu thức con lần lượt được tính từ trái

sang phải. Biểu thức mới nhận được là giá trị của biểu thức bên phải cùng.

Ví dụ:

x = (a++, b = b + 2); // Tương đương với a++; b = b + 2; x = b;
0
1
2
3

hoặc

int x = 0; int y = 2; int z = (++x, ++y); // increment x and y // Tương đương với int x = 0; int y = 2; ++x; ++y; int z = y;
0
1
2
3
4
5
6
7
8
9
10

Chú ý: Dấu phẩy có ưu tiên thấp nhất trong tất cả các toán tử.

Vì vậy, hai dòng code sau đây sẽ cho kết quả khác nhau:

z = (a, b); // z = b z = a, b;   // z = a, và b bị bỏ qua
0
1

Chú ý: Tránh sử dụng các toán tử dấu phẩy (,), ngoại trừ trường hợp dùng trong vòng lặp. Vấn đề về vòng lặp sẽ được hướng dẫn chi tiết trong bài Vòng lặp For trong C++ (For statements).

Conditional operator

Operator Symbol Form Operation
Conditional ?: c ? x : y If c is nonzero (true) then evaluate x, otherwise evaluate y

Toán tử điều kiện ( ?: ) là toán tử 3 ngôi duy nhất trong C++ (có 3 toán hạng), tương đương với câu điều kiện ( if/else statements ).

Cấu trúc câu điều kiện if/else:

if (condition)     // nếu condition là true      expression1;  // thực thi câu lệnh này else      expression2;  // nếu condition là false, thực thi câu lệnh này
0
1
2
3

Hoặc :

if (condition)     // nếu condition là true      x = value1;   // x = value 1 else      x = value2;   // nếu condition là false, x = value 2
0
1
2
3

Viết lại dưới dạng toán tử điều kiện ( ?: ):

(condition) ? expression1 : expression2;
0

Hoặc:

x = (condition) ? value1 : value2;
0

Ví dụ:

#include <iostream> using namespace std; int main() { int x{ 6 }, y{ 9 }, max; if (x > y) { max = x; } else { max = y; } cout << "Max = " << max << endl; // Tương đương với max = (x > y) ? x : y; cout << "Max = " << max << endl; return 0; }
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Outputs:

Operators

Chú ý: Chỉ sử dụng toán tử điều kiện với những câu điều kiện đơn giản.

Ví dụ:

#include <iostream> using namespace std; int main() { int a{ 3 }, b{ 2 }, c{ 4 }, max; // Khó hiểu, dễ sai => Không nên max = a > b ? (a > c ? a : c) : (b > c ? b : c); cout << "Max = " << max << endl; // Dễ hiểu => Nên max = a; if (max < b) { max = b; } if (max < c) { max = c; } cout << "Max = " << max << endl; return 0; }
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

Outputs:

Operators

Chú ý: Toán tử điều kiện ( ?: ) có thể là một biểu thức (expression), trong khi câu điều kiện ( if/else ) chỉ là một câu lệnh (statements).

Ví dụ:

bool bIsVip = true; // Initializing a const variable const double dPrice = bIsVip ? 1000 : 500;
0
1
2
3

Trong ví dụ trên, không thể dùng câu điều kiện ( if/else ) để thay thế. Vì một hằng số phải được khởi tạo giá trị tại thời điểm khai báo.

Một số toán tử khác

Operator Description
. (dot) and -> (arrow) Member operators are used to reference individual members of classes, structures, and unions.
Cast Casting operators convert one data type to another. For example, int(2.2000) would return 2.
& Pointer operator & returns the address of an variable. For example &a; will give actual address of the variable.
* Pointer operator * is pointer to a variable. For example *var; will pointer to a variable var.

Độ ưu tiên và quy tắc kết hợp toán tử trong C++

Để đánh giá đúng một biểu thức như 6 + 9 * 8, bạn cần hiểu rõ ý nghĩa mỗi toán tử trong biểu thức đó, và thứ tự thực hiện của nó. Thứ tự thực hiện của các toán tử trong 1 biểu thức gọi là độ ưu tiên của toán tử (operator precedence).

Khi áp dụng độ ưu tiên toán tử, biểu thức bên trên sẽ tương đương với 6 + ( 9 * 8 ) = 78. Phép nhân (*) có độ ưu tiên cao hơn phép cộng (+), compiler sẽ tự động hiểu và thực hiện đúng theo độ ưu tiên của từng toán tử.

Khi 2 toán tử có cùng độ ưu tiên trong 1 biểu thức, các quy tắc kết hợp (associativity rules) sẽ nói cho compiler biết nên thực hiện từ trái sang phải (L->R) hay từ phải sang trái (R->L).

Ví dụ: bạn có biểu thức 6 * 9 / 8. Trong biểu thức này, phép nhân (*) và chia (/) cùng độ ưu tiên, nhưng nó có quy tắc kết hợp từ trái sang phải (L->R). Vì vậy nó sẽ tương đương (6 * 9) / 8.

Bảng độ ưu tiên (operator precedence) và quy tắc kết hợp (associativity rules) các toán tử trong C++:

Prec/Ass Operator Description Pattern
1 None ::
::		 Global scope (unary)
Class scope (binary)		 ::name
class_name::member_name
2 L->R ()
()
()
{}
type()
type{}
[]
.
->
++
––
typeid
const_cast
dynamic_cast
reinterpret_cast
static_cast		 Parentheses
Function call
Initialization
Uniform initialization (C++11)
Functional cast
Functional cast (C++11)
Array subscript
Member access from object
Member access from object ptr
Post-increment
Post-decrement
Run-time type information
Cast away const
Run-time type-checked cast
Cast one type to another
Compile-time type-checked cast		 (expression)
function_name(parameters)
type name(expression)
type name{expression}
new_type(expression)
new_type{expression}
pointer[expression]
object.member_name
object_pointer->member_name
lvalue++
lvalue––
typeid(type) or typeid(expression)
const_cast<type>(expression)
dynamic_cast<type>(expression)
reinterpret_cast<type>(expression)
static_cast<type>(expression)
3 R->L +
–
++
––
!
~
(type)
sizeof
&
*
new
new[]
delete
delete[]		 Unary plus
Unary minus
Pre-increment
Pre-decrement
Logical NOT
Bitwise NOT
C-style cast
Size in bytes
Address of
Dereference
Dynamic memory allocation
Dynamic array allocation
Dynamic memory deletion
Dynamic array deletion		 +expression
-expression
++lvalue
––lvalue
!expression
~expression
(new_type)expression
sizeof(type) or sizeof(expression)
&lvalue
*expression
new type
new type[expression]
delete pointer
delete[] pointer
4 L->R ->*
.*		 Member pointer selector
Member object selector		 object_pointer->*pointer_to_member
object.*pointer_to_member
5 L->R *
/
%		 Multiplication
Division
Modulus		 expression * expression
expression / expression
expression % expression
6 L->R +
–		 Addition
Subtraction		 expression + expression
expression – expression
7 L->R <<
>>		 Bitwise shift left
Bitwise shift right		 expression << expression
expression >> expression
8 L->R <
<=
>
>=		 Comparison less than
Comparison less than or equals
Comparison greater than
Comparison greater than or equals		 expression < expression
expression <= expression
expression > expression
expression >= expression
9 L->R ==
!=		 Equality
Inequality		 expression == expression
expression != expression
10 L->R & Bitwise AND expression & expression
11 L->R ^ Bitwise XOR expression ^ expression
12 L->R | Bitwise OR expression | expression
13 L->R && Logical AND expression && expression
14 L->R || Logical OR expression || expression
15 R->L ?:
=
*=
/=
%=
+=
-=
<<=
>>=
&=
|=
^=		 Conditional (see note below)
Assignment
Multiplication assignment
Division assignment
Modulus assignment
Addition assignment
Subtraction assignment
Bitwise shift left assignment
Bitwise shift right assignment
Bitwise AND assignment
Bitwise OR assignment
Bitwise XOR assignment		 expression ? expression : expression
lvalue = expression
lvalue *= expression
lvalue /= expression
lvalue %= expression
lvalue += expression
lvalue -= expression
lvalue <<= expression
lvalue >>= expression
lvalue &= expression
lvalue |= expression
lvalue ^= expression
16 R->L throw Throw expression throw expression
17 L->R , Comma operator expression, expression
Có thể bạn sẽ không hiểu phần lớn những toán tử trong bảng trên ở thời điểm này, bạn chỉ cần quan tâm đến những toán tử vừa học ở phần trên. Những toán tử còn lại bạn có thể tự tìm hiểu nếu bạn có nhu cầu đặt biệt nào đó.
Chủ đề: C++, Ngôn ngữ lập trình

VCOWFLIX – spoj

August 9, 2017 by Leave a Comment

Đề bài: http://vn.spoj.com/problems/VCOWFLIX/

Thuật toán:

  • Gọi L[i][j] tổng khối lượng bò lớn nhất mà John có thể mang đi xem phim khi có i con bò và sức chứa của xe là j.
    • Nếu a[i]<=j thì L[i,j]:=max(L[i-1,j], L[i-1,j-a[i]]+a[i]);
    • Nếu a[i]>j thì L[i,j]:=L[i-1,j];

Code:

uses    math;
const   fi='';
        fo='';
        maxn=16;
        oo=5000;
var     l:array[0..maxn,0..5000] of longint;
        a:array[1..maxn] of longint;
        i,j,c,n:longint;
begin
        assign(input,fi);reset(input);
        assign(output,fo);rewrite(output);

        readln(c,n);
        for i:=1 to n do read(a[i]);

        for i:=1 to n do
                for j:=0 to c do
                        begin
                            l[i,j]:=l[i-1,j];
                            if a[i]<=j then
                                l[i,j]:=max(l[i,j],l[i-1,j-a[i]]+a[i]);
                        end;

        writeln(l[n,c]);

        close(input);close(output);
end.
Chủ đề: Quy hoạch động

Các cấu trúc điều khiển trong C++

August 9, 2017 by Leave a Comment

Cấu trúc lặp for

   for(biểu_thức_1; biểu_thức_2; biểu_thức_3)
   {
      Câu lệnh 1;
      ...
      Câu lệnh n;
   }
  • Ý nghĩa từng biểu thức:
  • biểu_thức_1: thường dùng khởi tạo biến đếm vòng lặp.
  • biểu_thức_2: thường dùng kiểm tra điều kiện vòng lặp.
  • biểu_thức_3: thường dùng điều khiển biến đếm của vòng lặp
  • Ví dụ: for(int i=0; i<10; i++)
  • Thứ tự thực hiện:
    • Bước 1: Xác định biểu_thức_1
    • Bước 2: Xác định biểu_thức_2
    • Bước 3: Nếu biểu_thức_2 đúng chương trình sẽ thực hiện khối lệnh trong vòng lặp for. Ngược lại thoát khỏi for.
    • Bước 4: Tính biểu_thức_3, sau đó quay lại bước 2 để bắt đầu vòng lặp mới.

Cấu trúc điều khiển rẽ nhánh if

   if(biểu_thức_điều_kiện)
   {
      Câu lệnh 1;
      ...
      Câu lệnh n;
   }

Cấu trúc điều khiển rẽ nhánh if…else

   if(biểu_thức_điều_kiện)
   {
      Câu lệnh 1;
      ...
      Câu lệnh n;
   }
   else
   {
      Câu lệnh 1;
      ...
      Câu lệnh n;
   }

Cấu trúc điều khiển switch

   switch(biều_thức_chọn)
   {
      case Giá_trị_1:
            Lệnh_1;
            Lệnh_2;
            ...
            break;
      case Giá_trị_2:
            Lệnh_1;
            Lệnh_2;
            ...
            break;
      default:
            Lệnh_1;
            Lệnh_2;
            ...
            break;
   }
  • biều_thức_chọn trong switch sẽ được so sánh với các giá trị trong tương ứng với các mệnh đề case.
  • Nếu giá trị biều_thức_chọn bằng Giá_trị_i thì khối lệnh của case i được thực hiện. Ngược lại thì khối lệnh tương ứng với khóa default được thực hiện.

Cấu trúc điều khiển lặp while

   while(<điều_kiện_lặp)
   {
      Câu lệnh 1;
      ...
      Câu lệnh n;
   }
  • Điều kiện lặp được kiểm tra trước khi thực hiện khối lệnh

Cấu trúc lặp while

   do
   {
      Câu lệnh 1;
      ...
      Câu lệnh n;
   }while(điều_kiện_lặp);
  • Điều kiện lặp được kiểm tra khi khối lệnh được thực hiện xong. Do đó khối lệnh trong vòng lặp được thực hiện ít nhất 1 lần
Chủ đề: C++

SHHV – spoj

August 9, 2017 by Leave a Comment

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include 
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 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 = 13;
const int oo = 1e9+3;
string s;

ll gt[MAXN+1];
int n, x, a[MAXN+1], b[MAXN+1], i, j;
bool chon[MAXN+1];
ll t;

void init() {
    gt[0] = 1;
    gt[1] = 1;
    for (int i=2; i<=MAXN; i++) gt[i] = gt[i-1]*i;
}

void query1() {
    ll ans = 0;
    memset(chon,0,sizeof(chon));
    for (int i=1; i<=n; i++) {
        for (int j=1; j<=a[i]-1; j++)
        if (!chon[j]) {
            ans += gt[n-i];
        }
        chon[a[i]] = 1;
    }
    cout << ans+1 << endl;
}

void query2() {
    memset(chon,0,sizeof(chon));
    t--;
    for (i=1; i<=n; i++) {
        int tmp = 0;
        for (j=1; j<=n; j++) {
            if (!chon[j]) tmp++;
            if (gt[n-i]*tmp>t) break;
        }
        t -= gt[n-i]*(tmp-1);
        b[i] = j;
        chon[j]=1;
    }
    for (int i=1; i<=n; i++) cout << b[i] << " ";
}

int main() {
    	#ifndef ONLINE_JUDGE
    	freopen("test.inp", "r", stdin);
    	freopen("test.out", "w", stdout);
    	#endif
    while (cin>>a[++n]);
    t=a[--n]; n--;
    init();
    query1();
    query2();
    return 0;
}
Chủ đề: Toán học

BONUS13 – spoj

August 9, 2017 by Leave a Comment

Đề bài:

Thuật toán:

Code:

uses    math;
const   fi='';
        fo='';
        maxn=80;
        n=8;
        hx:array[1..8] of integer=(-1,-2,-2,-1,1,2,2,1);
        hy:array[1..8] of integer=(-2,-1,1,2,2,1,-1,-2);
type    point=record
                x,y:byte;
                end;
var     cx,dx:array[1..maxn] of point;
        a:array[1..8,1..8] of boolean;
        c:array[1..maxn] of longint;
        i,j,k:longint;
        top1,top2:longint;
        hau,xe,ma,tuong:array[1..maxn,1..maxn] of boolean;
        m,t,x,h : longint;
        res:int64;
procedure nhap;
var     u,v:byte;
        w:longint;
begin
    assign(input,fi);reset(input);
    readln(k);
    for i:=1 to k do
        begin
            readln(u,v,w);
            a[u,v]:=true;
            inc(top1); dx[top1].x:=u; dx[top1].y:=v; c[top1]:=w;
        end;
    close(input);
end;
procedure init;
begin
    res:=0;
    for i:=1 to 8 do
        for j:=1 to 8 do
                if a[i,j]=false then
                        begin
                               inc(top2);
                               cx[top2].x:=i;
                               cx[top2].y:=j;
                        end;
end;
function chau(i,j:longint):boolean;
begin
    if cx[i].x=dx[j].x then exit(true);
    if cx[i].y=dx[j].y then exit(true);
    if (cx[i].x+cx[i].y)=(dx[j].x+dx[j].y) then exit(true);
    if (cx[i].x-cx[i].y)=(dx[j].x-dx[j].y) then exit(true);
    exit(false);
end;
function cxe(i,j:longint):boolean;
begin
    if cx[i].x=dx[j].x then exit(true);
    if cx[i].y=dx[j].y then exit(true);
    exit(false);
end;
function ctuong(i,j:longint):boolean;
begin
    if (cx[i].x+cx[i].y)=(dx[j].x+dx[j].y) then exit(true);
    if (cx[i].x-cx[i].y)=(dx[j].x-dx[j].y) then exit(true);
    exit(false);
end;
function cma(i,j:longint):boolean;
var     k,u,v:integer;
begin
    for k:=1 to 8 do
        begin
            u:=cx[i].x+hx[k];
            v:=cx[i].y+hy[k];
            if (u=dx[j].x) and (v=dx[j].y) then exit(true);
        end;
    exit(false);
end;
procedure xuly;
var     i,j:longint;
begin
    for i:=1 to top2 do
        for j:=1 to top1 do
         begin
          if chau(i,j) then hau[i,j]:=true;
          if cxe(i,j) then xe[i,j]:=true;
          if cma(i,j) then ma[i,j]:=true;
          if ctuong(i,j) then tuong[i,j]:=true;
         end;
end;
procedure main;
var     tam:int64;
begin
    for h:=1 to top2 do
        for x:=1 to top2 do
                if h<>x then
                        for m:=1 to top2 do
                                if (m<>h) and (m<>x) then
                                        for t:=1 to top2 do
                                                if (m<>t) and (t<>x) and (t<>h) then
                                                  begin
                                                        tam:=0;
                                                        for i:=1 to top1 do
                                                                if hau[h,i] or xe[x,i] or ma[m,i] or tuong[t,i] then tam := tam + c[i];
                                                        res:=max(res,tam);
                                                  end;

end;
procedure inkq;
begin
    assign(output,fo);rewrite(output);
    writeln(res);
    close(output);
end;
begin
    nhap;
    init;
    xuly;
    main;
    inkq;
end.

#include 
#include 
using namespace std;
#define LL long long
#define rep(i, a, b) for (int i=a; i& a) {
    LL res = 0;
    for (auto &x: a) {
        if (state & 1) res += x.w;
        state >>= 1;
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int m; cin >> m;
    vector a(m);
    vector frei(64, true);
    for (auto &a: a) {
        cin >> a.x >> a.y >> a.w;
        a.x--, a.y--;
        frei[a.x*8+a.y] = false;
    }
    vector xe(64, 0), tuong(64, 0), ma(64, 0), hau(64, 0);
    int c = 0;
    rep(i, 0, 8) rep(j, 0, 8) if (frei[c]) {
        rep(k, 0, m) {
            int x = a[k].x, y = a[k].y;
            if (x==i || y==j) xe[c] |= 1ll<
Chủ đề: Vét cạn

C11CAVE – spoj

August 9, 2017 by Leave a Comment

Đề bài:

Thuật toán:

  • Chỉ cần duyệt từ 1 đến h rồi kiểm tra, bạn đọc code bên dưới sẽ hiểu.

Code:

    const           fi      = '';
                    fo      = '';
                    maxn    = 1000000;

    var
                    n , h   : longint;
                    m       : longint;
                    d , c   : array[ 0..maxn ] of longint;

    procedure   enter;
        var
                i           : longint;
                u , v       : longint;
        begin
                read( n , h );
                m := n div 2;
                for i := 1 to m do
                  begin
                    read( u , v );
                    inc( d[ u ] );
                    inc( c[ v ] );
                  end;
        end;

    procedure   prepair;
        var
                i           : longint;
        begin
                for i := 1 to h do
                  begin
                    d[ i ] := d[ i-1 ] + d[ i ];
                    c[ i ] := c[ i-1 ] + c[ i ];
                  end;
        end;


    procedure   solve;
        var
                res , num   : longint;
                i , tmp     : longint;
        begin
                res := n+1;
                num := 0;
                for i := 1 to h do
                  begin
                    tmp := d[ h ] - d[ i-1 ] + c[ h ] - c[ h-i ];
                    if res > tmp then
                      begin
                        res := tmp;
                        num := 1;
                      end
                    else
                      if res = tmp then inc( num );
                  end;
                writeln( res , ' ' , num );
        end;



    BEGIN

                assign( input , fi ); reset( input );
                assign( output , fo ); rewrite( output );

                enter;
                prepair;
                solve;

                close( input ); close( output );

    END.
Chủ đề: Vét cạn

MESSAGE1 – spoj

August 9, 2017 by Leave a Comment

[mathjax]

Đề bài

Thuật toán
message1-yeulaptrinh.pw

Ở bài này ta dời bảng B như hình, trong mỗi lần dời ta so sách các ô trong vùng giao nhau nữa 2 bảng, ô bằng nhau có giá trị 1, khác nhau có giá trị 0.

Cụ thể hơn, giả sử ta dời bảng B theo một vector $(x, y)$, khi đó ô $A(i, j)$ sẽ được so sánh với ô $B(i-x, j-y)$. Ta tính toạ độ các ô trong phần giao giữa 2 bảng như sau, có 4 điều kiện:

$
\begin{cases}
0 <= i < m\\
0 <= j < n\\
0 <= i-x < m\\
0 <= i-y < n\\
\end{cases}
$

Từ đó suy ra:

$
\begin{cases}
max(0, x) <= i < min(m, m + x)\\
max(0, y) <= j < min(n, n + y)\\
\end{cases}
$

Sau đó ta tìm hình chữ nhật chứa toàn số 1 và có diện tích lớn nhất (như bài QBRECT).

Sau đây là cách tìm hình chữ nhật như trên 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)\times(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)$:

message1-2-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.

Độ phức tạp của toàn bộ lời giải là $O(n^4)$.

Code

#include 
#include 
#include 
using namespace std;

void calc(int &res, int x, int y, const vector &a, const vector &b) {
    int m = a.size(), n = a[0].size();
    int low_i = max(0, x), high_i = min(m, m + x);
    int low_j = max(0, y), high_j = min(n, n + y);
    if ((high_i - low_i)*(high_j - low_j) <= res) return;
    vector f(high_j, 0);
    vector l(high_j), q(high_j), idx(high_j);
    for (int i=low_i; i < high_i; i++) {
        int top = 0;
        for (int j=low_j; j < high_j; j++) {
            if (a[i][j] == b[i-x][j-y]) {
                f[j]++;
                while (top && q[top-1]>=f[j]) top--;
                if (!top) l[j] = low_j-1;
                else l[j] = idx[top-1];
                q[top] = f[j], idx[top] = j, top++;
            } else {
                f[j] = 0;
                q[0] = 0, idx[0] = j, top = 1;
            }
        }
        top = 0;
        int r;
        for (int j=high_j-1; j >= low_j; j--) {
            if (f[j]) {
                while (top && q[top-1]>=f[j]) top--;
                if (!top) r = high_j;
                else r = idx[top-1];
                res = max(res, f[j]*(r - l[j] - 1));
                q[top] = f[j], idx[top] = j, top++;
            } else {
                q[0] = 0, idx[0] = j, top = 1;
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int T; cin >> T;
    while (T--) {
        int n, m; cin >> m >> n;
        vector a(m), b(m);
        for (auto &s: a) cin >> s;
        for (auto &s: b) cin >> s;
        int res = 0;
        for (int i=-m+1; i
Chủ đề: Cấu trúc dữ liệu, Deque

FIBVAL – spoj

August 9, 2017 by Leave a Comment

Đề bài

Thuật toán

Để giải được bài này, ta cần áp dụng 1 tính chất đặc biệt của dãy Fibonacci, đó là chu kỳ Pisano

Dãy Fibonacci có dạng:

  • f(0) = 0
  • f(1)=1
  • f(i)=f(i-1)+f(i-2)

Đối với 1 số nguyên n bất kì thì dãy g(i)=f(i) mod n có tính chu kì.

Ví dụ: Với n=3 ta có:

f 0 1 1 2 3 5 8 13 15 28 43 …
g 0 1 1 2 0 2 2 1 0 1 1 …

Ở bài này, ta có chu kì gồm 7 nốt nhạc vì vậy ta xét tính chu kì trên dãy g(i)=f(i) mod 7.

Chu kì Peisano của 7 trong bài này gồm 16 số:

 1 2 3 5 1 6 0 6 6 5 4 2 6 1 0 1

Như vậy, độ dài đoạn nhạc dài nhất có tính chu kì chỉ có thể là 2 hoặc có dạng 16*k.

Code

CONST
    tfi = '';
    tfo = '';
VAR
    fi,fo           : text;

Function pro(l,r: longint): longint;
    Var
        len,res: longint;
    Begin
        len:=r-l+1;
        l:=l mod 16;
        r:=r mod 16;
        If l=0 then l:=16;
        If r=0 then r:=16;
        res:=len div 16;
        If len>=32 then exit(res*16)
        else
            If len>=9 then exit(2)
            else
                If ((l=9)) or ((l>9) and (r0 do
            begin
                read(fi,l,r);
                writeln(fo,pro(l,r));
                dec(test);
            end;
    End;

BEGIN
    assign(fi,tfi); reset(fi);
    assign(fo,tfo); rewrite(fo);
        process;
    close(fi); close(fo);
END.

Nguồn: không rõ

Chủ đề: Toán học