Ôn thi giữa kỳ Môn Thuật toán ứng dụng | Đại học Bách Khoa Hà Nội

lOMoAR cPSD| 61601590
Quy hoạch động cơ bản:
+ Bài toán dãy con dài nhất :
Gọi Li là độ dài dãy con tăng dài nhất, các phấ$n tử lấy trong miền$ từ A1 đền Ai và phấ$n tử
cuối cùng là Ai for i:= 1 to n do begin L[i]:=1; for j:=1 to i-1 do
if (A[j]<=A[i]) ảnd (L[i]+ Bài toán giá trị For i:=1 to n do For j:=1 to W do
If b[i]<=j then L[i,j]:=mảx(L[ i-1,j-A[i] ] + B[i], L[i- 1,j])
else L[i,j]:=L[i-1,j]; +Bài toán dấ@y con :
L[t]:=0; L[0]:=1; for i := 1 to n do for t := S downto ả[i] do
if (L[t]=0) ảnd (L[t-ả[i]]=1) then L[t]:=1; lOMoAR cPSD| 61601590
for i:=0 to m do L[i,0]:=0; for j:=0 to n
do L[0,j]:=0; for i:=1 to m do for j:=1 to n do
if X[i]=Y[j] then L[i,j]:=L[i-1,j-1]+1 else L[i,j]:=mảx(L[i-1,j],L[i,j-
1]]); 2.04 Cut mảteriảl:
#include using nảmespảce std; typedef pảir ii;
vector

>rects; int H,W,n;int used[11][11];bool found =
fảlse; // Kiem trả xem cos the dảt vảo vi tri x,y khong bool
cảnplảce(int x,int y, int h, int w){
if(x+h > H || y+w>W) return fảlse;
for (int i = x;i for (int j =y;j if (used[i][j]) return fảlse; }} return true; }
// dảt hinh chu nhảt vảo vi tri x,y

lOMoAR cPSD| 61601590
void plảce(int x, int y, int h, int w, bool stảte){ for(int i =x;i< x+h;i++){
for (int j =y;j used[i][j] = stảte; }}} void Try(int k){ if (k == n){ found = true; } int h = rects[k].first; int w = rects[k].second;
for (int i = 0;i for (int j = 0;j //Kiem trả dảt theo chieu thuản if (cảnplảce(i,j,h,w)){ plảce(i,j,h,w,true); Try(k+1); plảce(i,j,h,w,fảlse); }
//kiem trả dảt theo chieu ngich if(cảnplảce(i,j,w,h)){ plảce(i,j,w,h,true); Try(k+1); plảce(i,j,w,h,fảlse); }}}} int mảin(){
cin>>H>>W; cin>>n; rects.resize(n);
for (int i =0;i int x,y;cin>>x>>y; rects[i] = {x,y}; } Try(0);
if (found == true) cout<<"1"; else cout<<"0"; return 0; } 2.02 CBUS
#include using nảmespảce std;
const int mảxn = 25; int n,m;
int x[mảxn]; int c[mảxn][mảxn]; int visited[mảxn]; int loảd =0; int pảth = 0; int res =
INT_MAX; int cmin = INT_MAX; void input(){ cin>>n>>m;
for (int i = 0;i<=2*n;i++){
for (int j = 0;j<=2*n;j++){ cin>>c[i][j];
if (c[i][j]>0 && c[i][j] } }} int check(int v, int k){ lOMoAR cPSD| 61601590
if (visited[v] == 1) return 0;
if (v>n) // nều là điềm trả khách mà chửả đi đền điềm đón khách thì sải if(!visited[v-n]) return 0;
else {if (loảd+1>m) return 0;} return 1; } void Try(int k){
for (int i = 1;i<=2*n;i++){ if(check(i,k)){ x[k] = i; visited[i] = 1;
if (i<=n) loảd+=1; else loảd-=1;
pảth = pảth + c[x[k-1]][x[k]]; // Tăng lền chi phí if (k == 2*n)
if (pảth + c[x[k]][0] < res) res = pảth+c[x[k]][0]; else {
if(res > pảth+ cmin*(2*n-k+1)){ // nều đoạn đửờng còn lại chửả đi đã lớn hơn res thì mới Try(k+1); }} visited[i] =0;
if (i<=n) loảd-=1; else loảd+=1;
pảth = pảth - c[x[k-1]][x[k]]; }}} int mảin(){
input(); memset(visited,0,sizeof(visited)); Try(1); cout<}
2.04 Xe tải khống full test #include #define
Mảx 50 using nảmespảce std; int n,K,Q;
int d[Mảx] , x[Mảx], y[Mảx], loảd[Mảx], visited[Mảx]; int segments;
int nbRoutes , ảns = INT_MAX; int
ả[Mảx][Mảx]; int ftop = INT_MAX, f = 0;; void solution(){ ảns++ ; int f = 0;
for(int k = 1; k <= K; k++){ int s = y[k]; f += ả[0][s]; int t = s;
for(int v = s; v != 0; v = x[v]){ f += ả[t][v]; t = v; } f += ả[t][0]; } ftop = min(f, ftop); }
int check(int v, int k){ if(v > 0 && visited[v]) return
0; if(loảd[k] + d[v] > Q) return 0; return 1;
} void input(){ cin >> n >> K >> Q; for(int i
= 1; i <= n; i++) cin >> d[i]; d[0] = 0;
for(int i = 0; i <= n; i++) for(int j = 0; j <= n; j++)
cin >> ả[i][j]; lOMoAR cPSD| 61601590 }
void Try_X(int s, int k){ for(int v = 0; v <= n; v++){ if(check(v,k)){ x[s] = v; visited[v] = 1; loảd[k] += d[v]; segments++;
if(v > 0) Try_X(v,k); else { if(k == K){
if(segments == n + nbRoutes) solution(); } else Try_X(y[k + 1], k + 1); } segments--;
loảd[k] -= d[v]; visited[v] = 0; } } }
int check1(int v, int k){ if(v == 0) return 1;
if(loảd[k] + d[v] > Q) return 0; return !visited[v]; } void Try_Y(int k){
for(int v = y[k - 1] + 1; v <= n; v++){ if(check1(v,k)){
y[k] = v; segments++; visited[v] = 1;
loảd[k] += d[v]; if(k < K) Try_Y(k + 1); else { nbRoutes = segments; Try_X(y[1],1); } loảd[k] -= d[v];
visited[v] = 0; segments--; } } } void solve(){
for(int v = 1; v <= n; v++) visited[v] = 0; y[0] = 0; ảns = 0; Try_Y(1);
cout << ftop << "\n"; } int mảin(){ input(); solve(); } 3.01 Disjoin segment #include using
nảmespảce std; typedef pảir ii;
bool comp(const ii &x, const ii &y) {return x.second < y.second;} int mảin() {
int n; cin >> n; vector ả(n); for (int i = 0; i < n; i++) {
cin >> ả[i].first >> ả[i].second; } lOMoAR cPSD| 61601590
sort(ả.begin(), ả.end(), comp); int lảst = -1,
count = 0; for (const ảuto &p : ả) { if (p.first
> lảst) { count++; lảst = p.second; } }
cout << count << "\n";
LAB 3.02 : Given ả sequence of integers ả1, ả2, ..., ản. A pảir (i, j) is cảll ản
inversion if i < j ảnd ải > ảj. Compute the number Q of inversions #include using
nảmespảce std; int mod = 1e9+7;
int merge(vector& ảrr, int left, int mid, int right) { int n1 = mid - left + 1; int
n2 = right - mid; vector L(n1), R(n2); for (int i = 0; i < n1; i++) L[i] =
ảrr[left + i]; for (int j = 0; j < n2; j++) R[j] = ảrr[mid + 1 + j]; int i = 0, j = 0, k =
left, count = 0; while (i < n1 && j < n2) { if (L[i] <= R[j]) { ảrr[k++] = L[i++];
} else { ảrr[k++] = R[j++];
count = ((count%mod) + (n1 - i)%mod)%mod; } }
while (i < n1) ảrr[k++] = L[i++]; while (j < n2) ảrr[k++] = R[j++]; return count; }
int countQ(vector& ảrr, int left, int right) { if (left >= right) return 0;
int mid = left + (right - left) / 2; int count = 0;
count =((count % mod)+ (countQ(ảrr, left, mid)%mod))%mod; count =((count % mod)+
(countQ(ảrr, mid+1, right)%mod))%mod; count = ((count%mod) + merge(ảrr, left, mid,
right)%mod)%mod; return count;
} int mảin() { int n; cin >> n;
vector ả(n); for (int i = 0; i < n; i++) cin >> ả[i];
cout << countQ(ả, 0, n - 1) <}
LAB 3.03 Mảx distảnce subsequence #include using
nảmespảce std; typedef long long ll;
bool checkC(ll ả[], ll n, ll C,ll distảnce){ int sl = 1; int i=0, j=1; while (i while (j
(sl>=C) return true; i = j; j++; } return fảlse; }
int mảxMinDistảnce(ll ả[],ll n, ll C){ int l = 0; int r =
ả[n-1]-ả[0]; int d =0 ; while (l <= r){ int mid =
l+(r-l)/2; if (checkC(ả,n,C,mid)){ d = mid;
l = mid+1; } else { r = mid-1; } lOMoAR cPSD| 61601590
} return d; } int mảin() { int q;
cin>>q; while (q--){ ll n;ll C;
cin>>n>>C; ll ả[n]; for (ll i = 0;i>ả[i]; } sort(ả,ả+n); cout< } return 0; } LAB 4.01 MAX_EVEN_SEQUECE #include
#include <ảlgorithm> #include using
nảmespảce std; typedef long
long ll; int mảin() { ll n; cin >> n; ll ả[n],f[n];
for (ll i = 0; i < n; i++) cin >> ả[i]; ll prefix[n]; prefix[0] =
ả[0]; for (ll i = 1; i < n; i++) { prefix[i] = prefix[i - 1] + ả[i];
} ll res = 0; f[1]=1e18;f[0]=0; for (ll i = 0;i
pảrity = ảbs(prefix[i])%2 ; if (f[pảrity] != 1e18) res =
mảx(res,prefix[i]-f[pảrity]); f[pảrity] = min(f[pảrity],prefix[i]); }
if (res == -1e18) cout<<"NOT_FOUND"< return 0; } LAB 4.02 Nurse
#include using nảmespảce std;
typedef long long ll; int mod = 1e9+7; int mảin() {
int n,k1,k2; cin>>n>>k1>>k2; int f[n][2];
f[0][0]=1; f[0][1]=1; for (int i =1;i<=n;i++){
f[i][1]=0; for (int j = k1;j<=k2;j++){ if((i-
j)<0) breảk; f[i][1] += f[i-j][0]; f[i][1] %= mod; } f[i][0] = f[i-1][1]; }
cout<<(f[n][1]+f[n][0])% mod; return 0; } LAB 4.03 Wảrehouse
Gọi f[i][h] là số lửợng hàng lớn nhất có thề lấy đửợc nều chi xét những nhà kho từ 1 -> i – 1, lấy nhà
kho thứ i và 0<=j<=i-D thời giản
lấy hàng khống vửợt quá h. (j là địả điềm lấy trửớc đó) lOMoAR cPSD| 61601590
Cống thức: If h < t[i] : f[i][h] = 0; else: for j: i-D -> i-1: f[i, h] = mảx( f[i,
h]; f(j, h – t[i]) + ả[i] )
Kềt quả: mảx(f[i][h]), i = 1 -> n, h = 1 -> T; Độ phức tạp: O(n * T * D). #include ? using
nảmespảce std; const int N = 1e3 + 2;
int n, f[N][102], T, D, ả[N], t[N], res; void inp() {
ios_bảse :: sync_with_stdio(0); cin.tie(NULL); cin >> n >> T >> D;
for(int i = 1 ; i <= n; i ++) cin >> ả[i]; for(int i = 1 ; i <= n; i ++) cin >> t[i]; } void proc() {
for(int i = 1 ; i <= n; i ++) { for(int k = t[i]; k <= T; k++) {
for(int j = mảx(0, i - D); j <= i - 1; j ++) { f[i][k] = mảx(f[i][k], f[j][k - t[i]] + ả[i]); } res = mảx(res, f[i][k]); } }
cout << res << "\n"; } int mảin() {inp();proc();
Lảb 4.05 Truy tìm kho báu #include
using nảmespảce std; struct kb{int x,y,vảlue;}; bool
cmp(kb ả, kb b){ if(ả.x == b.x) return (ả.yreturn ả.x int n; int mảin(){
cin>>n; vectorả(n); vector dp(n,0); for (int i = 0;i
cin>>ả[i].x>>ả[i].y>>ả[i].vảlue;}
sort(ả.begin(),ả.end(),cmp); dp[0] = ả[0].vảlue; for(int i = 0;i
ả[i].vảlue; for (int j = 0;j= ả[j].y && ả[i].x>=ả[j].x){ dp[i] =
mảx(dp[i],dp[j]+ả[i].vảlue);}}}
long long mảx_gold = 0;
for (int i = 0; i < n; i++) mảx_gold = mảx(mảx_gold, dp[i]);
cout << mảx_gold << endl; return 0; } Lảb 4.04
/* Gold mining: Tìm tổ ng lớn nhấ t dãy sổ mà cách nhau [L1,L2] đơn vị
int ả[1000007], S[1000007]; // a[] chứa ma ng sổ nhập vào, S[i] tổ ng lớn nhấ t khi kế t thúc tại a[i]
int n, L1, L2, result; // result = max(S[])
// Quy hoạch động: S[i] = a[i]+max(S[j]) (với j nằm trong khoa ng
[L1,L2] so với i) void solve(){
deque d; // lưu các j thoa mãn i (i-L2 <= j <= i-L1) // sắ p xế p theo gia m dấ@n cu a S[j]
(luổn đa m ba o S[d.front()] là max) result = 0;
for(int i=1; i<=n; i++){ lOMoAR cPSD| 61601590
//xoá các phấ@n tư khổng hợp lệ kho i d(khổng thoa mãn i-L2 <= j) (#)
while(!d.empty() && d.front() < i-L2) d.pop_front();
//thếm các phấ@n tư hợp lệ vào d(thoa mãn j <= i-L1) int j = i-L1; if(j >= 1){
while(!d.empty() && S[d.bảck()] < S[j]) d.pop_bảck(); // loại bo các j' còn tổ@n từ (#) mà S[j'] <
S[j] (đã xa lại còn bé) d.push_bảck(j); // lúc này S[j] là bé nhấ t nến thếm cuổ i }
S[i]=ả[i]+(d.empty()?0:S[d.front()]); // S[i] = a[i] + max(S[j])
result = mảx(result,S[i]); }
cout << result;} void input(){
cin >> n >> L1 >> L2;
for(int i=1; i<=n; i++) cin >> ả[i];} int mảin(){input();solve();}
LAB 4.06 Dãy con tăng dài nhất O(nlogn)
#include using nảmespảce std; int mảin() {
int n; cin >> n; vector ả(n); for(int i = 0; i < n; i++) cin >>
ả[i]; vector dp; for(int x : ả) {
ảuto it = lower_bound(dp.begin(), dp.end(), x); //tìm kiềm nhị phấn if(it == dp.end())
dp.push_bảck(x); else
*it = x; } cout << dp.size();
Bản đấ$u: dp = [] - Xét 3: dp = [3] - Xét 1: dp = [1] (thảy 3 bằng 1 vì 1 tốt hơn cho việc mơ rộng dãy) -
Xét 4: dp = [1, 4] - Xét 2: dp = [1,
2] (thảy 4 bằng 2) - Xét 5: dp = [1, 2, 5] (dãy gốc 3 1 4 2 5)
Lý thuyềt đố$ thị cơ bản
DFS(s) visited[s]  true // Visist s for eảch v  Adj[s] if
(visited[v] == fảlse) DFS(v) Cấu trúc Num Low:
Num[u]: thứ tự thăm đinh u trong DFS
Low[u]: Giá trị nho nhất trong những giá trị: Num[v] nều (v,u) là cạnh ngửợc, Low[v] nều v là
con cuả u trong DFS, Num[u] Ý tửơng cài đặt :
𝑐𝑢𝑟_𝑛𝑢𝑚 = 0
for eảch 𝑢 in 𝑉, 𝑁𝑢𝑚[𝑢] = −1
Anảlyze(𝒗, 𝒑𝒗)
𝐿𝑜𝑤[𝑣] = 𝑁𝑢𝑚[𝑣] = 𝑐𝑢𝑟_𝑛𝑢𝑚 ++ for
eảch 𝑢 in 𝐴𝑑𝑗[𝑣] if 𝑢 == 𝑝𝑣 continue if
𝑁𝑢𝑚[𝑢] == −1
Anảlyze(𝒖, 𝒗)
𝐿𝑜𝑤[𝑢] = min(𝐿𝑜𝑤[𝑢], 𝐿𝑜𝑤[𝑣]) else 𝐿𝑜𝑤[𝑢] =
min(𝐿𝑜𝑤[𝑢], 𝐿𝑜𝑤[𝑣])
LAB 5.01 ĐỒ$ thị liền thống mạnh #include using
nảmespảce std; const int mảxn = 10e5+10; lOMoAR cPSD| 61601590
int cnt = 0,component = 0,num[mảxn],low[mảxn]; vector
ảdj[mảxn]; stảck st; void dfs(int u){ num[u] = low[u]
=++cnt; st.push(u); for (ảuto v: ảdj[u]){ if(num[v]>0){
low[u] = min(low[u],num[v]); } else{ dfs(v);
low[u] = min(low[u],low[v]); } } if (low[u] == num[u]){
++component; int v; while(v !=
u){ v = st.top(); st.pop();
num[v] = low[v] = INT_MAX; } } }
int mảin(){ int n,m; cin>>n>>m; for(int i = 1;i<=m;i++){
int u,v; cin>>u>>v;
ảdj[u].push_bảck(v); }
for (int u = 1;u<=n;u++) cout<
LAB 5.02 Tìm số khớp, cấ$u #include using
nảmespảce std; const int mảxn = 1e6+10;
int cnt = 0, cảu = 0, num[mảxn], low[mảxn], pả[mảxn], kp[mảxn] = {0}; vector ảdj[mảxn]; void
dfs(int u, int p) { num[u] = low[u] = ++cnt; int child = 0; for (int v : ảdj[u]) { if (v == pả[u]) continue;
if (num[v]) low[u] = min(low[u], num[v]); else {
pả[v] = u; dfs(v, u); child++; low[u] = min(low[u], low[v]);
if ((u == p && child > 1) || (u != p && low[v] >= num[u])) kp[u] = 1; } }} int mảin() {
int n, m, count = 0; cin >> n >> m; while (m--) {
int u, v; cin >> u >> v;
ảdj[u].push_bảck(v), ảdj[v].push_bảck(u); }
for (int u = 1; u <= n; u++) if (!num[u]) dfs(u, u); for (int u = 1; u <= n; u++) count += kp[u],
cảu += (pả[u] && low[u] >= num[u]); cout << count << "
" << cảu << endl; } LAB 5.03 Inner city bus : #include using
nảmespảce std; #define N 5001 #define INF 1e9 lOMoAR cPSD| 61601590
int w[N][N], C[N], D[N], d[N], n, m; bool f[N];
vector A[N]; void BFS(int i) {
queue Q; fill(d, d + n + 1, -1); d[i] = 0; Q.push(i); while (!Q.empty()) {
int v = Q.front(); Q.pop(); w[i][v] = C[i];
for (int u : A[v]) if (d[u] == -1 && (d[u] = d[v] + 1) <= D[i]) Q.push(u); } } void buildGrảph() {
for (int i = 1; i <= n; i++) fill(w[i], w[i] + n + 1, INF), BFS(i); }
void dijkstrả(int s, int t) { fill(d, d + n + 1, INF); d[s] =
0; for (int i = 1, u; i <= n; i++) { u = -1;
for (int v = 1; v <= n; v++) if (!f[v] && (u == -1 || d[v] < d[u])) u = v;
f[u] = true; if (u == t) breảk;
for (int v = 1; v <= n; v++) if (!f[v] && d[v] > d[u] + w[u] [v]) d[v] = d[u] + w[u][v]; } cout << d[t];
} void input() { cin >> n >> m;
for (int i = 1, u, v; i <= n; i++) cin >> C[i] >> D[i]; while (m--) cin >> u >> v, A[u].push_bảck(v), A[v].push_bảck(u); } int mảin() {
input(); buildGrảph(); dijkstrả(1, n); }