比賽鏈接

好消息：永康喵喵這回沒翻車，沒有爆零或掛分！

壞消息：T2 這道唐題竟然沒看懂題意，相當于不知道怎么踩油門！

T1

一道非常簡單的貪心。雖然現在看來十分簡單，但是在場上想了好多種假的做法，畢竟貪心這種東西的核心就是連蒙帶猜。不過最后還是場切了。

簡單說來，就是從左到右遍歷每一根桿子，先嘗試往左放，如果放不了就往右放，如果還是放不了就放棄。

T2

如果讀懂題意，這道題就是完全的唐題。可惜我這四個月來學了不少東西，卻不知道二分圖是什么，遺憾離場。

什么是二分圖呢？簡單來說，這種圖的點可以劃分為兩部分，使得同一部分中的點沒有直接相連的邊。

那么問題就很簡單了。我們可以把左邊和右邊的點分別進行排序，然后計算出 \(\max(b_i - a_i, 0)\) 的前綴最大值和 \(\max(b_{i+1} - a_i, 0)\) 的后綴最大值，然后對于每一個 \(i\)，計算出 \(\max(\mathrm{premax}_{i-1}, \mathrm{sufmax}_{i})\)，最后把答案按原順序還原輸出即可。

#include <bits/stdc++.h>
const int N = 2e5+10;
typedef long long ll;
int n, a[N], b[N], pre1[N], suf2[N], order[N], ans[N];

int main() {
  std::ios::sync_with_stdio(false), std::cin.tie(0);
  std::cin >> n;
  n++;
  for (int i = 1; i <= n; i++) {
    std::cin >> b[i];
  }
  for (int i = 1; i <= n - 1; i++) {
    std::cin >> a[i];
  }
  for (int i = 1; i <= n; i++) {
    order[i] = i;
  }
  std::sort(order+1, order+1+n, [](int x, int y) {
    return b[x] < b[y];
  });
  std::sort(a+1, a+n);
  std::sort(b+1, b+1+n);
  for (int i = 1; i <= n - 1; i++) {
    pre1[i] = std::max(pre1[i-1], std::max(b[i] - a[i], 0));
  }
  for (int i = n-1; i >= 1; i--) {
    suf2[i] = std::max(suf2[i+1], std::max(b[i+1]-a[i], 0));
  }
  for (int i = 1; i <= n; i++) {
    ans[order[i]] = std::max(pre1[i-1], suf2[i]);
  }
  for (int i = 1; i <= n; i++) {
    std::cout << ans[i] << ' ';
  }
  std::cout << '\n';
  return 0;
}

T3

這道題的測試點數據設計真是太妙了，每個測試點的數據范圍都不一樣且遞增，具有很好的區分性。

言歸正傳，這道題要求 \(1 \sim n\) 中每個數的因數的異或和的異或和。如果你注意力驚人，可以注意到，對于每個因子 \(d\)，它在最終答案中出現的次數即為 \(\lfloor \frac{n}w0obha2h00 \rfloor\)，且只有當 \(\lfloor \frac{n}w0obha2h00 \rfloor\) 為奇數時，才會被計入最終答案。因此，題意可以轉化為：

求所有滿足 \(\lfloor \frac{n}w0obha2h00 \rfloor\) 為奇數的 \(d\) 的異或和。

這道題很多人（包括我的 DeepSeek）的第一反應應該是數論分塊。然而當你興高采烈地提交這樣的代碼，就會發現最后一個測試點以 1037 ms 成功 TLE。在 AeeE5x 大神的指導下，我嘗試使用了根號分治：對于\(x < \sqrt{n}\)，枚舉因子；對于 \(x > \sqrt{n}\)，枚舉 \(\lfloor \frac{n}{x} \rfloor\)。

#include <bits/stdc++.h>
typedef long long ll;

inline ll xorSum(ll n) {
  switch (n & 3) {
  case 0:
    return n;
  case 1:
    return 1;
  case 2:
    return n + 1;
  default:
    return 0;
  }
}

int main() {
  freopen("div.in", "r", stdin);
  freopen("div.out", "w", stdout);
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  ll n;
  std::cin >> n;
  register ll ans = 0;
  ll sqrtN = sqrt(n);
  for (ll x = 1; x <= sqrtN; x++) {
    if ((n / x) & 1) {
      ans ^= x;
    }
  }
  for (ll k = 1; k <= sqrtN; k++) {
    if (k & 1) {
      ll l = n / (k + 1) + 1;
      ll r = n / k;
      if (l <= sqrtN) l = sqrtN + 1;
      if (l > r) continue;
      ans ^= xorSum(r) ^ xorSum(l - 1);
    }
  }
  std::cout << ans << '\n';
  return 0;
}

請注意以上代碼使用了快速計算連續整數異或和的技巧。

總結

菜就多練，學得少就多學。