雅礼信奥 \(2023.11.22\) 习题课记录（讲解版）

都是 CF 题，不如 AT。

剧情版后面会更。

A - Yarik and Array（CF1899C）

dp 题，作为学 OI \(3\) 年的萌新 OIer，后面才想到 dp 真是太蒟蒻了，时间复杂度 \(O(tn)\)。

初始 \(f_1 = 1\)，其他为 \(0\)。

状态转移方程：

\(\begin{cases} \text{if} & \text{abs}(a_{i - 1}) \bmod 2 + \text{abs}(a_i) \bmod 2 = 1 & f_i = \max(a_i,\ f_{i - 1} + a_i) \\ \text{if} & \text{abs}(a_{i - 1}) \bmod 2 + \text{abs}(a_i) \bmod 2 \neq 1 & f_i = a_i \end{cases}\)

\(\max(f_1, f_2, \cdots, f_n)\) 即为答案。

罚时 \(1\) 次。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>

using namespace std;

using ll = long long;

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;

ll n, a[kMaxN], f[kMaxN], ans = 0;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
      f[i] = 0;
    }
    f[1] = a[1];
    ans = f[1];
    for (int i = 2; i <= n; ++ i) {
      if (abs(a[i - 1]) % 2 + abs(a[i]) % 2 == 1) {
        f[i] = max(a[i], f[i - 1] + a[i]);
        ans = max(ans, f[i]);
      } else {
        f[i] = a[i];
        ans = max(ans, f[i]);
      }
    }
    cout << ans << '\n';
  }
  return 0;
}

B - Game with Integers（CF1899A）

一眼题 + 面向样例题，\(n \bmod 3 = 0\) 输出 Second，否则 First，时间复杂度 \(O(t)\)。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>

using namespace std;

using ll = long long;

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;

int x;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> x;
    cout << (!(x % 3)? "Second" : "First") << '\n';
  }
  return 0;
}

C - 250 Thousand Tons of TNT（CF1899B）

枚举题。

首先，\(k\) 必定是 \(n\) 的因数，所以我们只需要枚举 \(n\) 的因数即可，时间复杂度不确定，好像是 \(O(tn\sqrt{n})\)。

罚时 \(3\) 次，因为不开 long long 见祖宗。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>

using namespace std;

using ll = long long;

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;

ll n, a[kMaxN], b[kMaxN], idx = 0, mini = 1e18, maxa = -1e18, ans = -1e18, sum = 0;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n;
    idx = 0, ans = -1e18;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
    }
    for (ll i = 1; i * i <= n; ++ i) {
      if (n % i) {
        continue;
      }
      b[++ idx] = n / i;
      mini = 1e18, maxa = -1e18;
      for (ll j = 1; j <= n; ++ j) {
        sum += a[j];
        if (!(j % i)) {
          mini = min(mini, sum);
          maxa = max(maxa, sum);
          sum = 0;
        }
      }
      ans = max(ans, maxa - mini);
    }
    sum = 0;
    for (ll i = 1; i <= idx; ++ i) {
      mini = 1e18, maxa = -1e18;
      for (ll j = 1; j <= n; ++ j) {
        sum += a[j];
        if (!(j % b[i])) {
          mini = min(mini, sum);
          maxa = max(maxa, sum);
          sum = 0;
        }
      }
      ans = max(ans, (b[i] == n? 0 : maxa - mini));
    }
    cout << ans << '\n';
  }
  return 0;
}

D - Yarik and Musical Notes（CF1899D）

成为一个合法的一对 \((i, j)\) 必须满足 \(a_i = a_j\) 或 \(a_i = 1\)，\(a_j = 2\) 或 \(a_i = 2\)，\(a_j = 1\)，所以我们建立一个哈希表 \(mp\)（一定要开 map，unoredered_map 被卡了！），如果 \(a_i = 1\)，答案加 \(mp_2\)，如果 \(a_i = 2\)，答案加 \(mp_1\)，然后每次答案加 \(mp_{a_i}\)。时间复杂度 \(O(n)\)。

罚时 \(5\) 次，因为 unoredered_map 啊啊啊啊啊！

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <unordered_map>

using namespace std;

using ll = long long;

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;

ll n, a[kMaxN], ans = 0; 

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    unordered_map<ll, ll> mp;
    ans = 0;
    cin >> n;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];  
      if (a[i] == 1) {
        ans += mp[2];
      }
      if (a[i] == 2) {
        ans += mp[1];
      }
      ans += mp[a[i]];
      ++ mp[a[i]];
    }
    cout << ans << '\n';
  }
  return 0;
}

E - Treasure Chest（CF1895A）

分类讨论题，只需稍微推一下就可以。

\(\begin{cases} \text{if} & x > y & x \\ \text{if} & x < y \text{ and } y - (k + x) \ge 0 & y \\ \text{if} & x < y \text{ and } y - (k + x) < 0 & x + k + (y - (k + x) \times 2) \end{cases}\)

当初还以为是搜索。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>

using namespace std;

using ll = long long;

const int kMaxN = -1, kInf = (((1 << 30) - 1) << 1) + 1;

int x, y, k;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> x >> y >> k;
    if (x > y) {
      cout << x << '\n';
    } else {
      if (y - (k + x) <= 0) {
        cout << y << '\n';
      } else {
        cout << x + k + (y - (k + x) << 1) << '\n';
      }
    }
  }
  return 0;
}

F - Queue Sort（CF1899E）

首先，我们定义一个 \(ans\) （存最小值）和 \(cnt\)（用来记录答案）。每次把 \(ans\) 赋值为 \(10^{18}\)，\(cnt\) 赋值为 \(0\)。遍历一遍数组，\(cnt\) 记录最小值的下标。如果 \([cnt + 1, n]\) 区间内有 \(a_i < a_{i - 1}\) 的情况，输出 \(-1\)，否则输出 \(cnt - 1\)。

罚时 \(1\) 次。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <stack>

using namespace std;

using ll = long long;

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;

ll n, a[kMaxN], ans = 1e18, cnt = 0;

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    cin >> n;
    ans = 1e18, cnt = 0;
    for (int i = 1; i <= n; ++ i) {
      cin >> a[i];
      if (a[i] < ans) {
        ans = a[i];
        cnt = i;
      }
    }
    for (int i = cnt + 1; i <= n; ++ i) {
      if (a[i] < a[i - 1]) {
        cnt = -1;
      }
    }
    cout << (cnt == -1? -1 : cnt - 1) << '\n';
  }
  return 0;
}

G - Points and Minimum Distance（CF1895B）

当初还以为是最短路，所以放在后面，结果发现 G 好简单。

将输入的数据排好序，然后遍历 \([1, n - 1]\)，每次把距离加 \(\text{abs}(a_i - a_{i + 1}) + \text{abs}(a_{i + n} - a_{i + n + 1})\)，遍历完后输出。然后我们定义两个指针 \(i, j\)，\(i = 1\)，\(j = n \times 2\)，每次 \(i\) 加 \(1\)，\(j\) 减 \(1\)，\(a_i, a_j\) 即是我们要输出的坐标。

#include <iostream>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <vector>

using namespace std;

using ll = long long;

const int kMaxN = 2e5 + 20, kInf = (((1 << 30) - 1) << 1) + 1;

ll n, ans = 0, a[kMaxN];

int main() {
  ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
  int t;
  for (cin >> t; t; -- t) {
    ans = 0;
    cin >> n;
    for (int i = 1; i <= (n << 1); ++ i) {
      cin >> a[i];
    }
    sort(a + 1, a + (n << 1) + 1);
    for (int i = 1; i <= n - 1; ++ i) {
      ans += labs(a[i] - a[i + 1]) + labs(a[i + n] - a[i + n + 1]);
    }
    cout << ans << '\n';
    for (int i = 1, j = (n << 1); i <= j; ++ i, -- j) {
      cout << a[i] << ' ' << a[j] << '\n';
    }
  }
  return 0;
}

Thanks for your looking.