Bình luận

• 
  

  1

  

  vominhmanh10  đã bình luận lúc 22, Tháng 7, 2026, 8:10 ← sửa 15 →

  Spoil!

  Sub 1: Mô phỏng hoàn toàn

  Sub 2: Để dễ dàng tính toán, chuyển đổi bài toán thành: đặt tường -> trống và trống -> tường, 2 robot là 2 nguồn sáng => đặt 2 nguồn sáng để đổ bóng nhiều nhất trên trục hoành, hai bức tường của biên chỉ giới hạn đặt nguồn sáng, không ảnh hưởng tính toán nên có thể bỏ qua
  Duyệt cặp ~x_1~ và ~x_2~ rồi duyệt ~k~ đoạn ~[l, r]~ mỗi đoạn được ~x_1~ (~x_2~ tương tự) chiếu lên một vùng ~[2l - x_1, 2r - x_1]~
  Lưu vector các đoạn này, sort rồi gộp lại và tính toán trong ~O(n^2k log k)~

  Sub 3: Kết quả bài toán chỉ phụ thuộc 2 điểm sáng lệch nhau bao nhiêu, chứ khi ~x_1~ tịnh tiến tới ~x_1 = d~ thì các đoạn chiếu xuống sẽ lùi lại theo công thức ~[2l - d, 2r - d]~ chứ mật độ đổ bóng vẫn như nhau ở mọi điểm, tương tự với ~x_2~. Vì thế độ lệch của chúng quyết định chúng giao bao nhiêu, càng ít giao thì đổ bóng càng nhiều thôi.
  Ta sẽ cố định ~x_1 = 0~ và dịch chuyển ~x_2~, rồi duyệt ~k~, loại bỏ vòng lặp duyệt ~x_1~ và tính toán trong ~O(nk log k)~ hoặc ~O(nk)~ nếu đánh dấu bằng mảng hiệu

  Code sub 3(dùng thuật toán ~O(nk log k)~:

  #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  using ull = unsigned long long;
  #define all(a) a.begin(), a.end()
  #define eb emplace_back
  #define pb push_back
  #define pii pair< ll, ll>
  #define fi first
  #define se second
  #define mini(a, b) (a) = min((a), (b))
  #define maxi(a, b) (a) = max((a), (b))
  #define filled(a, b) memset(a, b, sizeof(a))
  #define IO ios::sync_with_stdio(0); cin.tie(0)
  #define func inline __attribute__((always_inline))
  const ll maxn = 1e5 + 4, inf = 1e18, mod = 1e9 + 7, block = 470, maxa = 2e5 + 6;
  const ull base = 257; 
  
  
  
  ll n, k,  ans = 0;
  vector< pii> a;
  int main() {
      if (fopen("ROAI.INP", "r")) {
          freopen("ROAI.INP", "r", stdin);
          freopen("ROAI.OUT", "w", stdout);
      }
      IO; cin >> n >> k; vector< pii> b(k);
      for (int i = 0; i < k; ++i) cin >> b[i].fi >> b[i].se;
      int cur = 0;
      for (auto &[l, r] : b) {
          if (cur < l) a.eb(cur, l);
          cur = r;
      }
      if (cur < n) a.eb(cur, n);
      b.clear();
      if (a.empty()) {
          cout << 0;
          return 0;
      }
  
      for (ll x = 1; x <= n; ++x) {
          for (auto &[l, r] : a) {
              b.eb(2 * l, 2 * r);
              b.eb(2 * l - x, 2 * r - x);
          }
          sort(all(b));
          ll res = 0, cur = -inf;
          for (auto &[l, r] : b) {
              if (l < cur) res += max(0LL, r - cur);
              else res += (r - l);
              maxi(cur, r);
          }
          b.clear();
          maxi(ans, res);
      }
      cout << ans << "\n";
  }
  

  !<

  Sub 4 & 5: tiếp tục với việc 2 nguồn sáng chỉ phụ thuộc vào độ lệch của chúng hay chính là chúng giao nhau bao nhiêu, ~x_1 = 0~ cố định, giờ ta chỉ duyệt những ~x_2~ có thể đạt phần giao ít nhất có thể
  Xét quá trình ~x_2~ tịnh tiến, các đoạn chiếu dưới trục hoành bởi ~x_2~ sẽ có những thời điểm chúng đụng nhau ở biên của đoạn chiếu bởi ~x_1~, thời điểm này chúng bắt đầu tăng phần giao, giảm phần giao nhau hoặc giữ nguyên, chính những thời điểm này mới tạo nên các điểm tối ưu ta cần.
  Có ~2k~ biên cần xét, tính ~x_2~ tối ưu bằng cách xét mọi cặp có ~4k^2 = O(k ^ 2)~ sự kiện hay độ lệch cần tìm tối ưu. Kĩ thuật sweepline sắp các ~x_2~ và tính toán lượng giao nhau giữa các thời điểm và lấy kết quả với mọi thời điểm ~x_2~ tại ~0 \le x_2 \le n~.
  Lượng đổ bóng của 2 điểm là lượng ~total~ cố định vậy chúng phủ ~2total - ans~, tính phần giao nhỏ nhất ~ans~ tại mỗi thời điểm trong ~O(k^2)~.

  Code sub 4 & 5:

  #include <bits/stdc++.h>
  using namespace std;
  using ll = long long;
  using ull = unsigned long long;
  #define all(a) a.begin(), a.end()
  #define eb emplace_back
  #define pb push_back
  #define pii pair< ll, ll>
  #define fi first
  #define se second
  #define mini(a, b) (a) = min((a), (b))
  #define maxi(a, b) (a) = max((a), (b))
  #define filled(a, b) memset(a, b, sizeof(a))
  #define IO ios::sync_with_stdio(0); cin.tie(0)
  #define func inline __attribute__((always_inline))
  const ll maxn = 1e5 + 4, inf = 1e18, mod = 1e9 + 7, block = 470, maxa = 2e5 + 6;
  const ull base = 257; 
  
  ll n, k, ans = inf;
  vector< pii> a, b;
  int main() {
      if (fopen("ROAI.INP", "r")) {
          freopen("ROAI.INP", "r", stdin);
          freopen("ROAI.OUT", "w", stdout);
      }
      IO; cin >> n >> k; b.resize(k);
      for (int i = 0; i < k; ++i) cin >> b[i].fi >> b[i].se;
      int cur = 0;
      for (auto [l, r] : b) {
          if (cur < l) a.eb(cur, l);
          cur = r;
      }
      ll total = 0;
      if (cur < n) a.eb(cur, n);
      for (auto &[l, r] : a) {
          l <<= 1, r <<= 1;
          total += (r - l);
      }
      b.clear();
      b.reserve(5 * k * k);
      for (auto [l1, r1] : a) for (auto [l2, r2] : a) {
          ll d1 = l2 - r1, d2 = r2 - r1, d3 = l2 - l1, d4 = r2 - l1;
          b.eb(d1, 1);
          b.eb(d2, -1);
          b.eb(d3, -1);
          b.eb(d4, 1);
      }
      sort(all(b));
      ll spole = 0, last_d = -1e9, res = 0; 
      int i = 0, m = b.size();
      while (i < m) {
          ll d = b[i].fi;
          res += spole * (d - last_d);
          ll st = max(0LL, last_d), en = min(n, d);
          if (st <= en) {
              mini(ans, res - spole * (d - st));
              mini(ans, res - spole * (d - en));
          }
          while (i < m && b[i].fi == d) spole += b[i++].se;
          last_d = d;
      }
      cout << 2 * total - ans;
  }