牛客小白月赛102题解
非常抱歉对题目的难度进行了错误的判断，影响了大家的写题体验。
D 题的题意似乎很多人读成了 1 是边权，还恰好能过样例，题意描述上的不妥。
E 题的知识点是换根dp，虽然是板子题，但是可能很多同学没有学习这个知识点，导致通过率偏低。
我将汲取教训，在此向大家道歉了。
A 序列中的排列
开个桶检查数组中是不是 中的所有数都出现过。假如都出现过输出
YES，否则输出 NO。
AC_Code
#include<bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
vector<int> a(101);
int n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
int x;
cin >> x;
a[x]++;
}
for (int i = 1; i <= k; i++) {
if (a[i] == 0) {
cout << "NO" << endl;
goto end;
}
}
cout << "YES" << endl;
end:;
}
return 0;
}
B 连分数
解题思路
和
的差别是式子的最底部加了个
，比如
，
。
当 趋于无穷时，这个影响可以忽略不计，所以
，解方程，舍去负解得
。
假如不需要证明的话还是挺好写。
定理：
AC_Code
#include<bits/stdc++.h>
using namespace std;
signed main() {
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
int T;
cin >> T;
cout << fixed << setprecision(15);
while (T--) {
double a;
cin >> a;
cout << (a + sqrtl(a * a + 4)) / 2 << '\n';
}
return 0;
}
C sum
解题思路
考虑 大于总和和
小于总和的情况，假如
大于总和，那么我们要把小的数改大，否则，我们要把大的数改小。
先考虑 大于总和的情况，按照从小到大将数组排序，尝试把数组中的每一个数改成
，检查改完之后的数组的总和是否大于等于
，假如大于等于
，那么说明完成修改，输出答案。
时间复杂度
AC_Code
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, sum;
cin >> n >> sum;
int sum0 = 0;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)cin >> a[i], sum0 += a[i];
int ans = 0;
if (sum0 == sum)cout << 0 << endl;
else if (sum0 > sum) {//把大数边小数
std::sort(a.begin() + 1, a.end(), [&](int x, int y) {
return x > y;
});
for (int i = 1; i <= n; i++) {
if (sum0 - a[i] - 10000 > sum) {
ans++;
sum0 -= a[i] + 10000;
} else {
ans++;
break;
}
}
cout << ans << endl;
} else {
std::sort(a.begin() + 1, a.end());
for (int i = 1; i <= n; i++) {
if (sum0 - a[i] + 10000 < sum) {
ans++;
sum0 += 10000 - a[i];
} else {
ans++;
break;
}
}
cout << ans << endl;
}
}
return 0;
}
D 最短？路径
解题思路
考虑使用 ，用
表示走到
，有
天没有休息的最短时间。
用 dijkstra 进行转移，考虑走到下一个节点时是否休息，假如下一个节点是 已经休息了
次，选择休息，那么代价就是
，选择不休息，代价就是
，往
转移，需要考虑
是否小于
。
部分实现可能会细节较多。
时间复杂度 。
AC_Code
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 200000;
int dist[N + 1][11];
int st[N + 1][11];
signed main() {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--) {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(n + 1);
for (int i = 1; i <= n; i++)cin >> a[i];
vector<vector<int>> g(n + 1);
for (int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= k; j++) {
dist[i][j] = 1e18;
st[i][j] = 0;
}
}
priority_queue<array<int, 3>, vector<array<int, 3>>, greater<>> q;
if (k != 0) {
dist[1][1] = 1;
q.push({1, 1, 1});
}
dist[1][0] = a[1];
q.push({a[1], 1, 0});
while (q.size()) {
auto [w, i, j] = q.top();
q.pop();
if (st[i][j])continue;
st[i][j] = 1;
for (auto ne: g[i]) {
//休息
if (dist[ne][0] > a[ne] + w) {
dist[ne][0] = a[ne] + w;
q.push({dist[ne][0], ne, 0});
}
//不休息
if (j + 1 <= k && dist[ne][j + 1] > w + 1) {
dist[ne][j + 1] = w + 1;
q.push({dist[ne][j + 1], ne, j + 1});
}
}
}
int ans = 1e18;
for (int i = 0; i <= k; i++)ans = min(ans, dist[n][i]);
cout << ans << endl;
}
return 0;
}
E k - 路径（easy vension）
解题思路
先求出经过每个点的路径的最大权值，然后遍历所有点，更新当前点的种类的答案就可以了。
考虑如何求每个点的路径的最大权值。
首先假定根为 ，设
表示以
为根的子树中，
的儿子到的
的后代的链权值最大值，
表示次大值。
再考虑使用换根 ，设
，表示
的父亲与
上方的点连接的简单路径的最大权值。
然后用父亲去更新儿子的 ，假如父亲的最大值和次大值不一样，可以直接更新儿子的
，否则看最大值是不是当前儿子转移过来的，假如是，用次大值更新儿子，否则用最大值。
AC_Code
#include<bits/stdc++.h>
using namespace std;
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
using i64 = long long;
const i64 inf = 1e18;
const int N = 1000000;
i64 dp1[N + 1];
i64 dp2[N + 1];
i64 dp3[N + 1];
i64 ans[N + 1];
int w[N + 1];
int c[N + 1];
vector<int> g[N + 1];
inline void upd(i64 &mx1, i64 &mx2, i64 mx) {
if (mx > mx1)mx2 = mx1, mx1 = mx;
else if (mx > mx2)mx2 = mx;
}
void dfs(int x, int fa) {
for (auto i: g[x]) {
if (i == fa)continue;
dfs(i, x);
upd(dp1[x], dp2[x], dp1[i] + w[i]);
}
}
void dfs1(int x, int fa) {
if (x != 1)upd(dp1[x], dp2[x], dp3[x]);
for (auto i: g[x]) {
if (i == fa)continue;
if (dp1[x] != dp2[x] && dp1[x] == dp1[i] + w[i]) {
dp3[i] = dp2[x] + w[x];
} else dp3[i] = dp1[x] + w[x];
dfs1(i, x);
}
}
signed main() {
ios;
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) cin >> c[i];
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= n; i++) g[i].clear();
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++)dp1[i] = dp2[i] = 0, ans[i] = -inf;
dfs(1, 0);
dfs1(1, 0);
for (int i = 1; i <= n; i++) {
ans[c[i]] = max(ans[c[i]], w[i] + dp1[i] + dp2[i]);
}
for (int i = 1; i <= n; i++) {
if (ans[i] != -inf)cout << ans[i] << ' ';
else cout << -1 << ' ';
}
cout << endl;
}
return 0;
}
F k - 路径（mid vension）
解题思路
判断多重集是否相等可以使用哈希。
先给每种类别映射一个不同的 类型的随机数，得到
a 数组。
再给每种类别映射一个不同的 类型的随机数，得到
b 数组。
定义一个 map，map[i] 表示从某个点到 的路径的节点类型的随机值使用
a 映射的之和，加上这个点类型的随机值使用 b 映射的值，结果是 i 的路径的权值最大值。
然后就可以使用一条路径的信息查询是否存在另一条路径拼起来是 k-路径。
从 开始
，然后到达一个点
，查询是否有另一条和
相连的链和当前点和
相连的链组成的点的集合是否是
- 排列，假如存在就更新一下答案，然后将
与
相连的路径的点集的权值存一下，假如已经有相同的点集，权值取最大。查询可以使用
unordered_map 或者 map。
AC_Code
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define PII pair<int,int>
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define ull unsigned long long
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
static ull randint() {
return (rng() * 1ll << 32) ^ rng();
}
struct PIIHash {
size_t operator()(const PII &p) const {
return std::hash<int>()(p.first) ^ std::hash<int>()(p.second);
}
};
using i64 = long long;
const i64 inf = 1e18;
const int N = 1000000;
int c[N + 1];
i64 w[N + 1];
ull b[N + 1];
ull sum[N + 1];
ull d[N+1];
i64 ans[N + 1];
int main() {
ios;
int T;
cin>>T;
while (T--) {
int n, x;
cin>>n>>x;
for (int i = 1; i <= n; i++)cin>>c[i];
for (int i = 1; i <= n; i++)cin>>w[i];
vector<vector<int>> g(n + 1);
for (int i = 1; i < n; i++) {
int u, v;
cin>>u>>v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++)b[i] = randint();
for (int i = 1; i <= n; i++)d[i] = randint();
for (int i = 1; i <= n; i++)sum[i] = sum[i - 1] + b[i];
for (int i = 1; i <= n; i++)sum[i] += b[i];
gp_hash_table<ull, i64> mp;
for (int i = 1; i <= n; i++)ans[i] = -inf;
auto dfs = [&](auto &&self, int u, int fa, ull sum0, i64 w0) -> void {
if (mp.find(sum[c[u]] - sum0 + b[c[x]] + d[c[u]])!=mp.end()) {
ans[c[u]] = max(ans[c[u]], w0 + mp[sum[c[u]] - sum0 + b[c[x]] + d[c[u]]] - w[x]);
}
if (mp.find(sum0+d[c[u]])!=mp.end()) mp[sum0+d[c[u]]] = max(mp[sum0+d[c[u]]], w0);
else mp[sum0+d[c[u]]] = w0;
for (auto i: g[u]) {
if (i != fa)self(self, i, u, sum0 + b[c[i]], w0 + w[i]);
}
};
dfs(dfs, x, 0, b[c[x]], w[x]);
if (mp.find(sum[c[x]]+ d[c[x]])!=mp.end())ans[c[x]] = max(ans[c[x]], mp[sum[c[x]]+ d[c[x]]]);
for (int i = 1; i <= n; i++) {
if (ans[i] != -inf)cout << ans[i] << ' ';
else cout << -1 << ' ';
}
cout << endl;
}
return 0;
}
G k - 路径（hard vension）
解题思路
沿用 mid vension 的思路，路径有关的题目可以考虑用点分治，每次找到树的重心，然后重心将树分为更小的树，分别调用 的代码即可。
AC_Code
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
#define PII pair<int,int>
#define fi first
#define se second
#define ios ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define endl '\n'
#define vii vector<vector<int>>
using i64 = long long;
#define ull unsigned long long
const i64 inf = 1e18;
mt19937 rng(chrono::system_clock::now().time_since_epoch().count());
static ull randint() {
return (rng() * 1ll << 32) ^ rng();
}
struct pair_hash {
template<class T1, class T2>
std::size_t operator()(const std::pair<T1, T2> &p) const {
return std::hash<T1>()(p.first) ^ std::hash<T2>()(p.second);
}
};
const int N = 200010;
int c[N];
i64 w[N];
ull sum[N];
ull b[N];
ull d[N];
int st[N];
i64 ans[N];
int siz[N];
vector<int> g[N];
void dfs1(int x, int fa) {
siz[x] = 1;
for (auto i: g[x]) {
if (i == fa || st[i])continue;
dfs1(i, x);
siz[x] += siz[i];
}
};
int maxxx;
int tot;
int G;
void dfs2(int x, int fa) {
int add = 0;
int maxx = 0;
for (auto i: g[x]) {
if (i == fa || st[i])continue;
add += siz[i];
maxx = max(maxx, siz[i]);
dfs2(i, x);
}
maxx = max(maxx, tot - add - 1);
if (maxxx > maxx)G = x, maxxx = maxx;
};
int idx = 0;
void dfs(int x, int fa, ull sum0, i64 w0) {
for (auto i: g[x]) {
if (i == fa || st[i])continue;
idx++;
dfs(i, x, sum0 + b[c[i]], w0 + w[i]);
}
};
gp_hash_table<ull, i64> mp;
void cal(int x) {
mp.clear();
auto dfs = [&](auto &&self, int u, int fa, ull sum0, i64 w0) -> void {
if (mp.find(sum[c[u]] - sum0 + b[c[x]] + d[c[u]])!=mp.end()) {
ans[c[u]] = max(ans[c[u]], w0 + mp[sum[c[u]] - sum0 + b[c[x]] + d[c[u]]] - w[x]);
}
if (mp.find(sum0+d[c[u]])!=mp.end()) mp[sum0+d[c[u]]] = max(mp[sum0+d[c[u]]], w0);
else mp[sum0+d[c[u]]] = w0;
for (auto i: g[u]) {
if (i != fa&&!st[i])self(self, i, u, sum0 + b[c[i]], w0 + w[i]);
}
};
dfs(dfs, x, 0, b[c[x]], w[x]);
if (mp.find(sum[c[x]]+ d[c[x]])!=mp.end())ans[c[x]] = max(ans[c[x]], mp[sum[c[x]]+ d[c[x]]]);
}
void work(int x) {
dfs1(x, 0);
maxxx = 1e9;
tot = siz[x];
dfs2(x, 0);
st[G] = 1;
cal(G);
for (auto i: g[G]) {
if (st[i])continue;
work(i);
}
};
int main() {
ios;
for (int i = 1; i < N; i++)b[i] = randint();
for (int i = 1; i < N; i++)d[i] = randint();
for (int i = 1; i < N; i++)sum[i] = sum[i - 1] + b[i];
for (int i = 1; i < N; i++)sum[i] += b[i];
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++)cin >> c[i];
for (int i = 1; i <= n; i++)cin >> w[i];
for (int i = 1; i <= n; i++)g[i].clear(), st[i] = 0;
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++)ans[i] = -inf;
work(1);
for (int i = 1; i <= n; i++) {
if (ans[i] != -inf)cout << ans[i] << ' ';
else cout << -1 << ' ';
}
cout << endl;
}
return 0;
}
京公网安备 11010502036488号