Hướng dẫn cho LQDOJ CUP 2022 - Round 6 - DYSLEXIA
Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.
Authors:
Subtask \(1\) (\(15\%\) số điểm): \(n \leq 300\).
Tutorial
Dùng hai vòng lặp để duyệt qua các xâu con của \(S\). Sau đó lại lặp thêm một lần nữa để tính trọng số
Độ phức tạp: \(\mathcal{O}(n^3)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10000005;
const int MOD = 1e9 + 7;
const char B64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
int n;
string xxx;
char s[MAX_N];
int position[256];
void initBase64() {
for (int i = 0; i < 64; i++) {
position[(int)B64[i]] = i;
}
}
void b64Conversion(const string &str) {
int ptr = 1;
for (char c : str) {
int x = position[(int)c];
for (int i = 0; i < 6; i++) {
s[ptr++] = x & 1;
x >>= 1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("DYSLEXIA.inp", "r", stdin);
freopen("DYSLEXIA.out", "w", stdout);
cin >> n >> xxx;
initBase64();
b64Conversion(xxx);
long long answer = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
int x = 0, y = 0;
for (int k = i; k <= j; k++) {
x += s[k] == 0, y += s[k] == 1;
}
if (x > 0 && y > 0) {
answer += x * y;
} else {
answer += x * x + y * y;
}
}
}
cout << answer % MOD;
return 0;
}
Subtask \(2\) (\(10\%\) số điểm): \(n \leq 5 \times 10^3\).
Tutorial
Việc chạy thêm vòng lặp thứ 3 để tính chi phí là hoàn toàn thừa thãi.
Nhận thấy trong vòng for biến \(r\), khi \(r\) tăng \(1\) đơn vị thì phần tử \(a_r\) được thêm vào, vì vậy chỉ cần tăng một trong hai biến đếm số lượng \(0, 1\) lên một đơn vị rôi tính lại.
Độ phức tạp: \(\mathcal{O}(n^2)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10000005;
const int MOD = 1e9 + 7;
const char B64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
int n;
string xxx;
char s[MAX_N];
int position[256];
void initBase64() {
for (int i = 0; i < 64; i++) {
position[(int)B64[i]] = i;
}
}
void b64Conversion(const string &str) {
int ptr = 1;
for (char c : str) {
int x = position[(int)c];
for (int i = 0; i < 6; i++) {
s[ptr++] = x & 1;
x >>= 1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("DYSLEXIA.inp", "r", stdin);
freopen("DYSLEXIA.out", "w", stdout);
cin >> n >> xxx;
initBase64();
b64Conversion(xxx);
long long answer = 0;
for (int i = 1; i <= n; i++) {
int x = 0, y = 0;
for (int j = i; j <= n; j++) {
x += s[j] == 0, y += s[j] == 1;
if (x > 0 && y > 0) {
answer += x * y;
} else {
answer += x * x + y * y;
}
}
}
cout << answer % MOD;
return 0;
}
Subtask \(3\) (\(10\%\) số điểm): \(n \leq 10^5\), toàn bộ các ký tự của \(S\) đều giống nhau.
Tutorial
Như vậy chi phí của đoạn con độ dài \(l\) sẽ là \(l^2\). Dễ suy luận được công thức sau: \(\sum_{l=1}^{n} l^2 \times (n-l+1)\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10000005;
const int MOD = 1e9 + 7;
const char B64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
int n;
string xxx;
char s[MAX_N];
int position[256];
void initBase64() {
for (int i = 0; i < 64; i++) {
position[(int)B64[i]] = i;
}
}
void b64Conversion(const string &str) {
int ptr = 1;
for (char c : str) {
int x = position[(int)c];
for (int i = 0; i < 6; i++) {
s[ptr++] = x & 1;
x >>= 1;
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("DYSLEXIA.inp", "r", stdin);
freopen("DYSLEXIA.out", "w", stdout);
cin >> n >> xxx;
initBase64();
b64Conversion(xxx);
long long answer = 0;
for (int i = 1; i <= n; i++){
answer += (long long)i * i * (n - i + 1);
}
cout << answer % MOD;
return 0;
}
Subtask \(4\) (\(15\%\) số điểm): \(n \leq 10^5\), tồn tại duy nhất một vị trí \(i\) sao cho \(S_i \neq S_{i + 1}\) (\(0 \le i < n-1\)).
Tutorial
Việc tính chi phí của mỗi xâu con trong một đoạn cùng "màu" (0/1) hoàn toàn giống subtask 3.
Ta chỉ quan tâm những đoạn con chứa hai loại kí tự khác nhau - nằm vắt ngang giữa 2 đoạn.
Nhận thấy, nếu xâu con bao gồm \(x\) kí tự cuối cùng của đoạn thứ nhất, và \(y\) kí tự đầu tiên của đoạn thứ hai thì trọng số hiển nhiên là \(xy\)
Do đó cần tính \(\sum_{x=1}^{A} \sum_{y=1}^{B} xy\) với \(A,B\) lần lượt là độ dài các đoạn.
Có \(\sum_{x=1}^{A} \sum_{y=1}^{B} xy = \sum_{x=1}^{A} x \times \frac{B(B+1)}{2} = \frac{A(A+1)}{2} \times \frac{B(B+1)}{2}\)
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10000005;
const int MOD = 1e9 + 7;
const char B64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
int n;
string xxx;
char s[MAX_N];
int position[256];
void initBase64() {
for (int i = 0; i < 64; i++) {
position[(int)B64[i]] = i;
}
}
void b64Conversion(const string &str) {
int ptr = 0;
for (char c : str) {
int x = position[(int)c];
for (int i = 0; i < 6; i++) {
s[ptr++] = x & 1;
x >>= 1;
}
}
}
long long f(int n) {
long long result = 0;
for (int i = 1; i <= n; i++) {
result += ((long long)i * i % MOD * (n - i + 1)) % MOD;
}
return result % MOD;
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("DYSLEXIA.inp", "r", stdin);
freopen("DYSLEXIA.out", "w", stdout);
cin >> n >> xxx;
initBase64();
b64Conversion(xxx);
for (int i = 0; i < n; i++) {
if (s[i] != s[0]) {
int a = i, b = n - a;
long long ans = f(a) + f(b);
ans += 1ll * (1ll * a * (a + 1) / 2 % MOD) * (1ll * b * (b + 1) / 2 % MOD);
cout << ans % MOD;
return 0;
}
}
cout << f(n);
return 0;
}
Subtask \(5\) (\(20\%\) số điểm): \(n \le 10^5\).
Subtask \(6\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.
Tutorial
Đầu tiên, ta cắt xâu \(S\) thành những đoạn liên tiếp cùng màu, mà độ dài mỗi đoạn là lớn nhất có thể (số đoạn cắt ra là ít nhất), tức hai đoạn kề nhau bất kì phải khác màu nhau.
Tính riêng trường hợp các xâu con chỉ có một loại kí tự trước.
Bây giờ, ta chỉ quan tâm các xâu con có đủ hai kí tự 0,1
Quan sát thấy \(xy = y + y + \dots + y\) (\(x\) số hạng như vậy). Do đó ta có thể phát biểu lại công thức như sau:
"Với mỗi xâu con có hai loại kí tự, với mỗi kí tự 0 xuất hiện trong xâu, ta cộng vào trọng số số lần xuất hiện của kí tự 1"
Từ đó việc tính có thể tách ra theo từng vị trí: Tại vị trí \(i\) có \(S[i] = '0'\), cần biết nó đã đóng góp bao nhiêu vào trọng số của các đoạn con?
Lượng đóng góp của \(S[i]\) chính bằng tổng (tần số của 1 trong xâu \(T\)) với mọi xâu con \(T\) chứa \(i\).
Đặt \(p[i]\) là số lượng kí tự '1' trong xâu con \(S[1..i]\).
Lượng cần tính bằng:
\(\sum_{j=0}^{i-1} \sum_{k=i}^{n} p[k] - p[j] = \sum_{j=0}^{i-1} \{-p[j]\times (n-i+1) + \sum_{k=i}^{n}p[k]\} = (n-i+1) \times -\sum_{j=0}^{i-1}p[j] + i\times\sum_{k=i}^{n} p[k]\)
Áp dụng mảng cộng dồn thêm một lần nữa, trên \(p\).
Đối với subtask 6, đáp án có thể vượt quá giá trị của kiểu dữ liệu long long, nên cần dùng một kiểu dữ liệu có thể lưu số lớn (tự cài, hoặc với C++ thì dùng int128).
Solution
#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 10000005;
const int MOD = 1000000007;
const char B64[65] = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
int n;
string xxx;
char s[MAX_N];
int position[256];
void initBase64() {
for (int i = 0; i < 64; i++) {
position[(int)B64[i]] = i;
}
}
void b64Conversion(const string &str) {
int ptr = 1;
for (char c : str) {
int x = position[(int)c];
for (int i = 0; i < 6; i++) {
s[ptr++] = x & 1;
x >>= 1;
}
}
}
long long sum[2][MAX_N];
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
freopen("DYSLEXIA.inp", "r", stdin);
freopen("DYSLEXIA.out", "w", stdout);
cin >> n >> xxx;
initBase64();
b64Conversion(xxx);
long long answer = 0;
long long cnt = 1;
s[n + 1] = -1;
for (int i = 2; i <= n + 1; i++) {
if (s[i] == s[i - 1]) {
cnt++;
} else {
for (long long x = 1; x <= cnt; x++) {
answer = (answer + x * x % MOD * (cnt - x + 1)) % MOD;
}
cnt = 1;
}
}
long long total[2] = {};
for (int i = 1; i <= n; i++) {
sum[0][i] = sum[0][i - 1] + (s[i] == 0);
sum[1][i] = sum[1][i - 1] + (s[i] == 1);
total[0] = (total[0] + sum[0][i]) % MOD;
total[1] = (total[1] + sum[1][i]) % MOD;
}
long long plus = 0, minus = 0;
for (int i = 1; i <= n; i++) {
plus = (plus + sum[0][i] * sum[1][i]) % MOD;
}
plus = plus * n % MOD;
for (int i = 1; i <= n; i++) {
minus = (minus + sum[0][i] * (total[1] - sum[1][i] + MOD)) % MOD;
}
answer = (answer + plus - minus + MOD) % MOD;
cout << answer;
return 0;
}
Bình luận