2023牛客暑期多校训练营6 ABCEG
- 作者: 五速梦信息网
- 时间: 2026年04月04日 13:53
A
题解
方法一
知识点：并查集，树形dp，背包dp。
因为需要路径中的最大值，因此考虑按边权从小到大加入图中，保证通过这条边产生贡献的点对已经全部出现。
在加边的同时进行树上背包，答案存在集合根节点里即可。
树上背包需要用到上下界限制的转移优化，能将复杂度从 (O(n^3)) 降到 (O(n^2)) ，基本思想是每个点对只在LCA处贡献一次。
时间复杂度 (O(n^2))
空间复杂度 (O(n^2))
方法二
知识点：Kruskal重构树，树形dp，背包dp。
对原图进行最小生成树性质的Kruskal重构，任意两点的LCA点权为路径最大值。
然后，在这棵重构树上进行dp，核心内容一致，区别在于原边权变为了点权，原子树大小变为叶子节点个数。
时间复杂度 (O(n^2))
空间复杂度 (O(n^2))
代码
方法一
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> fa;<br/>
vector<int> sz;
DSU(int n = 0) { init(n); }
void init(int n) {
fa.assign(n + 1, 0);<br/>
sz.assign(n + 1, 1);<br/>
iota(fa.begin(), fa.end(), 0);<br/>
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void merge(int x, int y) {
sz[y] += sz[x];<br/>
fa[find(x)] = find(y);<br/>
}<br/>
};
tuple<int, int, int> e[3007];
bool black[3007];
int cost[3007];
ll f[3007][3007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);<br/>
int n;<br/>
cin >> n;<br/>
for (int i = 1;i <= n;i++) cin >> black[i];<br/>
for (int i = 1;i <= n;i++) {<br/>
cin >> cost[i];<br/>
f[i][black[i]] = 0;<br/>
f[i][black[i] ^ 1] = -cost[i];<br/>
}<br/>
for (int i = 1;i <= n - 1;i++) {<br/>
int u, v, w;<br/>
cin >> u >> v >> w;<br/>
e[i] = { w,u,v };<br/>
}
sort(e + 1, e + n);
DSU dsu(n);<br/>
for (int i = 1;i <= n;i++) {<br/>
auto [w, u, v] = e[i];<br/>
u = dsu.find(u);<br/>
v = dsu.find(v);<br/>
vector<ll> g(n + 1, -1e18);<br/>
for (int j = 0;j <= dsu.sz[u];j++) {<br/>
for (int k = 0;k <= dsu.sz[v];k++) {<br/>
ll val = 1LL * (j * (dsu.sz[v] - k) + k * (dsu.sz[u] - j)) * w;<br/>
g[j + k] = max(g[j + k], f[u][j] + f[v][k] + val);<br/>
}<br/>
}<br/>
for (int j = 0;j <= dsu.sz[u] + dsu.sz[v];j++) f[u][j] = g[j];<br/>
dsu.merge(v, u);<br/>
}<br/>
ll ans = 0;<br/>
for (int i = 0;i <= n;i++) ans = max(ans, f[dsu.find(1)][i]);<br/>
cout << ans << '\n';<br/>
return 0;<br/>
}
方法二
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
struct DSU {
vector<int> fa;<br/>
vector<int> sz;
DSU(int n = 0) { init(n); }
void init(int n) {
fa.assign(n + 1, 0);<br/>
sz.assign(n + 1, 1);<br/>
iota(fa.begin(), fa.end(), 0);<br/>
}
int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool same(int x, int y) { return find(x) == find(y); }
void merge(int x, int y) {
sz[y] += sz[x];<br/>
fa[find(x)] = find(y);<br/>
}<br/>
};
int n;
struct edge {
int u, v, w;<br/>
}e[3007];
bool black[3007];
int cost[3007];
int g_w[6007];
vector<int> g[6007];
DSU dsu;
void kruskal_rebuild() {
sort(e + 1, e + n, [&](const edge &a, const edge &b) {return a.w < b.w;});<br/>
dsu.init(2 * n - 1);<br/>
for (int i = 1;i <= n - 1;i++) {<br/>
auto [u, v, w] = e[i];<br/>
u = dsu.find(u);<br/>
v = dsu.find(v);<br/>
g_w[n + i] = w;<br/>
g[n + i].push_back(u);<br/>
g[n + i].push_back(v);<br/>
dsu.merge(u, n + i);<br/>
dsu.merge(v, n + i);<br/>
}<br/>
}
/// kruskal重构树，O(mlogm)，图重构为树后任意两点LCA的权值是路径瓶颈
//* 最小生成树 <=> u-v所有路径最大边权中的最小值
ll sz[6007], f[6007][3007];
void dfs(int u) {
sz[u] = u <= n;<br/>
for (auto v : g[u]) {<br/>
dfs(v);<br/>
vector<ll> ff(n + 1, -1e18);<br/>
for (int i = 0;i <= sz[u];i++) {<br/>
for (int j = 0;j <= sz[v];j++) {<br/>
ll val = 1LL * (i * (sz[v] - j) + j * (sz[u] - i)) * g_w[u];<br/>
ff[i + j] = max(ff[i + j], f[u][i] + f[v][j] + val);<br/>
}<br/>
}<br/>
for (int i = 0;i <= sz[u] + sz[v];i++) f[u][i] = ff[i];<br/>
sz[u] += sz[v];<br/>
}<br/>
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);<br/>
cin >> n;<br/>
for (int i = 1;i <= n;i++) cin >> black[i];<br/>
for (int i = 1;i <= n;i++) {<br/>
cin >> cost[i];<br/>
f[i][black[i]] = 0;<br/>
f[i][black[i] ^ 1] = -cost[i];<br/>
}<br/>
for (int i = 1;i <= n - 1;i++) {<br/>
int u, v, w;<br/>
cin >> u >> v >> w;<br/>
e[i] = { u,v,w };<br/>
}
kruskal_rebuild();
dfs(2 * n - 1);
ll ans = 0;
for (int i = 0;i <= n;i++) ans = max(ans, f[2 * n - 1][i]);<br/>
cout << ans << '\n';<br/>
return 0;<br/>
}
题解
知识点：排列组合。
只有大小相同的多重子集才能产生贡献。对于一对子集，显然从小到大排序后，对应数字的差的绝对值的和就是最小操作次数，现在考虑枚举每个点对产生的贡献。
对于一组点对 ((i,j)) 表示A中第 (i) 个数和B中第 (j) 个数在对应位置，那么包含它们的子集有：
直接算是 (O(n)) 的，无法预处理，这里需要用到范德蒙德卷积公式：
其中一个推论是：
因此原式可以化简为 (O(1)) 的计算。
时间复杂度 (O(n^2))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int P = 998244353;
namespace Number_Theory {
const int N = 4e3 + 7;<br/>
int qpow(int a, ll k) {<br/>
int ans = 1;<br/>
while (k) {<br/>
if (k & 1) ans = 1LL * ans * a % P;<br/>
k >>= 1;<br/>
a = 1LL * a * a % P;<br/>
}<br/>
return ans;<br/>
}<br/>
int fact[N], invfact[N];<br/>
void init(int n) {<br/>
fact[0] = 1;<br/>
for (int i = 1;i <= n;i++) fact[i] = 1LL * i * fact[i - 1] % P;<br/>
invfact[n] = qpow(fact[n], P - 2);<br/>
for (int i = n;i >= 1;i--) invfact[i - 1] = 1LL * invfact[i] * i % P;<br/>
}<br/>
}
namespace CNM {
using namespace Number_Theory;<br/>
int C(int n, int m) {<br/>
if (n == m && m == -1) return 1; //* 隔板法特判<br/>
if (n < m || m < 0) return 0;<br/>
return 1LL * fact[n] * invfact[n - m] % P * invfact[m] % P;<br/>
}<br/>
}
/// 公式法求组合数，O(n)，预处理阶乘及其逆元快速求出组合数
int a[2007], b[2007];
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);<br/>
int n;<br/>
cin >> n;<br/>
for (int i = 1;i <= n;i++) cin >> a[i];<br/>
for (int i = 1;i <= n;i++) cin >> b[i];<br/>
sort(a + 1, a + n + 1);<br/>
sort(b + 1, b + n + 1);<br/>
CNM::init(2 * n);<br/>
int ans = 0;<br/>
for (int i = 1;i <= n;i++) {<br/>
for (int j = 1;j <= n;j++) {<br/>
int val = abs(a[i] - b[j]);<br/>
(ans += 1LL * CNM::C(i + j - 2, min(i, j) - 1) * CNM::C(2 * n - i - j, min(n - i, n - j)) % P * val % P) %= P;<br/>
}<br/>
}<br/>
cout << ans << '\n';<br/>
return 0;<br/>
}
题解
知识点：数学。
显然，(2) 的个数远比 (5) 多，因此我们只需要计算 (5) 因子的个数即可。
我们化简后有如下式子：
注意到， (5) 的倍数会贡献一次， (5^2) 的倍数又会贡献一次，以此类推。因此，我们按 (5) 的幂求幂次数总和即可。
但是，这里奇数和偶数的幂次规律是不同的，但都是等差，分别求一下即可。例如， (5) 的倍数时，分别求 (5,15,25,\cdots) 和 (10,20,30,\cdots) 两个幂次等差数列的和即可。
时间复杂度 (O(\log n))
空间复杂度 (O(1))
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using i128 = __int128_t;
template<class T>
inline void write(T x) {
if (x < 0) { putchar('-');x = -x; }<br/>
if (x >= 10) write(x / 10);<br/>
putchar(x % 10 + '0');<br/>
}
i128 calc1(i128 n, i128 x) {
i128 a1 = (n + 1) / 2 - x / 2;<br/>
i128 an = a1 % x;<br/>
i128 cnt = (a1 - an) / x + 1;<br/>
return (a1 + an) * cnt / 2;<br/>
}
i128 calc0(i128 n, i128 x) {
i128 a1 = n / 2 - x + 1;<br/>
i128 an = a1 % x;<br/>
i128 cnt = (a1 - an) / x + 1;<br/>
return (a1 + an) * cnt / 2;<br/>
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);<br/>
ll n;<br/>
cin >> n;<br/>
i128 x = 5, ans = 0;<br/>
while (n >= x) {<br/>
if (n >= 2 * x) ans += calc0(n, x);<br/>
ans += calc1(n, x);<br/>
x *= 5;<br/>
}<br/>
write(ans);<br/>
puts("");<br/>
return 0;<br/>
}
题解
知识点：枚举，前缀和。
我们求出前缀和 (sum)，那么原式改写为 (sum_{b1} - sum{l-1},sum_{b2} - sum{b1} \cdots) 。显然，当 (sum{l-1}) 和 (sum{r}) 不同奇偶时无解，否则需要在 ([l,r-1]) 的前缀和之间找到 (k-1) 个和 (sum{l-1},sum_{r}) 同奇偶的位置，这个过程可以用 (cnt) 记录前缀和奇偶个数的前缀和，可以 (O(1)) 查询。
时间复杂度 (O(n))
空间复杂度 (O(n))
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
ll a[100007];
int cnt[100007];
bool solve() {
int n, q;<br/>
cin >> n >> q;<br/>
for (int i = 1;i <= n;i++) {<br/>
cin >> a[i];<br/>
a[i] += a[i - 1];<br/>
cnt[i] = (a[i] & 1) + cnt[i - 1];<br/>
}<br/>
while (q--) {<br/>
int l, r, k;<br/>
cin >> l >> r >> k;<br/>
if ((a[l - 1] & 1) != (a[r] & 1)) {<br/>
cout << "NO" << '\n';<br/>
continue;<br/>
}<br/>
int res = cnt[r - 1] - cnt[l - 1];<br/>
if (!(a[l - 1] & 1)) res = r - l - res;<br/>
if (res >= k - 1) cout << "YES" << '\n';<br/>
else cout << "NO" << '\n';<br/>
}<br/>
return true;<br/>
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);<br/>
int t = 1;<br/>
cin >> t;<br/>
while (t--) {<br/>
if (!solve()) cout << -1 << '\n';<br/>
}<br/>
return 0;<br/>
}
题解
知识点：GCD和LCM。
可以分三类讨论：
- 当 (x,y = 0) 时，当且仅当 (z = 0) 时有解。
- 否则，当 (x = 0) 或 (y = 0) 时，当且仅当 (z) 为其中非零数的倍数时有解。
- 否则，当且仅当 (z) 是 (0) 或者 (\gcd(x,y)) 的倍数时有解。
时间复杂度 (O(T\log{\min{x_i,y_i}}))
空间复杂度 (O(1))
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
bool solve() {
int x, y, z;<br/>
cin >> x >> y >> z;<br/>
int d = gcd(x, y);<br/>
if (x == 0 && y == 0) {<br/>
if (z == 0) cout << "YES" << '\n';<br/>
else cout << "NO" << '\n';<br/>
}<br/>
else if (x == 0 || y == 0) {<br/>
if (z % d == 0) cout << "YES" << '\n';<br/>
else cout << "NO" << '\n';<br/>
}<br/>
else {<br/>
if (z && z % d == 0) cout << "YES" << '\n';<br/>
else cout << "NO" << '\n';<br/>
}<br/>
return true;<br/>
}
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);<br/>
int t = 1;<br/>
cin >> t;<br/>
while (t--) {<br/>
if (!solve()) cout << -1 << '\n';<br/>
}<br/>
return 0;<br/>
}
- 上一篇： 12306官方火车票Api接口
- 下一篇： 2023年郑州轻工业大学校赛邀请赛jc
相关文章
-
12306官方火车票Api接口
12306官方火车票Api接口
- 互联网
- 2026年04月04日
-
A 算法求第k短路径
A 算法求第k短路径
- 互联网
- 2026年04月04日
-
Aaron Stannard̸Akka.NET 1.1
Aaron Stannard̸Akka.NET 1.1
- 互联网
- 2026年04月04日
-
2023年郑州轻工业大学校赛邀请赛jc
2023年郑州轻工业大学校赛邀请赛jc
- 互联网
- 2026年04月04日
-
2023Java面试学习网站推荐
2023Java面试学习网站推荐
- 互联网
- 2026年04月04日
-
2023 年汽车行业向好发展，火山引擎 VeDI 助力车企数智转型
2023 年汽车行业向好发展，火山引擎 VeDI 助力车企数智转型
- 互联网
- 2026年04月04日
