1
MỤC LỤC
LỜI MỞ ĐẦU............................................................................................................................3
PHẦN I. SỐ HỌC.....................................................................................................................3
BÀI 1. 3620. Số phong phú - http://vn.spoj.pl/problems/NKABD/.......................................3
Bài 2. 1783. Tìm số nguyên tố - http://vn.spoj.pl/problems/PNUMBER/.............................7
Bài 3. 3632. Số thân thiện - http://vn.spoj.pl/problems/NKNUMFRE/...............................10
Bài 4. 4141. Euler Totient Function - http://vn.spoj.pl/problems/ETF/...............................13
PHẦN II. XỬ LÝ CHUỖI......................................................................................................14
Bài 1. 4257. First Number - http://vn.spoj.pl/problems/MDIGITS2/...................................14
Bài 2. 3638. Word Counting - http://vn.spoj.pl/problems/WORDCNT/..............................15
Bài 3. Tập số - Chuyên tin 2011...........................................................................................17
PHẦN III. ĐỒ THỊ.................................................................................................................19
Bài 1. 2722. Gặm cỏ - http://vn.spoj.pl/problems/VMUNCH/............................................19
Bài 2. 2719. Bãi cỏ ngon nhất - http://vn.spoj.pl/problems/VBGRASS/.............................22
Bài 3. 2721. Nước lạnh - http://vn.spoj.pl/problems/VCOLDWAT/...................................25
Bài 4. Hexgame - Chuyên tin 2011......................................................................................27
Bài 5. 3478. Xây dựng thành phố - http://vn.spoj.pl/problems/NKCITY/...........................30
Bài 6. 3125. Đến trường - http://vn.spoj.pl/problems/QBSCHOOL/...................................34
PHẦN IV. QUY HOẠCH ĐỘNG..........................................................................................37
Bài 1. 2356. Lát gạch - http://vn.spoj.pl/problems/LATGACH/..........................................37
Bài 2. 3883. Lát gạch 3 - http://vn.spoj.pl/problems/M3TILE/............................................40
Bài 3. 2795. Steps - http://vn.spoj.pl/problems/VSTEPS/....................................................42
Bài 4. 2782. Đường đi có tổng lớn nhất - http://vn.spoj.pl/problems/QBMAX/ .................44
PHẦN V. CÁC BÀI TOÁN KHÁC.......................................................................................46
Bài 1. Đấu giá - Chuyên tin 2010.........................................................................................46
Bài 2. Trông xe - Chuyên tin 2010.......................................................................................48
Bài 3. 3480. Cây nhị phân tìm kiếm - http://vn.spoj.pl/problems/NKTREE/......................49
2
Bài 4. 2786. Cây khung nhỏ nhất (HEAP) - http://vn.spoj.pl/problems/QBMST/...............51
Bài 5. 4031. Mass of Molecule- http://vn.spoj.pl/problems/MMASS/................................52
3
LỜI MỞ ĐẦU
Để phục vụ cho việc ôn luyện thi Olympic khối chuyên tin năm 2012, các thành viên
của đội tuyển Olympic chuyên tin năm 2011, Khoa Công nghệ thông tin - Đại học
Hàng Hải sẽ tổng hợp lại các bài tập đã giải được, bao gồm các bài tập trên trang Giải
bài trực tuyến: http://vn.spoj.pl/problems/oi/, các bài thi Olympic các năm trước và
một số bài tập khác.
Các bài ôn luyện sẽ được phân vào các phần khác nhau bao gồm:
•PHẦN I. SỐ HỌC
•PHẦN II. ĐỒ THỊ
•PHẦN III. QUY HOẠCH ĐỘNG
•PHẦN IV. CÁC BÀI TOÁN KHÁC
Ngôn ngữ lập trình được sử dụng trong các bài chủ yếu là C/C++.
Trong quá trình biên soạn sẽ không thể tránh khỏi những sai sót, đội tuyển rất hoan
nghênh sự đóng góp từ tất cả các bạn. Mọi ý kiến phản hồi xin gửi về hòm thư:
olptin@vimaru.edu.vn hoặc trungvdt49@gmail.com . Chân thành cảm ơn!
PHẦN I. SỐ HỌC
BÀI 1. 3620. Số phong phú - http://vn.spoj.pl/problems/NKABD/
Trong số học, số phong phú là các số mà tổng các ước số của số đó (không kể chính
nó) lớn hơn số đó. Ví dụ, số 12 có tổng các ước số (không kể 12) là 1 + 2 + 3 + 4 + 6 =
16 > 12. Do đó 12 là một số phong phú.
Bạn hãy lập trình đếm xem có bao nhiêu số phong phú trong đoạn [L,R].
Dữ liệu
Gồm 2 số L, R (1 <= L <= R <= 10^5)
Kết quả
Gồm 1 số nguyên duy nhất là số số phong phú trong đoạn [L, R].
Chú ý
Có 50% số test có 1 <= L <= R <= 10^3
4
Ví dụ
Dữ liệu
1 50
Kết quả
9
Giải thích:
Từ 1 đến 50 có 9 số phong phú là: 12, 18, 20, 24, 30, 36, 40, 42, 48
Time: 1s
Giải
Cách giải thông thường là duyệt từng số nguyên từ L đến R, tính tổng các ước của số
đó không kể chính nó và kiểm tra nếu tổng đó lớn hơn số đó thì tăng biến đếm lên 1.
Để liệt kê các ước và tính tổng tất cả các ước của một số a không kể a ta chỉ việc kiểm
tra lần lượt các số từ 1 cho đến a/2, nếu a chia hết thi in ra ước và cộng thêm ước vào
biến tổng, đoạn mã như sau:
int main()
{
int a;
int i;
int tong=0;
scanf("%d",&a);
for(i=1;i<=a/2;++i)
{
if(a%i==0)
{
printf("%d ",i);
tong += i;
}
}
printf("\n%d",tong);
system("pause");
return 0;
}
Để ý một chút ta thấy, không nhất thiết phải duyệt từ 1 cho đến a/2 mà chỉ cần duyệt
các số i chạy từ 2 cho đến căn bậc 2 của a là đủ, nếu a chia hết cho i thì tong = tong + i
+ a/i (chú ý là nếu a/i = căn bậc 2 của a thì tong = tong + i). Đoạn mã như sau:
#include <stdio.h>
#include <math.h>
int main()
{
5
int a;
int i;
int tong=1;
scanf("%d",&a);
int cb2 = (int)sqrt(a);
printf("Cac uoc cua %d la:\n 1 ",a);
for(i=2;i<cb2;++i)
{
if(a%i==0)
{
printf("%d %d ",i,a/i);
tong += i+a/i;
}
}
if(a%cb2==0)
{
tong += cb2;
printf("%d ",cb2);
if(a != cb2*cb2)
{
tong+=a/cb2;
printf("%d",a/cb2);
}
}
printf("\nTong uoc cua %d = %d",a,tong);
//system("pause");
return 0;
}
Tuy nhiên nếu mỗi lần xét 1 số trong đoạn [L,R] lại chạy hàm kiểm tra xem số đó có
phải là số phong phú không thì sẽ rất mất thời gian. Thay vì điều đó ta sẽ dùng thuật
toán khá giống với tư tưởng của sàng nguyên tố với nhận xét nếu một số a viết dưới
dạng i*j thì i và j chính là ước của a. Đoạn mã đầu tiên như sau (time=0.08s):
#include <stdio.h>
int a[100001];
int main()
{
int l,r,i,j,k=0;
scanf("%d%d",&l,&r);
for(i = 1; i<=r; i++)
a[i] = 1;
for(i = 2; i<=r/2; i++)
{
for(j = 2; j*i<=r; j++)
a[j*i] += i;
}
for(i=l; i<=r; i++)
if(a[i] > i) k++;
printf("%d",k);
//system("pause");