10.3 总结

T1

每一个数列有 \(m\) 种变式，而总共有 \(m^n\) 个数列，所以答案是 \(m^{n-1}\)，赛事 AC 了

#include <fstream>

using namespace std;
using ll = long long;

const ll kMod = 1e9 + 7;

ifstream cin("sum.in");
ofstream cout("sum.out");

ll t, n, m;

ll fpow(ll a, ll b) {
  ll res = 1;
  for (; b; res = b & 1 ? res * a % kMod : res, b >>= 1, a = a * a % kMod) {
  }
  return res % kMod;
}

int main() {
  for (cin >> t; t; t--) {
    cin >> n >> m;
    cout << fpow(m, n - 1) << '\n';
  }
  return 0;
}

T2

一道 DP 题，终点是如何对 dp 数组转移。

具体来讲，枚举可能的运输时间，再运输时间的限制下进行背包DP，时间复杂度 \(O(b^2(\sum a_i)^2)\)。

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <fstream>

using namespace std;

const int kMaxN = 50;

ifstream cin("fruit.in");
ofstream cout("fruit.out");

long long n, a[kMaxN], b[3], c[3][kMaxN], d[3][kMaxN], u[3][kMaxN], f[kMaxN][kMaxN][kMaxN][kMaxN][2], ans = 3e15;

int main() {
  cin >> n;
  for (int i = 1; i <= n; i++) {
    cin >> a[i];
  }
  cin >> b[1] >> b[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 (int i = 1; i <= n; i++) {
    for (int j = 0; j <= a[i]; j++) {
      for (int k = 0; k <= b[1]; k++) {
        for (int l = 0; l <= b[2]; l++) {
          f[i][j][k][l][0] = f[i][j][k][l][1] = 3e15;
        }
      }
    }
  }
  f[0][0][0][0][0] = f[0][0][0][0][1] = 0;
  for (int i = 0; i <= n; i++) {
    for (int j = 0; j <= a[i]; j++) {
      for (int k = 0; k <= b[1]; k++) {
        for (int l = 0; l <= b[2]; l++) {
          if (a[i + 1] == 0) {
            f[i + 1][j][k][l][0] = f[i][j][k][l][0];
            f[i + 1][j][k][l][1] = f[i][j][k][l][1];
            continue;
          }
          for (int p = 0; p <= a[i + 1]; p++) {
            long long tmp = max(f[i][j][k][l][0], max(d[2][i + 1] * (a[i + 1] - p), d[1][i + 1] * p)) + max(f[i][j][k][l][1], max(u[2][i + 1] * (a[i + 1] - p), u[1][i + 1] * p));
            if (p == 0) {
              if (tmp < f[i + 1][p][k][l + c[2][i + 1]][0] + f[i + 1][p][k][l + c[2][i + 1]][1]) {
                f[i + 1][p][k][l + c[2][i + 1]][0] = max(f[i][j][k][l][0], max(d[2][i + 1] * (a[i + 1] - p), d[1][i + 1] * p));
                f[i + 1][p][k][l + c[2][i + 1]][1] = max(f[i][j][k][l][1], max(u[2][i + 1] * (a[i + 1] - p), u[1][i + 1] * p));
              }
            } else if (p == a[i + 1]) {
              if (tmp < f[i + 1][p][k + c[1][i + 1]][l][0] + f[i + 1][p][k + c[1][i + 1]][l][1]) {
                f[i + 1][p][k + c[1][i + 1]][l][0] = max(f[i][j][k][l][0], max(d[2][i + 1] * (a[i + 1] - p), d[1][i + 1] * p));
                f[i + 1][p][k + c[1][i + 1]][l][1] = max(f[i][j][k][l][1], max(u[2][i + 1] * (a[i + 1] - p), u[1][i + 1] * p));
              }
            } else {
              if (tmp < f[i + 1][p][k + c[1][i + 1]][l + c[2][i + 1]][0] + f[i + 1][p][k + c[1][i + 1]][l + c[2][i + 1]][1]) {
                f[i + 1][p][k + c[1][i + 1]][l + c[2][i + 1]][0] = max(f[i][j][k][l][0], max(d[2][i + 1] * (a[i + 1] - p), d[1][i + 1] * p));
                f[i + 1][p][k + c[1][i + 1]][l + c[2][i + 1]][1] = max(f[i][j][k][l][1], max(u[2][i + 1] * (a[i + 1] - p), u[1][i + 1] * p));
              }
            }
          }
        }
      }
    }
  }
  for (int j = 0; j <= a[n]; j++) {
    for (int k = 0; k <= b[1]; k++) {
      for (int l = 0; l <= b[2]; l++) {
        ans = min(ans, f[n][j][k][l][0] + f[n][j][k][l][1]);
      }
    }
  }
  cout << ans;
  return 0;
}

T3

T4

一道 Kruskal加上LCA的题目，超级缝合怪，出题人还卡long long ，所以要用 int128。

#include <algorithm>
#include <fstream>
#include <vector>

using namespace std;
using ll = long long;
using i128 = __int128;

const ll kMaxN = 2e5 + 1;

ifstream cin("run.in");
ofstream cout("run.out");

int n, m, k, t0, ans, fat[kMaxN];
struct Side {
  ll u, v, w;
} s[kMaxN];
struct Node {
  int f[20], d;
  i128 s;
  vector<pair<int, ll>> e;
} v[kMaxN];

int Find(int x) {
  return fat[x] = fat[x] == x ? x : Find(fat[x]);
}

void Walk(int x, int fa) {
  v[x].d = v[fa].d + 1, v[x].f[0] = fa;
  for (auto i : v[x].e) {
    ll y = i.first, z = i.second;
    if (y != fa) {
      v[y].s = v[x].s + z;
      Walk(y, x);
    }
  }
}

void CalcF() {
  for (ll j = 1; j < 20; j++) {
    for (ll i = 1; i <= n; i++) {
      v[i].f[j] = v[v[i].f[j - 1]].f[j - 1];
    }
  }
}

ll LCA(ll x, ll y) {
  if (v[x].d < v[y].d) {
    swap(x, y);
  }
  for (ll i = 19; i >= 0; i--) {
    if (v[v[x].f[i]].d >= v[y].d) {
      x = v[x].f[i];
    }
  }
  if (x == y) {
    return x;
  }
  for (ll i = 19; i >= 0; i--) {
    if (v[x].f[i] != v[y].f[i]) {
      x = v[x].f[i], y = v[y].f[i];
    }
  }
  return v[x].f[0];
}

ll Len(ll x, ll y) {
  return v[x].d + v[y].d - 2 * v[LCA(x, y)].d - 1;
}

i128 Dis(ll x, ll y) {
  return v[x].s + v[y].s - 2 * v[LCA(x, y)].s;
}

void print(i128 x) {
  if (x >= 10) {
    print(x / 10);
  }
  cout.put(x % 10 + '0');
}

int main() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) {
    fat[i] = i;
  }
  for (int i = 1; i <= m; i++) {
    cin >> s[i].u >> s[i].v >> s[i].w;
  }
  // 最小生成树 begin
  sort(s + 1, s + m + 1, [](Side a, Side b) { return a.w < b.w; });
  for (int i = 1; i <= m; i++) {
    int x = s[i].u, y = s[i].v, w = s[i].w;
    int fx = Find(x), fy = Find(y);
    if (fx != fy) {
      fat[fy] = fx;
      v[x].e.push_back({y, w});
      v[y].e.push_back({x, w});
    }
  }
  // 最小生成树 end

  // LCA begin
  Walk(1, 0), CalcF();
  // LCA end

  // 回答 begin
  cin >> k >> t0;
  ll lst = 0;
  i128 ans = 0, cnt = 0;
  for (ll i = 1, x; i <= k; i++) {
    cin >> x;
    if (i != 1) {
      cnt += Len(lst, x);
      ans += Dis(lst, x);
    }
    cnt += (i != 1 && i != k);
    lst = x;
  }
  ans += cnt * t0;
  print(ans);
  return 0;
}