由于人太菜，所以只做了前两道。
A.能量水晶 crystal
简化题意：进行 \(m\) 次加 \(1\) 操作，最大化相同元素的数量。
很容易想到，这 \(m\) 次操作一定会被加到大小相邻的元素上面，且最终每个元素为这些元素中的最大值。因此，对于递增序列 \(\{a\}\)，能够判断区间 \([l,r]\) 中的元素是否能通过 \(m\) 次操作变得相等，即
\[\sum_{i=l}^{r}a_i-a_r\times(r-l+1)\le m \Longleftrightarrow \text{can equal}
\]
枚举区间的代价是 \(n^2\) 的，显然不能通过，因此二分答案并且利用前缀和解决。
#include
using namespace std;
int n;
long long m, a[500100], sum[500100];
bool check(int x) {for (int i = 1; i <= n - x + 1; i ++ )if (a[i + x - 1] * x - (sum[i + x - 1] - sum[i - 1]) <= m) return true;return false;
}
int main() {cin >> n >> m;for (int i = 1; i <= n; i ++ ) cin >> a[i];sort(a + 1, a + n + 1);for (int i = 1; i <= n; i ++ ) sum[i] = sum[i - 1] + a[i];int l = 1, r = n, ans = -1;while (l <= r) {int mid = (l + r) >> 1;if (check(mid)) ans = mid, l = mid + 1;else r = mid - 1;}cout << ans ;return 0;
}
B.地铁 subway
简化题意：在地铁口、站厅、站台之间步行行走，不同的地铁线路连接不同站台，最小化每次询问的步行时间。根据题目可知
但是在每个地铁线路的站台之间穿行并不增加步行时间。则可以把图改为这样
因此如果我们想要查询地铁口 \(u\) 到 \(v\) 的最短步行时间，就可以写为站厅 \(u\) 到线路 \(a\)、线路 \(a\) 到线路 \(b\)、线路 \(b\) 到站厅 \(v\) 以及各地铁口到站厅的步行时间之和。
其中由于每个地铁站最多会有 \(d\) 条线路经过，则可以枚举线路 \(a\) 和线路 \(b\)，这样的代价是 \(d^2\) 的。
对于线路 \(a\) 到线路 \(b\) 的步行时间 \(d_{a,b}\)，如果它们均经过同一个站厅（地铁站），那么 \(d_{a,b}=\min\{t_{u,a}+t_{u,b}\}\)；否则跑一遍全源最短路即可，时间复杂度为 \(O(md^2+n^3)\)
则总体的时间复杂度为 \(O(md^2+n^3+qd^2)\) 的。
#include
using namespace std; constexpr int maxn = 5e5 + 7;
constexpr long long inf = 1e14 + 7;
int c, n, m, d, q;
long long w[maxn], mp[510][510];
vector> t[maxn]; int main() {
cin >> c >> n >> m >> d >> q;
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ ) mp[i][j] = inf;
for (int i = 1; i <= n; i ++ ) mp[i][i] = 0;
for (int i = 1; i <= m; i ++ ) cin >> w[i];
for (int i = 1, k; i <= n; i ++ ) {
cin >> k;
for (int j = 1, x, tim; j <= k; j ++ ) {
cin >> x >> tim;
t[x].push_back(make_pair(i, tim));
}
}
for (int i = 1; i <= m; i ++ ) {
for (int j = 0; j < t[i].size(); j ++ )
for (int k = j + 1; k < t[i].size(); k ++ ) {
int u = t[i][j].first, v = t[i][k].first;
long long w = t[i][j].second + t[i][k].second;
if (mp[u][v] > w) mp[u][v] = mp[v][u] = w;
}
}
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ ) mp[i][j] = min(mp[i][j], mp[i][k] + mp[k][j]);
for (int i = 1, u, v; i <= q; i ++ ) {
cin >> u >> v;
long long res = inf;
for (int j = 0; j < t[u].size(); j ++ )
for (int k = 0; k < t[v].size(); k ++ ) {
res = min(res, t[u][j].second + t[v][k].second + mp[t[u][j].first][t[v][k].first]);
}
cout << res + w[u] + w[v] << '\n';
}
return 0;
}