Hướng dẫn giải của Bedao Regular Contest 01 - GRADE
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
Vì các điểm x ~\leq 10^6~ nên ta chỉ cần sử dụng hai mảng là ~G~ và ~F~ với:
~G~ là tần suất của điểm ~K~ trong các dãy bàn liên tiếp
~F~ là giá trị lớn nhất của dãy con có điểm chung là ~K~ tại bàn thứ ~i~.
Vậy làm sao để biết được điểm K có xuất hiện trong 1 loạt các dãy bàn liên tiếp nhau không ?
Tại điểm thứ ~K~ của bàn thứ ~i~ ta sẽ tìm kiếm nhị phân ở bàn thứ ~i-1~ trước đó để xem xem điểm ~K~ có xuất hiện trong bàn thứ ~i-1~ hay không. Nếu không có thì ta sẽ gán ~G_K = 0~ vì lúc này ta không thể ghép ~2~ bàn ~i~ với ~i-1~ lại để được dãy bàn liên tiếp có điểm chung là ~K~ được. Sau mỗi lần duyệt như thế, tại điểm ~K~ đang xét tại bàn thứ ~i~, ta sẽ tăng ~G_K~ lên ~1~ và gán ~F_K = max(F_K , G_K)~.
Code mẫu
/*#pragma GCC optimize("Ofast") #pragma GCC optimize("unroll-loops") #pragma GCC target("avx,avx2,fma")*/ // only when really needed /* GNU G++17 7.3.0: No long long for faster code GNU G++17 9.2.0 (64 bit, msys 2): Long long only for faster code */ #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 */ #define PI 3.1415926535897932384626433832795 #define INF 1000000000000000000 #define MOD 1000000007 #define MOD2 1000000009 #define EPS 1e-6 using namespace std; int n, q, x, a; set<int> se[1005]; 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 >> q; for1(i,1,n) { cin >> x; while (x--) { cin >> a; se[i].insert(a); } } while (q--) { int p, cur = 0, res = 0; cin >> p; for1(i,1,n) { if (se[i].find(p) != se[i].end()) cur++; else cur = 0; res = max(res, cur); } cout << res << "\n"; } }
Bình luận
my friend write,not me
Dòng cuối phải là ~F_K = max(F_K,G_K)~ chứ ạ ? 😃