Hướng dẫn giải của [200 đề thầy Đức] Bài 193: Biến đổi dãy
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Được một thao tác: chọn đoạn ~[l, r]~ và cộng ~k > 0~ vào các phần tử của đoạn. Đặt ~d_i = b_i - a_i~. Đáp án YES khi mọi ~d_i~ không âm, các vị trí có ~d_i > 0~ liền nhau và có cùng giá trị, các vị trí còn lại bằng 0.
Sub 1: Vét cạn — ~O(n^3)~ với các giá trị ~k~, dùng khi ~n \le 30~
Nếu ~a = b~ thì YES. Ngược lại thử mọi đoạn ~[l, r]~ và mọi giá trị ~k~ lấy từ tập các hiệu dương ~d_i~ (vì ~k~ phải bằng ~d_i~ tại một vị trí trong đoạn). Cộng ~k~ vào đoạn rồi so với ~b~. Nếu chỉ nộp sub này: đúng 6/21 test.
Sub 2: Kiểm tra hiệu — ~O(n)~
Tính ~d_i~ trong ~O(n)~. Nếu có ~d_i < 0~ thì NO. Nếu không có ~d_i > 0~ thì YES. Ngược lại lấy đoạn từ vị trí ~d_i > 0~ đầu tiên đến cuối cùng và kiểm tra mọi ~d_i~ trong đoạn đều bằng nhau. Nếu chỉ nộp sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
main đọc ~T~ bộ dữ liệu. Với mỗi bộ, nếu ~n \le 30~ thì gọi sub1, ngược lại gọi sub2.
#include <bits/stdc++.h>
using namespace std;
int n;
long long a[100005], b[100005];
// Sub 1: vét cạn. Thử mọi đoạn [l, r] và mọi k dương (chỉ cần k là hiệu b - a của một vị trí),
// cộng k vào đoạn rồi so với b.
bool sub1() {
bool same = true;
for (int i = 1; i <= n; i++) if (a[i] != b[i]) same = false;
if (same) return true;
set<long long> ks;
for (int i = 1; i <= n; i++) if (b[i] - a[i] > 0) ks.insert(b[i] - a[i]);
for (int l = 1; l <= n; l++)
for (int r = l; r <= n; r++)
for (long long k : ks) {
bool good = true;
for (int i = 1; i <= n && good; i++) {
long long v = a[i] + (i >= l && i <= r ? k : 0);
if (v != b[i]) good = false;
}
if (good) return true;
}
return false;
}
// Sub 2: O(n). Hiệu d[i] = b[i] - a[i] phải không âm. Các vị trí d > 0 phải liền nhau
// và có cùng giá trị k; mọi vị trí còn lại phải bằng 0.
bool sub2() {
vector<long long> d(n + 1);
for (int i = 1; i <= n; i++) {
d[i] = b[i] - a[i];
if (d[i] < 0) return false;
}
int l = 0, r = 0;
for (int i = 1; i <= n; i++)
if (d[i] > 0) {
if (!l) l = i;
r = i;
}
if (!l) return true; // không cần thao tác nào
for (int i = l; i <= r; i++)
if (d[i] != d[l]) return false;
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
bool res = (n <= 30) ? sub1() : sub2();
printf("%s\n", res ? "YES" : "NO");
}
return 0;
}
Bình luận