Đề luyện thi HSG Tin 11 – Hà Giang – Kèm code C++

Đề luyện thi HSG Tin 11 – Hà Giang – Kèm code C++

Đề luyện thi HSG Tin 11 – Hà Giang

Dấu * tương ứng với đuôi .PAS hoặc .CPP khi học sinh sử dụng ngôn ngữ lập trình PASCAL hoặc C++.

Bài 1 (6,0 điểm): Chọn đồ chơi

Bạn Bi rất yêu thích việc mua sắm những đồ chơi khoa học viễn tưởng hiếm và đắt. Cậu ấy giữ chúng theo một dãy theo thứ tự ngày mua và để trong một cái tủ. Vì vậy, bạn Bo sẽ không bao giờ lấy được đồ chơi của cậu ấy. Nhưng vì một lần không may mắn, Bi đã thua Bo trong một vụ cá cược. Và Bo đã yêu cầu Bi chia sẻ đồ chơi. Bởi vì Bi không muốn mất nhiều tiền nên cậu ấy đã quyết định dựa trên một chiến lược để giảm thiểu sự mất mát xuống thấp nhất.

Bi bắt đầu chọn từ đồ chơi đầu tiên ở trong tủ, sẽ lấy một số đồ chơi, gọi là X đồ chơi. Bo sau đó sẽ chọn X đồ chơi (chú ý là Bo sẽ chọn số đồ chơi bằng với Bi, trừ khi số đồ chơi còn lại nhỏ hơn X). Việc này sẽ tiếp tục cho đến khi không còn lại đồ chơi nào nữa.

Bạn được đưa cho một dãy của đồ chơi với giá của chúng. Hãy đưa ra số tiền lớn nhất Bi có thể giữ lại ứng với số đồ chơi mà Bi chọn. Bi chỉ có thể chọn 1, 2 hay 3 đồ chơi (X có giá trị 1, 2 hay 3)

Dữ liệu: Vào từ tệp TOYS.INP có cấu trúc như sau:

+ Dòng đầu tiên ghi số nguyên dương N là số đồ chơi.

+ N dòng tiếp theo ghi N số nguyên dương là giá tiền của các đồ chơi.

Các số trên một dòng ghi cách nhau bởi một dấu cách.

Kết quả: Ghi ra tệp TOYS.OUT một số nguyên duy nhất là tổng số tiền lớn nhất của các đồ chơi mà bạn Bi chọn

Ràng buộc:

1 ≤ T ≤ 10

1 ≤  N ≤ 100000

1 ≤ Giá của đồ chơi ≤ 1000000

Ví dụ:

Giải thích:

• Ở test case 1: Bi chọn 3 đồ chơi trong lần đầu tiên của anh ta là: 5, 4, 3. Do đó, Bo không còn lựa chọn nào khác nên phải chọn 2. Khi đó, Bi thu được tổng số tiền lớn nhất là 5 + 4 + 3 = 12
• Ở test case 2: Bi chọn 10 và 8. Sau đó, Bo chọn 7 và 11. Cuối cùng Bi chọn 15 và 20. Do đó, số tiền lớn nhất mà Bi thu được là: 10 + 8 + 15 + 20 = 53

Subtask 1 (30%) : 1 ≤ N ≤ 10², 1 ≤ giá tiền các đồ chơi  ≤ 10³

Subtask 2 (30%) : 10² < N ≤ 10³, 10³ < giá tiền các đồ chơi ≤ 10⁵

Subtask 3 (40%) : 10³ < N ≤ 10⁵, 10⁵ < giá tiền các đồ chơi ≤ 10⁷

Bài 2 (7,0 điểm): Hệ thống nước

Nhà bác Sơn ở huyện Mộc Châu – Sơn La có một trang trại nuôi bò sữa lớn. Để cung cấp đủ thức ăn cho bò, bác phải trồng rất nhiều cỏ. Mùa hè năm nay, bác đã quyết định làm một hệ thống tưới nước cho N (1 ≤N≤ 300) đồng cỏ của mình. Để thuận tiện, các đồng cỏ được đánh số từ 1 đến N. Để tưới nước cho một đồng cỏ, bác có thể chọn 2 cách: 1 là đào ở đồng cỏ đó 1 cái giếng hoặc lắp ống nối dẫn nước từ những đồng cỏ trước đó đã có nước tưới.

Để đào một cái giếng ở đồng cỏ i cần 1 số tiền là W_i (1 ≤  W_i≤ 100.000). Lắp ống dẫn nước nối 2 đồng cỏ i và j cần 1 số tiền là P_ij (1 ≤ P_ij≤ 100.000; P_ij = P_ji; P_ii  = 0).

Các em hãy tính xem bác Sơn phải chi ít nhất bao nhiêu tiền để tất cả các đồng cỏ đều có nước.

Dữ liệu: Vào từ tệp WATER.INP có cấu trúc như sau:

+ Dòng đầu tiên ghi số nguyên dương N là số đồng cỏ.

+ Các dòng: 2..N+1: Dòng i+1 chứa một số nguyên duy nhất W_i;

+ Các dòng N+2..2N+1: Dòng N+1+i chứa N số nguyên cách nhau bởi dấu cách; số thứ j là P_ij

Kết quả: Ghi ra tệp WATER.OUT một số nguyên duy nhất là chi phí tối thiểu để cung cấp nước cho tất cả các đồng cỏ.

Giải thích:

Có 4 đồng cỏ. Mất 5 tiền để đào 1 cái giếng ở đồng cỏ 1, 4 tiền để đào ở đồng cỏ 2, 3 và 3 tiền để đào ở đồng cỏ 4. Các ống dẫn nước tốn 2, 3, và 4 tiền tùy thuộc vào nó nối đồng cỏ nào với nhau.

Bác Sơn có thể đào 1 cái giếng ở đồng cỏ thứ 4 và lắp ống dẫn nối đồng cỏ 1 với tất cả 3 đồng cỏ còn lại, chi phí tổng cộng là 3 + 2 + 2 + 2 = 9.

Bài 3 (7,0 điểm): Mạng máy tính

Có N máy tính đánh số từ 1 đến N và M dây cáp mạng, giữa 2 máy tính có thể có một hoặc nhiều đường dây cáp mạng nối chúng, không có cáp mạng nối một máy với chính nó. Hai máy tính có thể truyền dữ liệu cho nhau nếu có đường cáp nối trực tiếp giữa chúng hoặc truyền qua một số máy trung gian.

Một tập S các máy tính được gọi là hệ thống an toàn nếu dù một máy tính bất kỳ bị tấn công, thì trong số những máy tính còn lại, những máy tính thuộc tập S vẫn có thể truyền được dữ liệu cho nhau. Xác định số lượng lớn nhất có thể các máy tính của tập S.

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

+ Dòng 1 chứa 2 số nguyên N, M (1≤ N≤ 3000, 0 ≤ M  ≤ 10000)

+ M dòng tiếp theo ghi thông tin về các dây cáp mạng, gồm 2 chỉ số của 2 máy được dây đó nối trực tiếp.

Kết quả: Ghi ra tệp văn bản NETWORK.OUT một số nguyên duy nhất là số lượng máy tính lớn nhất tìm được.

Ví dụ:

 Code tham khảo Đề luyện thi HSG Tin 11 – Hà Giang

Bài 1:

#include <iostream>
#include <fstream>
using namespace std;

const int MAX = 1000010;

int N;                      // Số đồ chơi
int Price[MAX] 
;             // Giá của các đồ chơi
long long MaxMoney[MAX] ;    // MaxMoney[i] 













 là số tiền lớn nhất
                            // khi Leonard chọn từ đồ chơi thứ i.
int main(int argc, char** argv)
{
    freopen("TOYS.INP","r",stdin);
    freopen("TOYS.OUT","w",stdout);
    int T, test_case;
    ios::sync_with_stdio(false);
    //freopen("input.txt", "r", stdin);

    // Nhập đầu vào
        cin >> N;
        for(int i = 1; i <= N; i++)
        {
            cin >> Price[i] 
;
            MaxMoney[i] 



 = 0;
        }

        // Trường hợp cơ sở
        MaxMoney[N]  = Price[N] 

;
        for(int i = N + 1; i <= N + 5; i++)
            Price[i]  = MaxMoney[i] 




 = 0;

        for(int i = N-1; i >= 1; i--)
        {
            // Nếu chọn 1 đồ chơi
            MaxMoney[i]  = (long long)Price[i]  + MaxMoney[i + 2] 


;

            // Nếu chọn 2 đồ chơi
            long long t = (long long)(Price[i]  + Price[i + 1] ) + MaxMoney[i + 4] 
;
            if(t > MaxMoney[i] ) MaxMoney[i] 


 = t;

            // Nếu chọn 3 đồ chơi
            t = (long long)(Price[i]  + Price[i + 1]  + Price[i + 2] ) +  MaxMoney[i + 6] 
;
            if(t > MaxMoney[i] ) MaxMoney[i] 

 = t;
        }
        cout << MaxMoney[1] 


 << endl;

    return 0;//Your program should return 0 on normal termination.
}

Bài 2:

#include <iostream>
#include <fstream>
using namespace std;

long long c[301] [301] 
;
long long d[301] 
;
bool b[301] 








;

int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    freopen("WATER.INP","r",stdin);
    freopen("WATER.OUT","w",stdout);
    int n; cin >> n;
    for (int i=1; i<=n; i++) {
        int x; cin >> x;
        c[i] [0]  = c[0] [i] 


 = x;
    }
    for (int i=1; i<=n; i++) for (int j=1; j<=n; j++) {
        cin >> c[i] [j] 


;
    }

    for (int i=1; i<=n; i++) d[i] 


 = 1e9;
    for (int z=n; z--;) {
        int u = -1;
        for (int i=0; i<=n; i++) if (!b[i] 
) {
            if (u<0 || d[u]  > d[i] 


) u = i;
        }
        if (u < 0) break;
        b[u] 
 = true;
        for (int i=0; i<=n; i++) if (!b[i] 
) {
            d[i]  = min(d[i] , c[i] [u] 




);
        }
    }

    int res = 0;
    for (int i=1; i<=n; i++) res += d[i] 


;
    cout << res;
    return 0;
}

Bài 3:

#include <bits/stdc++.h>
#define maxn 30001
#define maxm 100005
#define fs first
#define sc second
using namespace std;
typedef pair<int,int> II;
    int n,m,deg[maxn] 
;
    vector<int> g[maxn] 
;
    II ed[maxm] 
;
    int s[maxn] ,cur[maxn] ,cl[maxn] ,pe[maxn] ,pre[maxn] ,num[maxn] ,low[maxn] ,x[maxn] 
,id=0;
    int sl[maxn] 



;
void dfs(int xp)
{
    int sn=0;
    s[++sn] =xp; cl[xp] 
=1;
    pe[xp] =pre[xp] 
=0;
    num[xp] =low[xp] 
=++id;
    x[id] 


=xp;
    while(sn)
    {
        int u=s[sn] 
;
        if(cur[u] <deg[u] 

)
        {
            int i=g[u] [cur[u] 
++];
            if(abs(i)!=pe[u] 

)
            {
                int v=(i>0)?ed[i] .sc:ed[-i] 
.fs;
                if(cl[v] 

==0)
                {
                    cl[v] =1; s[++sn] 
=v;
                    pe[v] =abs(i); pre[v] 
=u;
                    num[v] =low[v] 
=++id;
                    x[id] 
=v;
                } else low[u] =min(low[u] ,num[v] 



);
            }
        } else
        {
            int w=pre[u] 
;
            if(w) low[w] =min(low[w] ,low[u] 














);
            --sn;
        }
    }
}
int main()
{
    freopen("NETWORK.INP","r",stdin);
    freopen("NETWORK.OUT","w",stdout);
    ios::sync_with_stdio(0);
    cin>>n>>m;
    for(int i=1; i<=m; i++)
    {
        int u,v;
        cin>>u>>v;
        ed[i] 
=II(u,v);
        deg[u] ++; g[u] 
.push_back(i);
        deg[v] ++; g[v] 


.push_back(-i);
    }
    for(int i=1; i<=n; i++)
        if(cl[i] 



==0) dfs(i);
    int ds=1;
    for(int j=n; j>=1; j--)
    {
        int u=x[j] 
;
        for(int o=0; o<deg[u] 

; o++)
        {
            int i=g[u] [o] 
;
            int v=(i>0)? ed[i] .sc:ed[-i] 
.fs;
            if(abs(i)!=pe[v] 
) continue;
            if(sl[v] 
==0) continue;
            if(low[v] ==num[u] 

)
            {
                ds=max(ds,sl[v] 
+1);
                sl[v] 


=0;
            }
            else
            if(low[v] >num[u] 

)
            {
                ds=max(ds,sl[v] 
+1);
                sl[v] 
=0;
            } else sl[u] +=sl[v] 

;
        }
        sl[u] 


++;
    }
    cout<<ds;
}