Editorial for VOI 14 Bài 2 - Dãy con chung bội hai dài nhất
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của happyboy99x
#include<algorithm> #include<iostream> #include<vector> using namespace std; struct BIT2D { vector<vector<int> > data; int m, n; BIT2D(int m, int n): data (m, vector<int>(n, 0)), m (m), n (n) {} void update(int idx, int idy, int val) { for(int x = idx; x < m; x |= x + 1) for(int y = idy; y < n; y |= y + 1) data[x][y] = max(data[x][y], val); } int get(int idx, int idy) const { int res = 0; for(int x = idx; x >= 0; x -= ~x & (x + 1)) for(int y = idy; y >= 0; y -= ~y & (y + 1)) res = max(res, data[x][y]); return res; } }; const int N = 1500; int a[N], b[N], f[N + 1][N + 1]; int main() { ios::sync_with_stdio(false); int tc; cin >> tc; while(tc--) { int m, n; cin >> m >> n; for(int i = 0; i < m; ++i) cin >> a[i]; for(int i = 0; i < n; ++i) cin >> b[i]; vector<int> v (b, b + n); sort(v.begin(), v.end()); v.erase(unique(v.begin(), v.end()), v.end()); BIT2D bit (n, v.size()); for(int i = 0; i < m; ++i) { vector<int> toUpdate; for(int j = 0; j < n; ++j) { if(a[i] == b[j]) { int p = upper_bound(v.begin(), v.end(), b[j] / 2) - v.begin() - 1; f[i + 1][j + 1] = bit.get(j - 1, p) + 1; toUpdate.push_back(j); } else { f[i + 1][j + 1] = max(f[i][j + 1], f[i + 1][j]); } } for(unsigned k = 0; k < toUpdate.size(); ++k) { int j = toUpdate[k]; int p = lower_bound(v.begin(), v.end(), b[j]) - v.begin(); bit.update(j, p, f[i + 1][j + 1]); } } cout << f[m][n] << endl; } return 0; }
Code mẫu của ladpro98
#include <bits/stdc++.h> using namespace std; const int N = 1505; int BIT[N][N]; int a[N], b[N]; int n, m, SIZE; void update(int i, int y, int v) { for (; i <= n; i += i & -i) for (int j = y; j <= SIZE; j += j & -j) BIT[i][j] = max(BIT[i][j], v); } int getMax(int i, int y) { int ans = 0; for (; i; i -= i & -i) for (int j = y; j; j -= j & -j) ans = max(ans, BIT[i][j]); return ans; } void solve() { cin >> m >> n; for (int i = 1; i <= m; ++i) cin >> a[i]; for (int i = 1; i <= n; ++i) cin >> b[i]; vector<int> V (b + 1, b + 1 + n); sort(V.begin(), V.end()); V.resize(unique(V.begin(), V.end()) - V.begin()); SIZE = V.size(); for (int i = 1; i <= n; ++i) for (int j = 1; j <= SIZE; ++j) BIT[i][j] = 0; int ans = 0; for (int i = 1; i <= m; ++i) { vector<pair<pair<int, int>, int> > buffer; for (int j = 1; j <= n; ++j) if (a[i] == b[j]) { int value = lower_bound(V.begin(), V.end(), a[i]) - V.begin() + 1; int half = int(upper_bound(V.begin(), V.end(), a[i] >> 1) - V.begin()); int cur = getMax(j - 1, half) + 1; ans = max(ans, cur); buffer.push_back(make_pair(make_pair(j, value), cur)); } while (!buffer.empty()) { update(buffer.back().first.first, buffer.back().first.second, buffer.back().second); buffer.pop_back(); } } cout << ans << '\n'; } int main() { ios::sync_with_stdio(0); cin.tie(0); #ifndef ONLINE_JUDGE freopen("LCS2X.txt", "r", stdin); #endif // ONLINE_JUDGE int nTest; cin >> nTest; while (nTest--) solve(); return 0; }
Code mẫu của RR
#include <bits/stdc++.h> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define DEBUG(x) { cout << #x << " = "; cout << x << endl; } #define PR(a,n) { cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; } #define PR0(a,n) { cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; } using namespace std; //Buffer reading int INP,AM,REACHEOF; const int BUFSIZE = (1<<12) + 17; char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp && !REACHEOF) { \ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const int MN = 3011; int a[MN], b[MN], m, n, c[MN], s; int nextb[MN][MN]; int ca[MN], cb[MN], f[MN][55]; void init() { FOR(i,1,m) ca[i] = ca[i-1] + (a[i] == 0); FOR(i,1,n) cb[i] = cb[i-1] + (b[i] == 0); s = 0; FOR(i,1,m) c[++s] = a[i]; FOR(i,1,n) c[++s] = b[i]; sort(c+1, c+s+1); s = unique(c+1, c+s+1) - c - 1; FOR(i,1,m) a[i] = lower_bound(c+1, c+s+1, a[i]) - c; FOR(i,1,n) b[i] = lower_bound(c+1, c+s+1, b[i]) - c; memset(nextb, 0, sizeof nextb); FORD(i,n,1) { FOR(j,1,i) nextb[i][b[j]] = j; } } void solve() { int res = min(ca[m], cb[n]); // DEBUG(res); FORD(i,m,1) FOR(h,1,31) if (c[a[i]]) { if (h == 1) { f[i][1] = nextb[n][a[i]]; } else { f[i][h] = 0; if (f[i][h-1] == 0) continue; FOR(ii,i+1,m) if (c[a[i]] * 2 <= c[a[ii]]) { int u = f[ii][h-1]; f[i][h] = max(f[i][h], nextb[u][a[i]]); } } if (f[i][h]) { res = max(res, h + min(ca[i-1], cb[f[i][h]-1])); // cout << i << ' ' << h << ' ' << f[i][h] << ' ' << res << endl; } } cout << res << endl; } int main() { ios :: sync_with_stdio(false); int ntest; cin >> ntest; while (ntest--) { cin >> m >> n; FOR(i,1,m) cin >> a[i]; FOR(i,1,n) cin >> b[i]; init(); solve(); } return 0; }
Comments