AtCoder Beginner Contest 188

A，B很简单就不多说

C - ABC Tournament

找出前一半的最大值和后一半的最大值，二者中较小的那一个对应的序号就是最后的答案。

时间复杂度：AtCoder Beginner Contest 188 题解 - 图1#card=math&code=%5Cmathcal%7BO%7D%282%5EN%29)

  1. using ll = long long;
  2. int main() {
  3.     ios_base::sync_with_stdio(false), cin.tie(0);
  4.     ll a[70000];
  5.     int n;
  6.     cin >> n, n = pow(2, n);
  7.     for (int i = 0; i < n; ++i) cin >> a[i];
  8.     ll m1 = a[0], idx = 0;
  9.     for (int i = 1; i < n / 2; ++i)
  10.         if (a[i] > m1) m1 = a[i], idx = i;
  11.     ll m2 = a[n / 2], idxx = n / 2;
  12.     for (int i = n / 2 + 1; i < n; ++i)
  13.         if (a[i] > m2) m2 = a[i], idxx = i;
  14.     cout << (m1 < m2 ? idx + 1 : idxx + 1) << "\n";
  15.     return 0;
  16. }

D - Snuke Prime

时间复杂度：AtCoder Beginner Contest 188 题解 - 图2#card=math&code=%5Cmathcal%7BO%7D%28N%29)

  1. using ll = long long;
  2. int main() {
  3.     ios_base::sync_with_stdio(false), cin.tie(0);
  4.     ll N, C;
  5.     cin >> N >> C;
  6.     vector<pair<ll, ll>> event;
  7.     for (ll i = 0; i < N; ++i) {
  8.         ll a, b, c;
  9.         cin >> a >> b >> c;
  10.         event.push_back({a - 1, c});
  11.         event.push_back({b, -c});
  12.     }
  13.     sort(event.begin(), event.end());
  14.     ll ans = 0, fee = 0, time = 0;
  15.     for (auto [x, y] : event) {
  16.         if (x != time) {
  17.             ans += min(C, fee) * (x - time);
  18.             time = x;
  19.         }
  20.         fee += y;
  21.     }
  22.     cout << ans << "\n";
  23.     return 0;
  24. }

E - Peddler

题意：N 个城镇，每个镇子购买和卖出 AtCoder Beginner Contest 188 题解 - 图3 黄金的价格是 AtCoder Beginner Contest 188 题解 - 图4 ，现在可以我们有 Ｍ条道路，问怎么才能获得最大收益

思路：虽然看过去需要搜索做，但这里只要逆向动态规划即可。

  1. int main() {
  2.     ios_base::sync_with_stdio(false), cin.tie(0);
  3.     int N, M;
  4.     cin >> N >> M;
  5.     vector<int> A(N + 1);
  6.     for (int i = 1; i <= N; ++i) cin >> A[i];
  8.     vector<vector<int>> e(N + 1);
  9.     for (int i = 0; i < M; ++i) {
  10.         int u, v;
  11.         cin >> u >> v;
  12.         // e[u].emplace_back(v), e[v].emplace_back(u);
  13.         e[u].emplace_back(v);  // 这里单向和双向都没什么区别
  14.     }
  16.     vector<int> h(N + 1, -1e9);
  17.     int ans = -1e9;
  18.     for (int i = N; i > 0; --i) {
  19.         for (auto v : e[i]) h[i] = max(h[i], h[v]);
  20.         ans = max(ans, h[i] - A[i]);
  21.         h[i] = max(h[i], A[i]);
  22.     }
  23.     cout << ans << "\n";
  24.     return 0;
  25. }

F - +1-1x2

  • 如果 AtCoder Beginner Contest 188 题解 - 图5 ，则答案为AtCoder Beginner Contest 188 题解 - 图6
  • 如果 AtCoder Beginner Contest 188 题解 - 图7 ，则可以考虑用ＤＦＳ，详细可以看代码
  1. using ll = long long;
  2. ll x, y, ans = 1e18;
  3. map<ll, ll> mp;
  4. ll dfs(ll a) {
  5.     if (mp.count(a)) return mp[a];
  6.     if (a <= x) return x - a;
  7.     if (a & 1)
  8.         return mp[a] = min(min(dfs((a + 1) / 2), dfs((a - 1) / 2)) + 2, a - x);
  9.     else
  10.         return mp[a] = min(dfs(a / 2) + 1, a - x);
  11. }
  12. int main() {
  13.     cin >> x >> y;
  14.     cout << dfs(y);
  15. }