Bài 1
Chỉ giải thành công bài này. Qua việc mô phỏng các ví dụ và lập bảng cho tất cả các cặp [i,j], có thể dễ dàng nhận ra quy luật. Việc hiện thực hóa khá phức tạp, xem mã nguồn để hiểu rõ hơn.
Mã nguồn bài 1
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAX_SIZE = 5 * 1145140, MOD = 998244353;
int length, arr[MAX_SIZE], prefix_AC[MAX_SIZE], prefix_CA[MAX_SIZE];
char input_str[MAX_SIZE];
ll cumulative_sum[MAX_SIZE], count_arr[MAX_SIZE];
int main() {
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> (input_str + 1);
length = strlen(input_str + 1);
bool flag_A = false, flag_C = false;
for(int idx = 1; idx <= length; ++idx) {
arr[idx] = input_str[idx] - 'A' + 1;
prefix_AC[idx] = prefix_AC[idx - 1];
if(arr[idx] == 1) flag_A = true;
if(flag_A && arr[idx] == 3) flag_C = true;
if(flag_A && flag_C) {
prefix_AC[idx]++;
flag_A = flag_C = false;
}
}
flag_A = flag_C = false;
for(int idx = 1; idx <= length; ++idx) {
prefix_CA[idx] = prefix_CA[idx - 1];
if(arr[idx] == 3) flag_C = true;
if(flag_C && arr[idx] == 1) flag_A = true;
if(flag_A && flag_C) {
prefix_CA[idx]++;
flag_A = flag_C = false;
}
}
ll last_val = 0, total_count = 0;
for(int idx = length; idx >= 1; --idx) {
cumulative_sum[idx] = cumulative_sum[idx + 1];
if(arr[idx] != 2) {
if(last_val && last_val != arr[idx])
cumulative_sum[idx]++;
last_val = arr[idx];
}
}
ll result = 0, pointer = 1, deduction = 0;
for(int idx = 1; idx <= length; ++idx) {
++count_arr[cumulative_sum[idx]];
total_count += cumulative_sum[idx];
if(cumulative_sum[idx]) ++deduction;
}
for(int idx = length; idx >= 1; --idx) {
result += total_count;
result %= MOD;
if(arr[idx] != 2 && (prefix_AC[idx] != prefix_AC[idx - 1] ||
prefix_CA[idx] != prefix_CA[idx - 1])) {
total_count -= deduction;
deduction -= count_arr[pointer];
++pointer;
}
}
cout << result;
return 0;
}
Bài 2
Bài toán quy hoạch động trên đoạn. Ban đầu không nhận ra, nhưng sau khi phát hiện thì giải khá dễ dàng.
Vì là dạng vòng tròn nên cần phá vòng thành chuỗi thẳng, đồng thời cập nhật lại mối quan hệ chiến thắng. Gọi dp[i][j] biểu diễn khả năng i và j có thể đứng cạnh nhau hay không. Nếu đứng cạnh nhau thì coi như i thách thức j. Vì đã phá vòng nên không ảnh hưởng gì. Lặp qua các điểm k mà cả i và j đều có thể đến được, tức là dp[i][k] = dp[k][j] = 1. Nếu i có thể đánh bại k hoặc k không thể đánh bại j, thì dp[i][j] = 1.
Với mỗi i, nếu dp[i][i+n] = 1, thì i có thể là người chiến thắng cuối cùng.
Mã nguồn bài 2
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll MAX_N = 2 * 1145;
ll size, battle[MAX_N][MAX_N], reachable[MAX_N][MAX_N];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> size;
for(int row = 1; row <= size; ++row) {
for(int col = 1; col <= size; ++col) {
cin >> battle[row][col];
battle[row + size][col] = battle[row][col + size] =
battle[row + size][col + size] = battle[row][col];
}
}
for(int span = 2; span <= 2 * size; ++span) {
for(int start = 1; start <= 2 * size - span + 1; ++start) {
int end = start + span - 1;
if(span == 2) reachable[start][end] = 1;
for(int mid = start + 1; mid < end; ++mid) {
if(reachable[start][mid] && reachable[mid][end] &&
(battle[start][mid] || !battle[mid][end])) {
reachable[start][end] = 1;
}
}
}
}
for(int idx = 1; idx <= size; ++idx) {
if(reachable[idx][idx + size]) cout << idx << " ";
}
return 0;
}
Bài 3
Đây là bài tìm quy luật, đáng lẽ nên hoàn thành. Trước tiên, với các hàng và cột có thừa số bằng 0, giá trị tương ứng sẽ giống nhau và bằng 0. Sau đó, với mỗi hàng/cột, giá trị biến tương ứng chính là số lượng chữ số hàng chục khác nhau trong hàng/cột đó. Không có chứng minh cụ thể.
Mã nguồn bài 3
#include<bits/stdc++.h>
using namespace std;
#define ll int
const ll MAX_SIZE = 2 * 1145;
ll dimension, matrix_a[MAX_SIZE][MAX_SIZE], matrix_b[MAX_SIZE][MAX_SIZE],
output[MAX_SIZE], temp_num[MAX_SIZE];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> dimension;
for(int row = 0; row < dimension; ++row) {
output[row] = -1;
for(int col = 0; col < dimension; ++col) {
cin >> matrix_a[row][col] >> matrix_b[row][col];
}
}
for(int col = 0; col < dimension; ++col) {
bool identical = true;
for(int row = 0; row < dimension - 1; ++row) {
if(matrix_a[row][col] != matrix_a[row + 1][col] ||
matrix_b[row][col] != matrix_b[row + 1][col]) {
identical = false;
break;
}
}
if(identical) output[col] = 0;
}
for(int col = 0; col < dimension; ++col) {
ll unique_count = 0;
for(int row = 0; row < dimension; ++row) temp_num[row] = 0;
for(int row = 0; row < dimension; ++row) {
if(!temp_num[matrix_a[row][col]]) {
++unique_count;
temp_num[matrix_a[row][col]] = 1;
}
}
if(output[col] == -1) output[col] = unique_count;
}
for(int idx = 0; idx < dimension; ++idx) {
cout << output[idx] << " ";
}
return 0;
}
Bài 4
Không kịp hoàn thành bài này, tuy nhiên thuật toán tìm kiếm của tôi được hiện thực hóa rất kém hiệu quả...