比賽鏈接

分數(shù)：\(100 + 100 + 0 + 0 = 200\)

永康喵喵又沒有翻車！

有了前幾次翻車的教訓(xùn)，我形成了先寫注釋（對于難題）\(\rightarrow\) 仔細寫題 \(\rightarrow\) 靜態(tài)檢查 \(\rightarrow\) 動態(tài)檢查 \(\rightarrow\)（所有能做的題做完后）對拍 \(\rightarrow\) 最后核查的流程，大大降低了翻車率。如果你比較粗心，不妨也借鑒一下這套流程。

言歸正傳，分析題目。

T1

為什么數(shù)據(jù)這么水啊，\(n \le 50\) 是啥陰。這題明明有 \(n^2\) 做法，而且并不難，為什么不把數(shù)據(jù)范圍開到 \(n \le 3000\)。

當(dāng)然考場上寫題速度很重要，所以我當(dāng)然是暴力打 \(n^4\)。如果要 \(n^2\)，可以先計算出沒有老師時的握手次數(shù)，然后枚舉老師的位置，更新其周圍的握手情況。握手需要 \(2\) 個人進行，所以最后不要忘了 \(\div 2\)。

T2

在變換次數(shù)比較小（\(k \le 1000\)）時，暴力的時間復(fù)雜度可以接受，可是如果變換次數(shù)達到 \(10^9\) 就會 T 飛。但是如果仔細分析變換的過程就會發(fā)現(xiàn)這是一個周期性變換。因此可以先暴力找到周期 \(a\)，然后將 \(k\) 對 \(a\) 取模，再進行暴力。考慮到 \(|S| \le 1000\)，如果要進一步縮短程序運行時間，甚至可以打表（我就是如此場切的）。

T3

不知道為什么 ZR 也學(xué)上了 aoao，先放兩道特別水的題，然后在 T3 突然上難度，很搞人心態(tài)。

不過要是摸清了這道題的本質(zhì)就不難了。今天下午我學(xué)了 Floyd 最短路算法，其本質(zhì)是尋找一個中轉(zhuǎn)點，然后用它更新兩邊點的距離。這道題也類似。我們可以設(shè) \(f_{i, j}\) 表示當(dāng)前路徑的兩個端點分別為 \(i, j\)，且已經(jīng)訪問了從 \(1\) 到 \(\max(i, j)\) 的所有點時的最小時間。初始時，\(f_{1,1}=0\)。

然后進行狀態(tài)轉(zhuǎn)移：

• 遍歷 \(i, j\)。

• 計算下一個要訪問的點 \(k = \max(i, j)+1\)。如果 \(k > n\) 則跳過。

• 更新兩個新狀態(tài)：

  • 從端點 \(j\) 擴展到 \(k\)：路徑變?yōu)?\((i, k)\)，時間增加 \(d_{j, k}\)，即 \(f_{i, k} = \min(f_{i, k}, f_{i, j} + d_{j, k})\)。

  • 從端點 \(i\) 擴展到 \(k\)：路徑變?yōu)?\((k, j)\)，時間增加 \(d_{i, k}\)，即 \(f_{k, j} = \min(f_{k, j}, f_{i, j} + d_{i, k})\)。

  這樣擴展保證了當(dāng)訪問點 \(k\) 時，所有小于 \(k\) 的點都已經(jīng)被訪問，滿足限制條件。

輸出答案時，遍歷所有 \(i\)，然后取 \(f_{n, i}\) 和 \(f_{i, n}\) 的最小值作為答案。

T4

如果仔細分析，這道題就是典型的紙老虎。

不難 （其實很難） 發(fā)現(xiàn)，有多少個不同的橫坐標，就能畫多少條不同的豎線；有多少個不同的縱坐標，就能畫多少條不同的橫線。同時，兩個人若要求得最優(yōu)策略，畫的線一定是橫縱交替的。所以，如果 Alice 要輸，那么一定由 Bob 把最后一根線畫完，也就是橫縱坐標數(shù)量相等。用 set 維護即可。

#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5+10;
std::set<int> xs, ys;
int n;

int main() {
  std::ios::sync_with_stdio(false); std::cin.tie(0);
  std::cin >> n;
  for (int i = 1; i <= n; i++) {
    int x, y;
    std::cin >> x >> y;
    xs.insert(x), ys.insert(y);
  }
  if (xs.size() == ys.size()) {
    std::cout << "Bob\n";
  } else {
    std::cout << "Alice\n";
  }
  return 0;
}