Đề thi HSG Tin học THPT Tỉnh Ninh Bình – Năm học 2020– 2021 – Có code tham khảo
Đề thi HSG Tin học THPT Tỉnh Ninh Bình – Năm học 2020– 2021
Tổng quan đề thi
| Bài | Tên bài | File
chương trình |
File
dữ liệu vào |
File kết quả | Thời gian/ Bộ nhớ |
| 1 | Số dư | DARR.* | DARR.INP | DARR.OUT | 1 giây/ test, 1024Mb |
| 2 | Dãy số | DELARR.* | DELARR.INP | DELARR.OUT | 1 giây/ test, 1024Mb |
| 3 | Sơ tán | EVA.* | EVA.INP | EVA.OUT | 1 giây/ test, 1024Mb |
| 4 | Vùng đất | LAND.* | LAND.INP | LAND.OUT | 1 giây/ test, 1024Mb |
Dấu * được thay bởi PAS hoặc CPP của ngôn ngữ lập trình tương ứng là Pascal hoặc C++
Hãy lập trình giải các bài toán sau:
Bài 1 (5,0 điểm):Số dư
Bạn được cho một dãy số nguyên dương .
Yêu cầu: Hãy tìm giá trị lớn nhất của phần dư trong phép chia số nguyên cho . Với và .
Dữ liệu vào: Cho file văn bản DARR.INP
- Dòng đầu tiên chứa số nguyên dương – độ dài của dãy (.
- Dòng thứ hai chứa số nguyên lần lượt là .
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Dữ liệu ra: Ghi ra file văn bản DARR.OUT một số nguyên là kết quả của bài toán.
Ví dụ:
| DARR.INP | DARR.OUT | Giải thích |
| 3
2 4 5 |
1 | 4 chia 2 dư 0;
5 chia 2 dư 1; 5 chia 4 dư 1; Kết quả số dư lớn nhất là 1 |
Ràng buộc: 70% số test có .
Bài 2 (5,0 điểm): Dãy số
Cho một dãy n số nguyên có giá trị lần lượt từ 1 đến n. Bạn được thực hiện m thao tác, mỗi thao tác sẽ xóa một số khỏi dãy tại một vị trí bất kỳ. Sau mỗi thao tác xóa thì tất cả các số đằng sau chưa bị xóa sẽ được dồn về phía trước.
Yêu cầu: Cho biết vị trí cần xóa của m thao tác, viết chương trình xác định số bị xóa trong mỗi thao tác. Nếu trong một thao tác không có số nào bị xóa thì ghi ra số 0.
Dữ liệu vào: Cho file DELARR.INP
- Dòng đầu tiên ghi hai số nguyên lần lượt là n, m (1≤ n, m ≤ 300000).
- Dòng thứ 2 ghi m số nguyên lần lượt là các vị trí cần xóa.
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Dữ liệu ra: Ghi vào file văn bản DELARR.OUT gồm m dòng, dòng thứ i là số bị xóa ở lượt thứ i. (1≤ i ≤ n)
Ví dụ:
Ràng buộc: 30% số test có
30% số test có .
40% số test có .
Bài 3 (5,0 điểm): Sơ tán
Một Trung tâm nghiên có n phòng thí nghiệm đặt ngầm trong lòng đất. Các phòng thí nghiệm được đánh số từ 1 đến n (1 ≤ n ≤ 105). Trung tâm có tất cả m đoạn đường hầm hai chiều nối trực tiếp hai phòng với nhau (1 ≤ m ≤ 105), sao cho từ một phòng bất kỳ có thể đi đến phòng còn lại (có thể phải đi qua một số phòng trung gian). Không có đoạn đường hầm nào nối một phòng với chính nó, nhưng có thể có nhiều đoạn đường hầm cùng nối 2 phòng với nhau. Có k phòng có lối thoát hiểm lên trên mặt đất (1 ≤ k ≤ n). Trong trường hợp phải sơ tán khẩn cấp, tất cả các nhân viên phải tập trung ở những phòng có lối thoát hiểm lên trên mặt đất.
Yêu cầu: Hãy xác định quãng đường ngắn nhất để nhân viên mỗi phòng tập trung về phòng có lối thoát hiểm lên trên mặt đất trong trường hợp phải sơ tán khẩn cấp.
Dữ liệu vào: Cho file văn bản EVA.INP.
- Dòng đầu tiên chứa 2 số nguyên n và k.
- Dòng thứ 2 chứa k số nguyên khác nhau cho biết các phòng có cửa thoát hiểm.
- Dòng thứ 3 chứa số nguyên m.
- Mỗi dòng trong m dòng tiếp theo chứa 3 số nguyên xác định cặp phòng có đoạn đường hầm nối trực tiếp và độ dài của đoạn đường hầm đó.
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Dữ liệu ra: Ghi ra file văn bản EVA.OUT một dòng chứa n số nguyên, số thứ i xác định quãng đường ngắn nhất để nhân viên phòng i đi được tới phòng có lối thoát hiểm lên trên mặt đất. (1 ≤ i ≤ n).
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Ví dụ:
Ràng buộc: 30% số test có và k =1.
30% số test có .
40% số test có và k < 10.
Bài 4 (5,0 điểm): Vùng đất
Do hiện tượng khí hậu ấm lên trên toàn cầu, mực nước biển dâng theo từng năm. Các nhà khoa học đã mô hình hóa quá trình ngập nước của một vùng đất. Giả sử vùng đất đã mô hình hóa quá trình ngập nước được chia thành m x n ô vuông nhỏ. Do có nhiều mạch ngầm thông với biển nên khi nước biển dâng bằng độ cao của một ô vuông thì coi như toàn bộ ô vuông đất bị ngập. Các nhà khoa học đã tính được độ cao của toàn bộ vùng đất và dự đoán được mức nước biển dâng sau từng năm, từ đó dự báo được năm (thời điểm) mà ô đất sẽ bị ngập.
Yêu cầu: Cho bảng số liệu dự báo thời gian ngập nước của các ô đất. Hãy cho biết có bao nhiêu mảnh đất không bị ngập nước trong các năm cần báo cáo. Một mảnh đất không bị ngập nước là tập hợp các ô vuông không bị ngập nước liên thông cạnh với nhau.
Ví dụ xét một vùng đất có kích thước 4 x 5 ô, giá trị trong mỗi ô là năm mà nước sẽ ngập ô đó. Các ô màu trắng chỉ nước ngập và các ô màu đen chỉ nước không ngập. Vào năm thứ nhất có 2 mảnh đất không bị ngập nước và vào năm thứ hai có 3 mảnh đất không ngập nước:
Dữ liệu vào: Cho file văn bản LAND.INP
- Dòng đầu tiên ghi hai số nguyên dương m, n (1≤ m, n ≤ 1000).
- m dòng tiếp theo mỗi dòng ghi n số nguyên, số thứ j của dòng (i+1) là một số thể hiện năm mà ô đất (i,j) bị ngập. (1≤ i ≤ m, 1≤ j ≤ n).
- Dòng tiếp theo ghi một số nguyên k là số lượng năm cần báo cáo (1≤ k ≤105).
- Dòng cuối ghi k số nguyên là danh sách các năm cần báo cáo số lượng mảnh đất không bị ngập nước. Các năm được sắp xếp theo thứ tự tăng dần.
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Dữ liệu ra: Ghi trong file văn bản LAND.OUT gồm k số trên một dòng lần lượt là số lượng mảnh đất không bị ngập nước của các năm trong danh sách.
(Mỗi số trên một dòng cách nhau bởi một dấu cách)
Ví dụ:
Ràng buộc: 30% số test có .
30% số test có .
40% số test có .
—–Hết—–
Code C++ Đề thi HSG Tin học THPT Tỉnh Ninh Bình – Năm học 2020– 2021
Bài 1
[rml_read_more]
#include<bits/stdc++.h>
using namespace std;
int n,a[1000001]
,res=0;
int main()
{
freopen("darr.inp","r",stdin);
freopen("darr.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i]
;
sort(a+1,a+1+n);
for(int j=n-1;j>=1;j--)
{
if(a[j]
<res) break;
else
for(int k=2;k<=a[n] /a[j]
+1;k++)
{
int i=lower_bound(a+j,a+1+n,a[j]
*k)-a-1;
res=max(res,a[i] %a[j]
);
}
}
cout<<res;
}
Bài 2:
#include<bits/stdc++.h>
#define fast ios::sync_with_stdio(0)
using namespace std;
int n,m,a[1000001]
,res=0;
int t[1000001]
;
void update(int i,int vt)
{
t[i] =t[i]
+vt;
while(i<=n)
{
i=i+(i&-i);
t[i] =t[i]
+vt;
}
}
int get(int i)
{
int res=0;
while(i>0)
{
res=res+t[i]
;
i=i-(i&-i);
}
return res;
}
int find(int i)
{
int d=1,c=n,mid;
while (d<=c){
mid=(d+c)/2;
if (get(mid)==i) return mid;
if (get(mid)>i) c=mid-1;
if (get(mid)<i) d=mid+1;
}
return 0;
}
int main()
{
freopen("delarr.inp","r",stdin);
freopen("delarr.out","w",stdout);
fast;
cin>>n>>m;
for(int i=1;i<=n;i++) update(i,1);
for (int i=1;i<=m;i++){
int x;
cin>>x; x=find(x);
cout<<x<<"\n";
if (x>0) update(x,-1);
}
}
Bài 3:
#include <bits/stdc++.h>
#define x first;
#define y second;
#define fast ios::sync_with_stdio(0)
using namespace std;
typedef pair <int,int> ii;
vector <ii> a[100001]
;
int b[100001] ,dx[100001]
;
const int oo=1e9;
int n,m,k;
priority_queue <ii> qu;
int d[500000] ,xd[500000]
;
void dij(int s)
{
for (int i=1;i<=n;i++) {d[i] =oo; xd[i]
=0;}
d[s]
=0;
qu.push(ii(0,s));
int dem=0;int u;
while (dem<n){
while (qu.size()>0){
ii c=qu.top();qu.pop();
u=c.y;
if (xd[u]
==1) continue;
for (int j=0;j<a[u]
.size();j++){
int v=a[u] [j]
.x;
int c=a[u] [j]
.y;
if (d[v] >d[u]
+c)
{ d[v] = d[u]
+c;
qu.push(ii(-d[v]
,v));
}
}
++dem; xd[u]
=1;
}
}
}
int main()
{
freopen("eva.inp","r",stdin);
freopen("eva.out","w",stdout);
fast;
cin>>n>>k;
for (int i=1;i<=k;i++) cin>>b[i]
;
cin>>m;
for (int i=1;i<=m;i++)
{
int u,v,c;
cin>>u>>v>>c;
a[u]
.push_back(ii(v,c));
a[v]
.push_back(ii(u,c));
}
for(int i=1;i<=n;i++) dx[i]
=oo;
for (int i=1;i<=k;i++)
{
dij(b[i]
);
for (int j=1;j<=n;j++) dx[j] =min(dx[j] ,d[j]
);
}
for (int i=1;i<=n;i++) cout<<dx[i]
<< " ";
}
Bài 4
#include <bits/stdc++.h>
//#define ff first;
//#define ss second;
#define fast ios::sync_with_stdio(0)
using namespace std;
typedef pair<int,int> II;
typedef pair <int,II> III;
III a[1000005]
;
II p[1005] [1005]
;
int dem=0,m,n,k;
int b[1000006] ,gt[1003] [1003]
;
int kq[1000006]
,res=0;
int d[4]
={0,0,-1,1};
int c[4]
={-1,1,0,0};
II findset(int x,int y)
{
if (p[x] [y]
==II(0,0)) return II(x,y);
else p[x] [y] =findset(p[x] [y] .first,p[x] [y]
.second);
return p[x] [y]
;
}
void unio(II u,II v)
{
II pu=findset(u.first,u.second);
II pv=findset(v.first,v.second);
if (pu!=pv) p[pu.first] [pu.second]
=pv;
}
int main()
{
freopen("land.inp","r",stdin);
freopen("land.out","w",stdout);
fast;
cin>>m>>n;
for (int i=0;i<=m+1;i++)
for (int j=0;j<=n+1;j++)
p[i] [j]
=II(0,0);
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++){
int x; cin>>x; gt[i] [j]
=x;
++dem; a[dem]
=III(x,II(i,j));
}
sort(a+1,a+1+dem);
//for (int i=dem;i>0;i--) cerr<<a[i]
.first<<" ";
cin>>k;
for (int i=1;i<=k;i++) cin>>b[i]
;
int tg=dem;
for (int i=k;i>0;i--){
while (tg>0 && a[tg] .first>b[i]
){
++res;
int ux=a[tg]
.second.first;
int uy=a[tg]
.second.second;
for (int t=0;t<4;t++){
int vx=ux+d[t] ;int vy=uy+c[t]
;
if(gt[vx] [vy] >b[i]
)
if (findset(ux,uy)!=findset(vx,vy)){
--res; unio(a[tg]
.second, II(vx,vy));
}
}
--tg;
}
kq[i]
=res;
}
for (int i=1;i<=k;i++)cout<<kq[i]
<<" ";
}
