Hướng dẫn giải của Bedao Regular Contest 11 - ABSTRING
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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.
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.
Tác giả: bedao
Có thể chứng minh rằng xâu cần tìm chắc chắn có dạng '~abababa...a~'. Vì vậy bài toán của ta đơn giản là tìm xâu con có dạng '~abababa...a~' dài nhất.
Để tìm được xâu như vậy thì ta sẽ xét từng vị trí trên xâu kí tự, giả sử đang xét đến vị trí ~i~, ta duyệt tìm vị trí ~j~ xa nhất sao cho xâu con từ ~i~ đến ~j~ vẫn thỏa mãn là xâu có dạng '~abababa...a~', cập nhật kết quả và ta sẽ nhảy ~i~ đến vị trí ~j~ đề không bị xét lại các xâu con của xâu từ ~i~ đến ~j~.
Độ phức tạp: ~O(n)~.
Code mẫu
/*#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma")*/ #include <bits/stdc++.h> #define for1(i,a,b) for (int i = a; i <= b; i++) #define for2(i,a,b) for (int i = a; i >= b; i--) #define int long long #define sz(a) (int)a.size() #define pii pair<int,int> #define pb push_back /* __builtin_popcountll(x) : Number of 1-bit __builtin_ctzll(x) : Number of trailing 0 */ const long double PI = 3.1415926535897932384626433832795; const int INF = 1000000000000000000; const int MOD = 1000000007; const int MOD2 = 1000000009; const long double EPS = 1e-6; using namespace std; const int N = 1e6 + 5; int n, mx, dp[N]; string s; signed main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); // freopen("cf.inp", "r", stdin); // freopen("cf.out", "w", stdout); cin >> n >> s; for1(i,2,n - 1) if (s[i] == 'a' && s[i - 1] == 'b' && s[i - 2] == 'a') { dp[i] = dp[i - 2] + 1; if (dp[i] > dp[mx]) mx = i; } cout << 'a'; for1(i,1,dp[mx]) cout << "ba"; }
Bình luận
"Có thể chứng minh rằng xâu cần tìm chắc chắn có dạng 'abababa...a'." Nhưng chứng minh kiểu gì vậy mọi người :((
Theo mình thì
Gọi G(x) là giá trị của xâu x
G('abababa...a') là n / (n * 2 + 1) với n là số kí tự 'b' và xâu 'abababa...a' là dài nhất --> n lớn nhất
Ta có n' / (n' * 2 + 1) là giá trị của xâu đó nếu có n' kí tự 'b' (n' < n)
Xét A = n / (n * 2 + 1) - n' / (n' * 2 + 1) = (n - n') / (n * 2 + 1) * (n' * 2 + 1) > 0 với mọi n , n' thỏa mãn
--> Giá trị của n / (n * 2 + 1) là lớn nhất
Còn xét về dạng của xâu thì chắc chắn việc lấy các xâu 'abababa...a' là tối ưu vì nếu có các kí tự khác xen vào sẽ làm tăng mẫu số của G(x) --> giảm giá trị
Mình chỉ không biết tại sao ko chọn đc các xâu dạng như "aba...abaaba...aba", mọi người giải thích giúp mình được không ạ! *Kiểu như test đề chỉ có xâu "aba...abaaba...aba" và tìm ra xâu có giá trị lớn nhất ấy.
giả sử ta có xâu phân biệt kề nhau ababa...ba độ dài khác nhau nma cùng có dạng aba..ba. gọi x1/y1 là giá trị của xâu 1, x2/y2 là giá trị xủa xâu 2=> tổng giá trị của 2 xâu là (x1+x2)/(y1+y2) trường hợp 1: y1=y2=>x1=x2 (vì 2 xâu đều cùng có dạng aba...ba)=> giá trị tổng = x1/y1 trường hợp 2: y1!=y2. ở đây mình sẽ coi như là y1>y2 vì ngược lại thì chứng minh vẫn thế. y1>y2=>x1/y1>x2/y2=>x1/y1>(x1+x2)/(y1+y2)>x2/y2 ( x1/y1 > (x1+x2)/(y1+y2) => x1y1+x1y2 > x1y1+y1x2=> x1y2>y1x2 => x1/y1>x2/y2 =>luôn đúng) =>x1/y1 >= (x1+x2)/(y1+y2) hay giá trị xâu x luôn >= tổng giá trị của x với 1 xâu y kề x có độ dài <=x vậy ta kết luận xâu độ dài lớn nhất sẽ cho ra kết quả tối ưu nhất