Tiêu đề olp mien trung - hue ict.docx ✅

1. 23-24 mttn kc – chung kết Câu 1. TONG1 Tổng 1 Alice có một bảng số kích thước m x n, các hàng được đánh số từ 1 đến m từ trên xuống dưới, các cột được đánh số từ 1 đến n từ trái sang phải. Ô nằm giao giữa hàng i (1 ≤ l ≤ m) và cột j (1 ≤ j ≤ n) chứa số a ij Một ô được gọi là ô trống nếu ô đó có đúng bốn ô kể cạnh, các ô còn lại gọi là ô biên. Alice muốn tỉnh tổng các số ở ô biên. Yêu cầu: Hãy lập trình giúp Alice tỉnh tổng các số ở ô biên. Dữ liệu: Vào từ thiết bị vào chuẩn theo khuôn dạng:  Dòng đầu chứa hai số nguyên dương m, n (3 ≤ m, n ≤ 10)  Dòng thứ i (1 ≤ i ≤ m) trong m dòng tiếp theo chứa n số nguyên a i1 , a i2 , … , a in . Các số có trị tuyệt đối không vượt quá 100. Kết quả: Ghi ra thiết bị ra chuẩn một dòng chứa một số là tổng các các số ở ô biên. Ví dụ: Input Output Giải thích 3 3 1 1 1 1 5 1 1 1 1 8 giải Lời giải: Ta tiến hành duyệt toàn bộ mảng, với những ô nằm ở ngoài biên, ta tính tổng cộng các ô đó lại. Code: #include <bits/stdc++.h> using namespace std; int a[1000][1000]; int main(){ int m,n; cin >> m >> n; long long sum = 0; for(int i=1;i<=m;i++){ for(int j=1;j<=n;j++) { cin >> a[i][j]; if(i == 1 || j == 1 || i == m || j == n) sum += a[i][j]; } } cout << sum << endl; return 0; } Câu 2. PHOIHOP Phối hợp (16/20 test) Nhóm n người bạn, các bạn có số hiệu từ 1 đến n. Với hai bạn có số hiệu a và b, khi cũng làm việc với nhau, độ phối hợp là f(a, b), giá trị này được tính bằng tổng các số nguyên dương vừa là ước của a vừa là ước của b. Yêu cầu: Hãy tính tổng độ phối hợp của tất cả các cặp bạn trong nhóm, cụ thể cần tính giá trị
Input: Vào từ thiết bị vào chuẩn gồm một số nguyên dương n. Output: Ghi ra thiết bị ra chuẩn một dòng chứa một số là phần dư của kết quả tính được chia cho () Ràng buộc:  Subtask 1 (30%): n ≤ 10 2  Subtask 2 (30%): n ≤ 10 3  Subtask 3 (20%): n ≤ 10 6  Subtask 4 (20%): n ≤ 10 14 Ví dụ: Input Output Giải thích 4 8 f(1,2) = 1; f(1,3) = 1; f(1,4) = 1; f(2,3) = 1; f(2,4) = 3; f(3,4) = 1 Câu 3. CHUPANH Chụp ảnh Một nhóm có n người bạn, các bạn được đánh số hiệu từ 1 đến n. Mọi người dự định tất cả đứng thành một hàng ngang để cùng nhau chụp ảnh. Đánh số n vị trí đứng từ trái sang phải bắt đầu từ 1 đến n. Với một số nguyên dương k, khi xếp hàng ai cũng mong muốn chênh lệch giữa số hiệu của mình với vị trí đứng không vượt quá k Yêu cầu: Cho hai số nguyên dương n, k, hãy đếm số cách xếp n người vào một hàng ngang gồm n vị trí để chụp ảnh sao cho người có số hiệu i (1 ≤ i ≤ n) xếp vào vị trí j (1 ≤ j ≤ n) thì |i – j| ≤ k Input: gồm hai số nguyên dương n, k (n ≤ ; k < 5) Kết quả: Ghi ra thiết bị ra chuẩn một dòng chứa một số là phần dư của kết quả tính được chia dư cho () Ràng buộc:  Subtask 1 (25%): n ≤ 8  Subtask 2 (25%): n ≤ 10 5 ; k = 1;  Subtask 3 (25%): n ≤ 10 5  Subtask 4 (15%): k < 3  Subtask 5 (10%): Không có ràng buộc gì thêm. Ví dụ: Input Output Giải thích 3 1 3 3 2 6 giải, dp bitmask Sử dụng quy hoạch động trạng thái, mỗi một vị trí i ta coi i là trung tâm và xét trạng thái của k vị trí bên phải và k vị trí bên trái i, cứ vậy mỗi lần chuyển giao vị trí của i lên i+1 ta chỉ cần dịch k*2+1 bit qua phải 1 lần. Code: #include <bits/stdc++.h>
using namespace std; struct str{ int a, b; }; const long long MOD = 1e9+7; int n, T, m, f[2][2050]; string sp = " "; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> m >> n; int N = (1<<((n<<1)+1))-1; for(int i = n; i <= (n<<1); i++) f[1][(1<<i)] = 1; for(int i = 1; i <= m; i++){ for(int j = 1; j <= N; j++) f[(i+1)&1][j] = 0; for(int j = 1; j <= N; j++){ for(int p = max(n-i,0); p <= (n<<1); p++){ if(!((j>>(p+1))&1)) { f[(i+1)&1][(j>>1)|(1<<p)] = (f[i&1][j] + f[(i+1)&1][(j>>1)|(1<<p)])%MOD; } } } } cout << f[m&1][(1<<(n+1))-1]; return 0; } Câu 4. CHONNHOM Chọn nhóm Một nhóm có n người bạn, các bạn được đánh số hiệu từ 1 đến n đứng thành một hàng ngang để cùng nhau chụp ảnh. Vị trí thứ i (1 ≤ i ≤ n) là người p i (1 ≤ p i ≤ n) đứng. Sau bức ảnh chụp chung cả n người, một số bạn muốn chụp chung cùng nhau. Cụ thể, các bạn đứng từ vị trị L đến vị trí R (1 ≤ L ≤ R ≤ n) giữ nguyên vị trí, các bạn từ 1 đến (L - 1) và các bạn đứng từ (R + 1) đến n rời khỏi hàng. Một cách chọn (L, R) được gọi là đẹp nếu tập số hiệu của các bạn đứng từ vị trí L đến vị trí R là một tập gồm số hiệu liên tiếp nhau. Ví dụ, với 5 bạn đứng lần lượt như sau: 1, 5, 3, 4, 2, khi đó cách chọn (L, R) bằng (1, 5), (2, 4), (2, 5), (3, 4), (3, 5) là các cách chọn đẹp, Yêu cầu: Cho dãy số nguyên dương p 1 , p 2 ,..., p n , hãy đếm số cách chọn (L, R) đẹp. Dữ liệu: Vào từ thiết bị vào chuẩn có khuôn dạng:  Dòng đầu chứa số nguyên dương n (n ≤ 3 * 10 5 ) ;  Dòng thứ hai chứa n số nguyên dương p 1 , p 2 ,...,p n (là một hoán vị của 1, 2 ,..., n)