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_tconst 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;
}