Codeforces Round 980 (Div. 2)

• 写在前面
• A 签到
• B 贪心，模拟
• C 贪心，结论，思维
• D 图论转化，最短路
• 写在最后

写在前面

比赛地址：https://codeforces.com/contest/2030。

赛时被 B 硬控 1h，后面两题一眼秒了一共写了 20min 呃呃。

还好是小号。

A 签到

讨论一下很容易算出来最优决策。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
//=============================================================
//=============================================================
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    int a, b; std::cin >> a >> b;
    if (a >= b) {
      std::cout << a << "\n";
      continue;
    }

    int x = b - a;
    if (x > a) {
      std::cout << 0 << "\n";
    } else {
      std::cout << a - x << "\n";
    }
  }
  return 0;
}

B 贪心，模拟

显然要确定某个按钮对应的饮料数量，当且仅当按下这个按钮后没有获得新的饮料。

则可知最优的操作，是每次把当前未确定的按钮全按一遍。

于是考虑将 \(a_i\) 排序后模拟上述过程即可，在此过程中计算每轮按的数量以及该轮获得的饮料数量。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
const int kN = 2e5 + 10;
//=============================================================
LL n, k, a[kN];
//=============================================================
//=============================================================
int main() {
  // freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n >> k;
    std::map<int, int> cnt;
    for (int i = 1; i <= n; ++ i) std::cin >> a[i], ++ cnt[a[i]];

    LL ans = 0, cnt0 = 0, round = 0;
    for (auto [x, y]: cnt) {
      if (k <= 0) break;
      int t = std::min((LL) ceil(1.0 * k / (x - round)), n - cnt0);
      ans += t * (x - round), k -= t * (x - round);
      cnt0 += y, round = x;
      if (k <= 0) break;
      ans += y;
    }
    std::cout << ans + k << "\n";
  }
  return 0;
}

C 贪心，结论，思维

发现一组两个数内部的逆序对不受影响，只需要考虑每组之间的就行。

考虑将每组看成二维平面上的点，发现逆序对最小时应该让这些点满足 \(x+y\) 递增即可。

正确性显然，讨论一下两个点之间的两维关系即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pii std::pair<int,int>
#define mp std::make_pair
const int kN = 2e5 + 10;
//=============================================================
int n;
struct Data {
  int sum, x, y;
} a[kN];
//=============================================================
bool cmp(Data fir_, Data sec_) {
  return fir_.sum < sec_.sum;
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n;
    for (int i = 1; i <= n; ++ i) {
      int x, y; std::cin >> x >> y;
      a[i] = (Data) {x + y, x, y};
    }
    std::sort(a + 1, a + n + 1, cmp);
    for (int i = 1; i <= n; ++ i) std::cout << a[i].x << " " << a[i].y << " ";
    std::cout << "\n";
  }
  return 0;
}

D 图论转化，最短路

发现这个人的策略一定是不断地重复往前做一段题，然后往后跳。在此过程中的价值之和，即到达的最远的位置 \(i\) 的价值的前缀和 \(\operatorname{sum}_i\)，减去选择跳的位置的权值之和。

考虑枚举每一个到达的最远的位置 \(i\)，并最小化跳的位置的权值之和，考虑建边 \(i\rightarrow b_i, i\operatorname{i - 1}\)，发现这等价于最小化到达每个位置 \(i\) 的最短路 \(\operatorname{dis}_i\)。

于是建图后跑最短路，对于能到达的点取 \(\operatorname{sum}_i -\operatorname{dis}_i\) 的最大值即可。

//
/*
By:Luckyblock
*/
#include <bits/stdc++.h>
#define LL long long
#define pr std::pair
#define mp std::make_pair
const int kN = 4e5 + 10;
const LL kInf = 1e18;
//=============================================================
int n, a[kN], b[kN]; 
LL sum[kN], dis[kN];
bool vis[kN];
std::vector<pr <int, int> > edge[kN];
//=============================================================
void Dijkstra() {
  std::priority_queue<pr <LL, int> > q;
  for (int i = 1; i <= n; ++ i) {
    dis[i] = kInf; 
    vis[i] = 0;
  }
  dis[1] = 0;
  q.push(mp(0, 1));

  while (!q.empty()) {
    int u = q.top().second; q.pop();
    if (vis[u]) continue;
    vis[u] = 1;
    for (auto [v, w]: edge[u]) {
      if (dis[v] > dis[u] + w) {
        dis[v] = dis[u] + w;
        q.push(mp(-dis[v], v));
      }
    }
  }
}
//=============================================================
int main() {
  //freopen("1.txt", "r", stdin);
  std::ios::sync_with_stdio(0), std::cin.tie(0);
  int T; std::cin >> T;
  while (T --) {
    std::cin >> n;
    for (int i = 1; i <= n; ++ i) {
      std::cin >> a[i], sum[i] = sum[i - 1] + a[i];
      edge[i].clear();
    }
    for (int i = 1; i <= n; ++ i) {
      std::cin >> b[i];
      if (b[i] > i) edge[i].push_back(mp(b[i], a[i]));
      if (i > 1) edge[i].push_back(mp(i - 1, 0));
    }
    Dijkstra();
    LL ans = 0;
    for (int i = 1; i <= n; ++ i) {
      if (dis[i] < kInf) ans = std::max(ans, sum[i] - dis[i]);
    }
    std::cout << ans << "\n";
  }
  return 0;
}

写在最后

我是傻逼。