2024/10/03

\(100+20+0+55=175\)，T4 数组开小挂了 \(45\)，T3 暴力写挂挂了 \(20\)

#A. 旋律的总数

这真的是提高组的题吗

不考虑同构有 \(m^n\) 种排法，一种同构的排法可以偏移 \(m\) 次，直接相除得到答案 \(m^{n-1}\)

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const LL kP = 1e9 + 7;

LL t, n, m, ans;

LL P(LL x, LL y, LL ret = 1) {
  for (; y; (y & 1) && ((ret *= x) %= kP), (x *= x) %= kP, y >>= 1) {
  }
  return ret;
}

int main() {
  freopen("sum.in", "r", stdin), freopen("sum.out", "w", stdout);
  for (cin >> t; t; t--) {
    cin >> n >> m;
    cout << P(m, n - 1) << '\n';
  }
  return 0;
}

#B. 水果加工

二分答案，二分时间限制 \(T\)，在限制下跑背包即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int kMaxN = 50 + 5;

int n, a[kMaxN], m[3], c[3][kMaxN];
LL d[3][kMaxN], u[3][kMaxN], ans, dp[kMaxN][kMaxN][kMaxN], p;

LL Calc(LL x) {
  for (int i = 0; i <= n; i++) {
    for (int l = 0; l <= m[1]; l++) {
      for (int r = 0; r <= m[2]; r++) {
        dp[i][l][r] = (i == 0 ? 0 : 1e18);
      }
    }
  }
  dp[0][0][0] = 0;
  for (int i = 1; i <= n; i++) {
    for (int j = 0; j <= a[i]; j++) {
      LL e = j, w = a[i] - j;
      if (e * d[1][i] > x || w * d[2][i] > x) {
        continue;
      }
      for (int l = 0; l <= m[1]; l++) {
        for (int r = 0; r <= m[2]; r++) {
          if (e == 0 && r >= c[2][i]) {
            dp[i][l][r] = min(dp[i][l][r], max(dp[i - 1][l][r - c[2][i]], w * u[2][i]));
          } else if (w == 0 && l >= c[1][i]) {
            dp[i][l][r] = min(dp[i][l][r], max(dp[i - 1][l - c[1][i]][r], e * u[1][i]));
          } else if (l >= c[1][i] && r >= c[2][i]) {
            dp[i][l][r] = min(dp[i][l][r], max({dp[i - 1][l - c[1][i]][r - c[2][i]], e * u[1][i], w * u[2][i]}));
          }
        }
      }
    }
  }
  return dp[n][m[1]][m[2]];
}

int main() {
  freopen("fruit.in", "r", stdin), freopen("fruit.out", "w", stdout);
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  cin >> m[1] >> m[2];
  for (int i = 1; i <= n; i++) {
    cin >> c[1][i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> c[2][i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> d[1][i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> d[2][i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> u[1][i];
  }
  for (int i = 1; i <= n; i++) {
    cin >> u[2][i];
  }
  for (ans = 1e11; p < 1e11;) {
    LL l = p, r = 1e18, o = Calc(l);
    for (ans = min(ans, l + o); l + 1 < r;) {
      LL mid = (l + r) >> 1, A = Calc(mid);
      (A == o) ? (l = mid, o = A) : (r = mid);
    }
    p = l + 1;
  }
  cout << ans << '\n';
  return 0;
}

#C. 最佳位置

直接开两个 set 维护，一个按照段长排序，一个按照编号排序，直接二分查找维护即可

代码还在调，咕咕咕

#D. 跑步路线

MST + LCA 例题，边权不同，所以最小生成树唯一，那么路径是固定的。按顺序枚举要达到的相邻两点，用 LCA 维护两点之间距离即可

// BLuemoon_
#include <bits/stdc++.h>

using namespace std;
using LL = long long;
#define int __int128_t

const int kMaxN = 2e5 + 5, kMaxM = 1e6 + 5, kL = 18 + 2;

struct E {
  int u, v;
  __int128_t w;
  bool operator<(const E &o) const {
    return w < o.w;
  }
};

int n, m, k, e[kMaxM], fa[kMaxN], tot, f[kMaxN][kL];
LL tmp_t;
__int128_t t, dis[kMaxN], ans, d[kMaxN];
vector<pair<int, __int128_t>> g[kMaxN];
E r[kMaxM];

int F(int x) { return fa[x] == x ? x : fa[x] = F(fa[x]); }
void DFS(int u, int fa) {
  f[u][0] = fa, d[u] = d[fa] + 1;
  for (auto i : g[u]) {
    LL v = i.first, w = i.second;
    if (v != fa) {
      dis[v] = dis[u] + w, DFS(v, u);
    }
  }
}
void Init() {
  for (int i = 1; i < kL; i++) {
    for (int j = 1; j <= n; j++) {
      f[j][i] = f[f[j][i - 1]][i - 1];
    }
  }
}
int LCA(int x, int y) {
  if (d[x] < d[y]) {
    swap(x, y);
  }
  for (int i = kL - 1; ~i; i--) {
    (d[f[x][i]] >= d[y]) && (x = f[x][i]);
  }
  if (x == y) {
    return x;
  }
  for (int i = kL - 1; ~i; i--) {
    (f[x][i] != f[y][i]) && (x = f[x][i], y = f[y][i]);
  }
  return f[x][0];
}
void print(__int128_t x) {
  if (x > 9) {
    print(x / 10);
  }
  putchar(x % 10 + 48);
}

signed main() {
  freopen("run.in", "r", stdin), freopen("run.out", "w", stdout);
  cin >> tmp_t, n = tmp_t, cin >> tmp_t, m = tmp_t;
  for (int i = 1, u, v, w; i <= m; i++) {
    cin >> tmp_t, u = tmp_t;
    cin >> tmp_t, v = tmp_t;
    cin >> tmp_t, w = tmp_t;
    r[i] = (E){u, v, w};
  }
  cin >> tmp_t, k = tmp_t;
  cin >> tmp_t, t = tmp_t;
  for (int i = 1; i <= k; i++) {
    cin >> tmp_t, e[i] = tmp_t;
  }
  for (int i = 1; i <= n; i++) {
    fa[i] = i;
  }
  sort(r + 1, r + m + 1);
  for (int i = 1; i <= m; i++) {
    if (F(r[i].u) != F(r[i].v)) {
      tot++, g[r[i].u].push_back({r[i].v, r[i].w}), g[r[i].v].push_back({r[i].u, r[i].w});
      fa[F(r[i].u)] = F(r[i].v);
    }
    if (tot == n - 1) {
      break;
    }
  }
  d[1] = 1, DFS(1, 0);
  Init();
  for (int i = 1; i < k; i++) {
    if (e[i + 1] == e[i]) {
      continue;
    }
    int l = LCA(e[i], e[i + 1]);
    ans += t * (d[e[i]] + d[e[i + 1]] - d[l] - d[l]);
    ans += dis[e[i]] + dis[e[i + 1]] - dis[l] - dis[l];
  }
  print(ans - t), cout << '\n';
  return 0;
}