B. Mô phỏng trí tuệ nhân tạo

Giải pháp đơn giản sử dụng phương pháp duyệt toàn bộ.

G. Bảo tàng

Chọn k hiện vật có giá trị lớn nhất, ưu tiên vị trí bên trái khi giá trị bằng nhau. Di chuyển tối ưu theo thứ tự từ trái sang phải.

H. Phân tách số nguyên bằng dãy palindrome

Đặt $D_n$ là số cách phân tách. Dãy palindrome có tính chất đệ quy: loại bỏ hai phần tử đầu cuối thu được dãy con palindrome. Công thức truy hồi:

\[ D_n = \begin{cases} (D_{n-2} + D_{n-4} + \cdots + D_1) + 1 & \text{n lẻ} \\ (D_{n-2} + D_{n-4} + \cdots + D_0) + 1 & \text{n chẵn} \end{cases} \]

Biên $D_0 = D_1 = 1$. Rút gọn: $D_n = 2D_{n-2}$ → $D_n = 2^{\lfloor n/2 \rfloor}$. Độ phức tạp $O(\log n)$.

H. Khóa mê cung

Sử dụng BFS với trạng thái biểu diễn bằng tập hợp tọa độ viên bi và hướng trọng lực. Mỗi trạng thái: $\{(x_1,y_1),(x_2,y_2),(x_3,y_3)\}$ + hướng. Viên bi rơi khỏi mê cung ký hiệu $(-1,-1)$.

Chuyển trạng thái mô phỏng rơi theo trọng lực, xử lý va chạm bằng cách lặp cập nhật vị trí. Sử dụng multiset do tọa độ có thể trùng.

#include<iostream>
#include<set>
#include<queue>
#include<map>
using namespace std;

const int dx[4] = {1,0,-1,0}, dy[4] = {0,-1,0,1};
int rows, cols, ball_count;

struct State {
  int gravity;
  multiset<pair<int,int>> balls;
  bool operator<(const State& o) const {
    return gravity==o.gravity ? balls<o.balls : gravity<o.gravity;
  }
};

bool outside(int x, int y) {
  return x<1 || x>rows || y<1 || y>cols;
}

void simulate_fall(State& s) {
  multiset<pair<int,int>> new_pos = s.balls;
  for(int i=0; i<ball_count; i++) {
    multiset<pair<int,int>> temp;
    for(auto [x,y]: new_pos) {
      if(x==-1) { 
        temp.insert({-1,-1}); 
        continue;
      }
      int nx = x + dx[s.gravity], ny = y + dy[s.gravity];
      while(!outside(nx,ny) && grid[nx][ny]=='s' && !temp.count({nx,ny})) {
        x = nx; y = ny;
        nx += dx[s.gravity]; ny += dy[s.gravity];
      }
      if(outside(nx,ny)) temp.insert({-1,-1});
      else temp.insert({x,y});
    }
    new_pos = temp;
  }
  s.balls = new_pos;
}

int main() {
  // Khởi tạo và BFS
}

I. Đua ngựa máy

Xác định khoảng giá trị nhiên liệu $x$ để $(b_i + x) \mod P > a_i$. Bài toán quy về phủ điểm trên trục số. Sử dụng cây phân đoạn xử lý phủ đoạn:

1. Rời rạc hóa các khoảng giá trị
2. Duyệt các điểm chia, cập nhật số tập phủ bằng cây phân đoạn
3. Tối ưu hóa bằng cách quản lý tập không chứa điểm đầu

#include<bits/stdc++.h>
using namespace std;

struct IntervalTree {
  vector<int> tree, lazy;
  void update(int l, int r, int val) { /* ... */ }
  int get_max() { /* ... */ }
};

int main() {
  vector<pair<int,int>> ranges;
  // Xây dựng các đoạn từ điều kiện
  for(int i=0; i<n; i++) {
    int L1 = max(0, a[i]-b[i]+1), R1 = P-b[i]-1;
    if(L1<=R1) ranges.push_back({L1,R1});
    int L2 = P+a[i]-b[i]+1, R2 = P-1;
    if(L2<=R2) ranges.push_back({L2,R2});
  }
  // Rời rạc hóa và xử lý
}

F. Quái vật bóng đêm

Bước 1: Tính khoảng cách tới nhà hàng gần nhất bằng BFS đa nguồn. Bước 2: Xây dựng đồ thị mới với trọng số cạnh $w(u,v) = \min(d_u, d_v)$. Bước 3: Giải bài toán đường đi chai cổ bằng cây khung lớn nhất.

#include<vector>
#include<queue>
#include<algorithm>
using namespace std;

void multi_source_bfs() {
  vector<int> dist(size, INF);
  queue<int> q;
  for(int r: restaurants) {
    dist[r] = 0;
    q.push(r);
  }
  while(!q.empty()) {
    int u = q.front(); q.pop();
    for(int v: neighbors[u]) {
      if(dist[v] > dist[u]+1) {
        dist[v] = dist[u]+1;
        q.push(v);
      }
    }
  }
}

void build_spanning_tree() {
  vector<tuple<int,int,int>> edges;
  for(auto [u,v]: graph_edges) {
    edges.push_back({min(dist[u],dist[v]), u, v});
  }
  sort(edges.rbegin(), edges.rend()); // Giảm dần
  // Xây cây khung lớn nhất
}

C. Lái xe tự động

Đặt $f(u)$ là số token tối thiểu từ $u$ tới đích. Hai chiến thuật:

1. Di chuyển ngẫu nhiên: $f(u) = \max_{(u,v)} f(v)$
2. Trả token: $f(u) = 1 + \min_{(u,v)} f(v)$

Công thức: $f(u) = \min( \max f(v), 1 + \min f(v) )$. Xử lý đồ thị tổng quát bằng BFS mở rộng:

#include<vector>
#include<queue>
using namespace std;

void compute_dp() {
  vector<int> f(n, INF);
  f[target] = 0;
  for(int cost=0; cost<=n; cost++) {
    // Cập nhật nút trả token
    for(int u=0; u<n; u++) {
      if(f[u]!=INF) continue;
      for(int v: graph[u]) {
        if(f[v] < cost) { 
          f[u] = cost; 
          break; 
        }
      }
    }
    // Cập nhật nút di chuyển ngẫu nhiên
    vector<bool> unsafe(n, false);
    for(int u: unreachable_nodes) 
      mark_unsafe(u, unsafe); // Đánh dấu nút không an toàn
    for(int u=0; u<n; u++) {
      if(f[u]==INF && !unsafe[u]) f[u]=cost;
    }
  }
}

D. Bao lồi chung

Bài toán hình học tính toán, không được giải quyết đầy đủ.