20240902

libohan / 2024-09-25 / 原文

Room Temperature

我们首先可以发现他的初始适宜温度是无关紧要的(因为我们可以让他穿非常多的衣服,然后后续的操作就等于脱衣服),然后我们将数组统一模 $T$,再排序,假设现在我们考虑第 $i$ 个人,那么一定可以通过脱衣服,让温度在 $a[i]$ 至 $a[i - 1] + t$ 内,然后我们要注意 $i = 1$ 那么就是 $a[1]$ 至 $a[n]$ 之内

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 1e7 + 5;

int n, t, a[N], ans = 1e18;

signed main() {
  cin >> n >> t;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
    a[i] %= t;
  }
  sort(a + 1, a + n + 1);
  for (int i = 1; i <= n; i++) {
    a[i + n] = a[i] + t;
  }
  for (int i = 1; i <= n; i++) {
    int tmp = (a[i] + a[i + n - 1] + 1) / 2;
    ans = min(ans, max(tmp - a[i], a[i + n - 1] - tmp));
  }
  cout << ans;
  return 0;
}

Construction Project 2

首先假如最短路已经满足要求了,那么就可以直接输出即可,接下来猜一个结论架设我们只要统计对于一个点来说的 $dis[1][a] + l + dis[b][n] <= k$ 的个数和就是答案,那么有一个问题就是如果有一条边使得 $dis[1][b] + l + dis[a][n] <= k$ 怎么办,如果按照以上方法就会统计两遍,假设如果 $dis[1][b] != dis[1][a] + l$ 那么 $dis[1][a] + l + dis[b][n] <= dis[1][b] + dis[b][n]$ 也就是说 $dis[1][n] <= k$ 那么就和最开始的条件矛盾了,然而假如 $dis[1][b] = dis[1][a] + l$ 那么, $dis[1][a] + l + l + dis[a][n] <= k$ 那么也与最初条件矛盾,所以也就是说如果 $dis[1][a] + l + dis[b][n] <= k$ 和 $dis[1][b] + l + dis[a][n] <= k$ 中只会有一个满足条件,所以直接从 $1$ 和 $n$ 分别跑一次再做一个双指针即可

#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 2e5 + 5;

struct node {
  int v, w;
};

struct F {
  int d, v;
  bool operator < (const F &_y) const {
    return d > _y.d;
  }
};

int n, m, s, t, l, k, dis[2][N], ans;

vector<node> g[N];

void dij(int x, int op) {
  priority_queue<F> q;
  q.push({0, x});
  dis[op][x] = 0;
  while (!q.empty()) {
    if (dis[op][q.top().v] < q.top().d) {
      q.pop();
      continue;
    }
    F cur = q.top();
    q.pop();
    for (auto e : g[cur.v]) {
      int v = e.v, w = e.w;
      if (dis[op][v] > dis[op][cur.v] + w) {
        dis[op][v] = dis[op][cur.v] + w;
        q.push({dis[op][v], v});
      }
    }
  }
}

signed main() {
  cin >> n >> m >> s >> t >> l >> k;
  for (int i = 1, u, v, w; i <= m; i++) {
    cin >> u >> v >> w;
    g[u].push_back({v, w});
    g[v].push_back({u, w});
  }
  memset(dis, 0x3f, sizeof(dis));
  dij(s, 0);
  dij(t, 1);
  if (dis[0][t] <= k) {
    cout << (n * (n - 1)) / 2 << "\n";
    return 0;
  }
  sort(dis[0] + 1, dis[0] + n + 1);
  sort(dis[1] + 1, dis[1] + n + 1);
  for (int i = 1, j = n; i <= n; i++) {
    while (j >= 1 && dis[0][i] + dis[1][j] + l > k) {
      j--;
    }
    ans += j;
  }
  cout << ans;
  return 0;
}

Marathon Race 2

我们可以把拿球改为放球,那么我们可以得出一个结论:放球时能放就放(当然终点与起点也会放球)
先考虑 $n <= 2500$ 时的做法,我们可以想到一个区间 $dp$ 的状态, $dp[i][j][0/1]$ 表示当前所在的区间,当前站在左端点还是右端点.但是不难发现这样设计会有一个缺陷,那就是当起点并不在一个球上时无法考虑