比賽鏈接

比賽時的狀態(tài) be like:

• 我靠，這題怎么這么難？T1 就開始上難度了？
• 沒一道題會寫，不會要爆零然后遺憾離場了吧？
• （想了 2147483647 種 T1 的假做法）
• （去體檢，在測血壓時）等會，我好像想明白 T1 的本質了……
• （回機房）秒切 T1！
• 開 T2！也不難，想一想就會了！
• 看來這場比賽也就那樣嘛！向著 T3 進發(fā)！
• 不是哥們這是什么東西啊……
• 6 點，遺憾離場。

可以說是大起大落了。不過還好，最后拿到了最近久違的兩個 AC。

T1

可以想到，假如一個子串（可以為空）兩邊的字符相同，那么翻轉這個子串，或者翻轉帶上兩邊字符的子串，得到的字符串完全相同。

進一步思考，加入我們有一個字符串形如 a#*&a~-^a （a 中間的是任意的字符），那么 a#*&a、a-^a 和 a#*&a~-^a 就會被重復計算。歸納可得，設字符串中某個字符出現了 \(n\) 次，那么重復計算的次數就是 \(\frac{(1 + n) n}{2}\) ——對于每個字母都是同理的。

所以，我們統(tǒng)計每個字母的出現次數（別忘了英文字母有 \(26\) 個啊喂——不然小心 10 pts），然后設字符串長度為 \(l\)，那么最終答案就是 \(\frac{(1+n)n}{2} + \sum_{i = 1}^{26}\frac{(1+n_i)n_i}{2}\)。

#include <bits/stdc++.h>
#define int long long
typedef long long ll;
const int N = 1e5+10;
ll ans;
std::string str;
int times[30];

signed main() {
  freopen("spring.in", "r", stdin);
  freopen("spring.out", "w", stdout);
  std::cin >> str;
  int n = str.size();
  str = " " + str;
  for (int i = 1; i <= n; i++) {
    times[str[i] - 'a' + 1]++;
  }
  ans = (1 + n) * n / 2;
  for (int i = 1; i <= 26; i++) {
    ans -= (1 + times[i]) * times[i] / 2;
  }
  std::cout << ans + 1 << '\n';
  return 0;
}

T2

首先，如果 \(a_1\) 被修改，那么就無可救藥了，因為根據規(guī)則，顯然 \(a_1\) 必須為 \(0\)。此外，如果 \(a_i\) 被修改，那么下標為 \(i\) 的因數和倍數的地方要受牽連。進一步分析可得，\(i\) 的最大的質因數的所有倍數都要被修改（\(i\) 本身除外）。可以用試除法對 \(i\) 分解質因數，時間復雜度 \(O(\sqrt{n})\)。

#include <bits/stdc++.h>
typedef long long ll;
const int N = 1e5+10;
int n, q;

int getMaxFactor(int x) {
  int ans = 0;
  for (int i = 2; i <= std::sqrt(x); i++) {
    while (x % i == 0) {
      ans = std::max(ans, i);
      x /= i;
    }
  }
  if (x > 1) {
    ans = std::max(ans, x);
  }
  return ans;
}

signed main() {
  freopen("summer.in", "r", stdin);
  freopen("summer.out", "w", stdout);
  std::cin >> n >> q;  
  while (q--) {
    int x;
    std::cin >> x;
    if (x == 1) {
      std::cout << "-1\n";
      continue;
    }
    int maxFactor = getMaxFactor(x);
    int ans = n / maxFactor - 1;
    std::cout << ans << '\n';
  }
  return 0;
}

T3

這題正解太難了，這里只討論可以得 50 pts 的反悔貪心做法。（aoao 太強了！）

設處理第 \(i\) 個位置的糖果需要的費用為 \(V_i\)，分多、少兩種情況討論：

1. 若少了，既可以花 \(X\) 費用解決，即 \(V_i = X\)，還可以向前面位置為 \(j\) 處要糖果，花費 \(Z|i-j|\) 費用，并且還要把之前的糖的貢獻減去，總費用為 \(Z|i-j|-V_j\)，所以 \(V_i = \min(X, Z|i-j|-V_j)\)。
2. 若多了，同理，\(V_i = \min(Y, Z|i-j|-V_j)\)。

此時時間復雜度是 \(O(n^2)\)，但對于拿 50 分顯然還不夠，考慮優(yōu)化。

我們可以拆貢獻：

可見，要讓 \(V_i\) 最小，我們需要讓 \((-jZ - V_j)\) 最小。

可以開兩個小根堆，一個存本來少了糖的單位糖的 \((-jZ-V_j)\)，可以用來更新現在糖果多了的地方；另一個存本來多了單位糖的 \((-jZ-V_j)\)，可以用來更新現在多了糖果的地方。得到處理當前糖果的費用后把 \((-iZ-V_i)\) 存進堆里，供后面的答案更新。

時間復雜度為 \(O(n\log n)\)。

以上內容基本賀自洛谷題解。

#include <bits/stdc++.h>
typedef long long ll;
const int N = 5e5+10;
int n, x, y, z, a[N], b[N];
std::priority_queue<ll, std::vector<ll>, std::greater<ll> > more, less;
ll v[N], ans;

signed main() {
  freopen("autumn.in", "r", stdin);
  freopen("autumn.out", "w", stdout);
  std::ios::sync_with_stdio(false);
  std::cin >> n >> x >> y >> z;
  for (int i = 1; i <= n; i++) {
    std::cin >> a[i] >> b[i];
    for (int j = 1; j <= a[i] - b[i]; j++) {
      v[i] = y;
      if (!more.empty()) {
        v[i] = std::min(v[i], i * z + more.top());
        more.pop();
      }
      less.push(-v[i] - i * z);
      ans += v[i];
    }
    for (int j = 1; j <= b[i] - a[i]; j++) {
      v[i] = x;
      if (!less.empty()) {
        v[i] = std::min(v[i], i * z + less.top());
        less.pop();
      }
      more.push(-v[i] - i * z);
      ans += v[i];
    }
  }
  std::cout << ans << '\n';
  return 0;
}

總結

這次考試最大的經驗就是沒有被看似困難的題面打倒，而是沉住心分析問題的本質。如果我上周六能有這樣的態(tài)度，就肯定不會 T2 空著了。

當然，比較高級的東西還要多學（向隔壁學 OI 兩個月就學會了 Dijkstra 的 hiphop 大神學習），爭取拿更多分！