Đề thi HSG Tin 12 – Bảng B – Năm học 2020 – 2021 – Code mẫu viết bằng C++

Đề thi HSG Tin 12 – Bảng B – Năm học 2020 – 2021

TỔNG QUAN ĐỀ THI

Lưu ý:

– Dấu * được thay thế bởi PAS hoặc CPP của ngôn ngữ lập trình tương ứng là Pascal hoặc C++.

– Thí sinh bắt buộc phải đặt tên file chương trình, file dữ liệu như trên.

– Khi hết thời gian làm bài, tại máy tính được sử dụng để làm bài thi, thí sinh tạo một thư mục với tên là số báo danh của mình và đặt các file bài làm (file chương trình .CPP hoặc .PAS) vào thư mục vừa tạo. Sau đó tiến hành ghi nội dung thư mục này vào đĩa CD dưới sự giám sát và hướng dẫn của Cán bộ coi thi và sự chứng kiến của một thí sinh nào đó tại phòng thi.

Bài 1 (4.0 điểm): DÃY SỐ

Cho số nguyên dương N, dãy A gồm N số nguyên dương: A₁, A₂, …, A_N và số nguyên dương X. Bạn hãy viết chương trình đưa ra số lượng cặp (i, j) thỏa mãn điều kiện:

• 1 ≤ i ≤ j ≤ N;
• A_i + A_j² = X;

Dữ liệu: Vào từ file văn bản DAYSO.INP gồm hai dòng

• Dòng đầu gồm 2 số nguyên dương N và X(1 ≤ N ≤ 10⁵,1 ≤ X ≤ 10⁹).
• Dòng thứ hai gồm N số nguyên dương: A₁, A₂, …, A_N (A_i ≤ 10⁴, i=1→N).

Kết quả: Ghi ra file văn bản DAYSO.OUT gồm một số nguyên duy nhất là số lượng cặp (i, j) thỏa mãn điều kiện đã nêu trên.

Ví dụ:

Bài 2 (4.0 điểm): TẶNG QUÀ

Ở một ngôi làng nọ, ông già Noel muốn tặng quà cho các cháu trong ngôi làng của mình. Một hôm ông mời các cháu tới một ngôi trường trong làng để tặng quà. Trong buổi tặng quà đó có N cháu. Ông già Noel đã đi đến từng cháu hỏi về tuổi hoặc là hỏi về xếp loại hạnh kiểm cuối năm của cháu đó. Sau đó ông ra ngoài để lấy quà vào tặng, vì lớn tuổi nên khi ra ngoài lấy quà thì ông lại quên số lượng các cháu cần tặng quà. Ông đã quyết định quay trở lại và hỏi một lần nữa, nhưng vì không muốn làm phiền mọi người nên ông muốn số lượng các cháu cần hỏi là ít nhất.

Bạn hãy tính xem ông già Noel cần hỏi ít nhất bao nhiêu cháu để biết chắc chắn cháu nào được nhận quà. Biết rằng những cháu nhận quà là những cháu có tuổi nhỏ hơn 15 tuổi hoặc có xếp loại hạnh kiểm cuối năm là TỐT (TOT), KHÁ (KHA).

Giả thiết rằng các cháu đều nói thật và đều trả lời duy nhất một câu hỏi về tuổi hoặc hạnh kiểm.

Dữ liệu: Vào từ file văn bản TANGQUA.INP gồm

• Dòng thứ nhất chứa số nguyên dương N (1 ≤ N ≤ 100),
• N dòng tiếp theo, mỗi dòng miêu tả thông tin trả lời của các cháu khi ông già Noel hỏi. Dòng thứ i là tuổi hoặc xếp loại hạnh kiểm của cháu thứ i (là một xâu chứa các kí tự Latinh in hoa có tối đa 100 kí tự).

Kết quả: Ghi ra file văn bản TANGQUA.OUT gồm một dòng duy nhất là số lượng cháu mà ông già Noel cần hỏi.

Ví dụ:

+ Ràng buộc:Không có ràng buộc gì thêm

Bài 3 (6 điểm): CÁCH XẾP

Kỳ thi chọn học sinh giỏi Tin học đang tới gần, địa điểm tổ chức thi là tại sân trường. Trường THPT A đang tìm cách sắp xếp chỗ ngồi phù hợp cho các thí sinh sao cho các thí sinh không thể gian lận để Kỳ thi diễn ra thật công bằng. Trường THPT A đã giao cho Thầy An tìm ra giải pháp sắp xếp chỗ ngồi phù hợp cho các thí sinh trong Kỳ thi. Vừa nghe yêu cầu, Thầy An liền nghĩ ra một cách xếp thú vị:

– Sân trường được chia thành một lưới ô vuông có kích thước là N x M (N hàng, M cột), mỗi thí sinh được xếp ngồi trên một ô trong lưới, mỗi ô chỉ có nhiều nhất một học sinh. Ô ở hàng i, cột j được gọi là ô (i, j).

– Mỗi thí sinh chỉ được ngồi quay mặt về một trong 4 hướng: Đông, Tây, Nam, Bắc.

– Để việc gian lận trao đổi bài với nhau là không xảy ra, nếu có hai thí sinh ngồi cùng hàng, tức là nếu có hai thí sinh ở vị trí (i, j₁) và (i, j₂)(1 ≤ i ≤ N; 1 ≤ j₁ < j₂ ≤ M) thì thí sinh ngồi ở vị trí (i, j₁) phải quay mặt về hướng Tây thì thí sinh còn phải quay mặt về hướng Đông.

– Tương tự, nếu có hai thí sinh ngồi cùng một cột, thì thí sinh ngồi ở hàng nhỏ hơn phải quay mặt về hướng Bắc và thí sinh còn lại phải quay mặt về hướng Nam.

Dù là cách sắp xếp không phải là tối ưu nhất, nhưng dù sao nó cũng là một cách xếp độc đáo và mang tính công bằng cao. Thầy An tự hỏi không biết có bao nhiêu cách để xếp ít nhất một thí sinh lên sân trường với cách sắp xếp thú vị trên.

Bạn hãy giúp Thầy An tính ra số cách xếp như trên.

Dữ liệu: Vào từ file văn bản CACHXEP.INP gồm một dòng duy nhất chứa 2 số nguyên dương N, M là số dòng và cột của lưới ô vuông.

Kết quả: Ghi ra file văn bản CACHXEP.OUT gồm một số duy nhất là phần dư của số lượng cách xếp theo Thầy An khi chia cho 10⁹+7.

Ví dụ:

Giải thích: Với bộ INPUT 1

Theo 4 hướng Đông, Tây, Nam, Bắc và sân trường có kích thước 2 x 1, ta có thể xếp một hoặc hai thí sinh như hình bên, tổng cộng có 9 cách xếp khác nhau.

+ Ràng buộc:

• Có 50% số điểm có N, M ≤
• Có 50% số điểm có N, M ≤

Bài 4 (6 điểm): ĐỒ THỊ CON

Hệ thống giao thông của thành phố ALPHA là một đồ thị vô hướng, liên thông và không có chu trình. Trong thành phố có N điểm du lịch được đánh số từ 1 đến N. Mỗi điểm du lịch trong thành phố được gán một giá trị nhất định, giá trị này được gọi là chất lượng du lịch của điểm đó. Bên cạnh đó giữa hai điểm du lịch bất kì trong thành phố luôn tồn tại một đường đi (trực tiếp hoặc gián tiếp) và đường đi này là duy nhất.

BETA là một du khách mới đặt chân đến thành phố ALPHA. BETA rất hứng thú với thành phố này và đặt cho mình một trong hai thử thách sau:

– Đánh giá lại chất lượng du lịch của một số điểm.

– Chọn một giá trị  x bất kì và tìm một đồ thị con (một đồ thị liên thông mà các đỉnh và cạnh của đồ thị này được trích ra từ đồ thị ban đầu) có ít điểm du lịch nhất và chứa tất cả các điểm có chất lượng du lịchx.

Bạn hãy giúp BETA hoàn thành thử thách.

Dữ liệu: Vào từ file văn bản DOTHICON.INP gồm:

• Dòng đầu tiên chứa số nguyên dương N là số điểm du lịch của thành phố ALPHA(2 ≤ N ≤ 10⁵).
• N – 1 dòng tiếp theo, mỗi dòng chứa hai số nguyên dương i, j thể hiện một cạnh (i, j) trên đồ thị.
• Dòng tiếp theo chứa N số nguyên dương V₁, V₂, … V_N(1 ≤ V_i ≤ 10⁵, i=1→N) với V_i là chất lượng du lịch của điểm i.
• Dòng tiếp theo chứa số nguyên dương M là số truy vấn (1 ≤ M ≤ 10⁵).
• M dòng tiếp theo, mỗi dòng có một trong hai dạng sau:
• U i  x
• Q x

(i=1→N, 1 ≤ x ≤ 10⁵)

Với truy vấn U  i  x, BETA sẽ đánh giá lại chất lượng du lịch của điểm i là x. Còn với truy vấn Q x,BETA muốn biết số lượng cạnh trong đồ thị con có ít điểm du lịch nhất và chứa tất cả các điểm có chất lượng du lịch x.

Kết quả: Ghi ra file văn bản DOTHICON.OUT gồm những nội dung như sau:

Với mỗi truy vấn Q  x, ghi ra số lượng cạnh trong đồ thị con cần tìm. Nếu không tồn tại điểm nào có chất lượng du lịch x thì ghi ra -1.  (Mỗi giá trị ghi trên một dòng)

Ví dụ:

+ Ràng buộc:Không có ràng buộc gì thêm

———-HẾT———-

Code mẫu viết bằng C++ – Đề thi HSG Tin 12 – Bảng B – Năm học 2020 – 2021

Bài 1:

#include <bits/stdc++.h>
using namespace std;

#define N 100005

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    freopen("DAYSO.INP","r",stdin);
    freopen("DAYSO.OUT","w",stdout);
    int a[N] 


;
    long n,X;
    cin>>n>>X;
    for (long i=1; i<=n; i++) cin>>a[i] 
;
    long c[10005] 




;
    memset(c,sizeof(c),0);
    long ans=0;
    for (long j=1; j<=n; j++)
    {
        c[a[j] 
]++;
        long tmp=X-a[j] *a[j] 
;
        if (tmp>0&&tmp<10001) ans+=c[tmp] 




;

    }
    cout<<ans;
    return 0;
}

Bài 2:

[rml_read_more]

#include <bits/stdc++.h>;
using namespace std;
int n;
string hk[2] 
 = {"TOT", "KHA"};
string st[101] 





;
void doc_dl(){
    fstream fi;
    fi.open("TANGQUA.INP",ios::in);
    fi>>n;
    for(int i=0;i<n;i++)
        fi>>st[i] 






;
    fi.close();
}
//Chuyển xâu sang số đồng thời kiểm tra có phải là có phải xâu số ko?
int chuyenso(string s){
    int x=0;
    for (int i=0;i<s.length();i++){
        if('0'<=s[i] &&s[i] <='9') x=x*10+(s[i] 








-48);
        else return -1;
    }
    return x;
}
main(){
    int kq,dem=0;
    doc_dl();
    for(int i=0;i<n;i++){
        kq=chuyenso(st[i] 


);
        if (kq==-1){
            for(int j=0;j<11;j++)
                if(st[i] ==hk[j] 







) dem++;
        }
        else if(kq<15) dem++;
    }
    fstream fo;
    fo.open("TANGQUA.OUT",ios::out);
    fo<<dem;
    fo.close();
}

Bài 3

	
	
	

































#include <bits/stdc++.h>
#define fileinput "CACHXEP.INP"
#define fileoutput "CACHXEP.out"
#define int unsigned long long
using namespace std;
int n, m;
const long long oo = 1e9 + 7;
void input()
{
    fstream fi;
    fi.open(fileinput, ios :: in);
    fi >> n >> m;
    fi.close();
}
void QHD_process()
{
    vector<vector<long long> > F(n+1, vector<long long>(m+1));
    for (int i = 0; i <= n; i++) F[i] [0] 
 = 1;
    for (int j = 0; j <= m; j++) F[0] [j] 


 = 1;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++){
            F[i] [j]  += F[i - 1] [j]  % oo;//f[i] [j] =f[i] [j] 
+.....;
            if (F[i] [j]  >= oo) F[i] [j] 
 -= oo;
            F[i] [j]  += F[i - 1] [j - 1] 
 * 4 * j % oo;
            if (F[i] [j]  >= oo) F[i] [j] 

	 -= oo;
            if (i > 1){
            	F[i] [j]  += F[i-2] [j-1] 
	 * (i-1) * j % oo;
            	if (F[i] [j]  >= oo) F[i] [j] 
	

 -= oo;
        	}
            if (j > 1){
                F[i] [j]  += F[i-1] [j-2] 
 * ((j-1) * j/2) % oo;
                if (F[i] [j]  >= oo) F[i] [j] 




 -= oo;
            }
        }
    fstream fo;
    fo.open(fileoutput, ios :: out);
    fo << (F[n] [m] 
 - 1 + oo) % oo;
    //cout<< (F[n] [m] 






 - 1 + oo) % oo;
    fo.close();
}
main()
{
    input();
    QHD_process();
}

Bài 4

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 100005;
const int MAXC = 100005;

typedef pair<int, int> pii;

struct SparseTable {
private:
    vector<int> a;
    vector<vector<int>> b;

public:
    int getMin(int i, int j) {
        return (a[i]  < a[j] 








) ? i : j;
    }

    void init(vector<int> _a) {
        a = _a;
        int n = a.size(), k = log2(n);
        b.assign(k+1, vector<int>(n, 0));

        for(int j = 0; j < n; ++j)
            b[0] [j] 


 = j;
        for(int i = 1; i <= k; ++i)
            for(int j = 0; j <= n - (1<<i); ++j)
                b[i] [j]  = getMin(b[i-1] [j] , b[i-1] [j + (1<<(i-1))] 




);
    }

    int query(int l, int r) {
        int i = log2(r - l + 1);
        return getMin(b[i] [l] , b[i] [r - (1<<i) + 1] 



);
    }
};

int n, q, color[MAXN] , h[MAXN] , in[MAXN] , ans[MAXC] 
;
vector<int> t[MAXN] 
, vList, hList;
set<pii> vtx[MAXC] 



;
SparseTable table;

void dfs(int u, int par) {
    vList.push_back(u); hList.push_back(h[u] 
);
    in[u] 

 = vList.size() - 1;

    for(int v: t[u] 


) {
        if (v == par)
            continue;
        h[v]  = h[u] 

 + 1;
        dfs(v, u);
        vList.push_back(u); hList.push_back(h[u] 




);
    }
}

int LCA(int u, int v) {
    if (in[u]  > in[v] 

)
        swap(u, v);
    return vList[table.query(in[u] , in[v] 



)];
}

void insert(int u, int c) {
    auto it = vtx[c] .insert({in[u] 
, u}).first;
    int prv = (it == vtx[c] .begin()) ? vtx[c] 
.rbegin()->second : prev(it)->second;
    int nxt = (next(it) == vtx[c] .end()) ? vtx[c] 
.begin()->second : next(it)->second;
    ans[c]  -= h[LCA(prv, u)]  + h[LCA(u, nxt)]  - h[LCA(prv, nxt)] 
;
    ans[c]  += h[u] 



;
}

void erase(int u, int c) {
    auto it = vtx[c] .find({in[u] 
, u});
    int prv = (it == vtx[c] .begin()) ? vtx[c] 
.rbegin()->second : prev(it)->second;
    int nxt = (next(it) == vtx[c] .end()) ? vtx[c] 
.begin()->second : next(it)->second;
    ans[c]  += h[LCA(prv, u)]  + h[LCA(u, nxt)]  - h[LCA(prv, nxt)] 
;
    ans[c]  -= h[u] 

;

    vtx[c] 



.erase(it);
}

int query(int c) {
    return (vtx[c] .empty()) ? -1 : ans[c] 











;
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    freopen("DOTHICON.INP","r",stdin);
    freopen("DOTHICON.OUT","w",stdout);
    scanf("%d", &n);
    for(int i = 0; i < n-1; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        --u; --v;
        t[u] .push_back(v); t[v] 







.push_back(u);
    }

    dfs(0, -1);

    table.init(hList);

    for(int u = 0; u < n; ++u) {
        scanf("%d", &color[u] 
);
        insert(u, color[u] 




);
    }

    scanf("%d", &q);
    for(int i = 0; i < q; ++i) {
        char s[2] 


; int u, c;
        scanf("%s", s);

        if (s[0] 






 == 'Q') {
            scanf("%d", &c);
            printf("%d\n", query(c));
        } else {
            scanf("%d%d", &u, &c);
            --u;

            erase(u, color[u] 

);
            insert(u, c);
            color[u] 




 = c;
        }
    }

    return 0;
}