比赛链接

牛客小白月赛102

A题

思路

用$set$检查$1$~$k$是不是全都出现过。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
int n, k;
int a[N];
void solve()
{cin >> n >> k;set<int> st;for (int i = 1; i <= n; i++){cin >> a[i];st.insert(a[i]);}for (int i = 1; i <= k; i++){if (!st.count(i)){cout << "NO" << endl;return;}}cout << "YES" << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

B题

思路

原式可以变化为：$x=a+\frac{1}{x}$，同时乘以$x$得到：$x^2=ax+1$。

因为$a$是已知，所以原问题便转化为了求一元二次方程的解。

即$x=\frac{a\pm \sqrt{a^2+4}}{2}$，因为$a-\sqrt{a^2+4}<0$，所以$x=\frac{a+\sqrt{a^2+4}}{2}$。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define double long double
double a;
void solve()
{cin >> a;double ans = (a + sqrtl(a * a + 4)) / 2.0;cout << fixed << setprecision(12) << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

C题

思路

假如sum大于总和，那么我们要把小的数改大，否则，我们要把大的数改小，排完序后直接贪心即可。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;int n, sum;
int a[N];
void solve()
{cin >> n >> sum;int res = 0;for (int i = 1; i <= n; i++){cin >> a[i];res += a[i];}sort(a + 1, a + 1 + n);int ans = 0;if (sum > res){int cha = sum - res;for (int i = 1; i <= n; i++){int op = 1e4;if (op - a[i] >= cha){ans++;break;}else{ans++;cha -= (op - a[i]);}}}else{int cha = res - sum;for (int i = n; i >= 1; i--){int op = -1e4;if (a[i] - op >= cha){ans++;break;}else{cha -= (a[i] - op);ans++;}}}cout << ans << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

D题

思路

$dist[i][j]$表示走到$i$号节点，有$j$天没有休息的最短时间。其中$dist[i][k+1]$表示走到$i$号节点且休息的最短时间。

用$dijkstra$进行转移，对于第$j$天没有休息的$dist[u][j]$，其可以转移到下一个点$v$的$dist[v][j+1:k+1]$。

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5, M = 10 + 5;
const int inf = 0x3f3f3f3f3f3f3f3f;int n, m, k;
int a[N];
int dist[N][M];
bool st[N][M];
vector<int> mp[N];
struct node
{int val, u, id;bool operator>(const node &w) const{return val > w.val;}
};
void dijkstra()
{priority_queue<node, vector<node>, greater<node>> q;for (int i = 1; i <= k; i++){if (i != k)dist[1][i] = 1;elsedist[1][k] = a[1];if (i != k)q.push({1, 1, i});elseq.push({a[1], 1, i});}while (q.size()){int d = q.top().val;int u = q.top().u;int id = q.top().id;q.pop();if (st[u][id])continue;st[u][id] = true;for (int i = 0; i < mp[u].size(); i++){int j = mp[u][i];int kkksc = id + 1;if (id == k)kkksc = 1;for (int op = kkksc; op <= k; op++){if (op == k){int len = a[j];if (dist[j][op] > d + len){dist[j][op] = d + len;q.push({dist[j][op], j, op});}}else{int len = 1;if (dist[j][op] > d + len){dist[j][op] = d + len;q.push({dist[j][op], j, op});}}}}}
}
void solve()
{cin >> n >> m >> k;k++;for (int i = 1; i <= n; i++){mp[i].clear();for (int j = 1; j <= k; j++){dist[i][j] = inf;st[i][j] = false;}}for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1, u, v; i <= m; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dijkstra();int minn = inf;for (int i = 1; i <= k; i++){minn = min(minn, dist[n][i]);}cout << minn << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}

E题

思路

换根dp板子题。

我们假设根节点为$1$号节点，令$dp1[i]$表示以$i$为根的子树中，$i$的儿子到$i$的后代的路径的最大值，$dp2[i]$为次大值。

之后我们考虑换根，$dp[i]$表示$i$的父亲与$i$上方的点形成的路径的最大值，之后用$dp[i]$去更新$dp1[i]$和$dp2[i]$即可。

最后的答案即为：$ans[c[i]]=max(ans[c[i]],dp1[i]+dp2[i]+w[i]);$

代码

#pragma GCC optimize("O2")
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 1e6 + 5;
const int inf = 1e18;int n;
int c[N], w[N];
int dp[N], dp1[N], dp2[N];
vector<int>mp[N];
vector<int>ans(N);
void modify(int &mx1, int &mx2, int mx)
{if (mx > mx1) mx2 = mx1, mx1 = mx;else if (mx > mx2)mx2 = mx;
}
void dfs1(int u, int fu)
{for (int j : mp[u]){if (j == fu) continue;dfs1(j, u);modify(dp1[u], dp2[u], dp1[j] + w[j]);}}
void dfs2(int u, int fu)
{if (u != 1){modify(dp1[u], dp2[u], dp[u]);}for (int j : mp[u]){if (j == fu) continue;if (dp1[u] != dp2[u] && dp1[u] == dp1[j] + w[j]){dp[j] = dp2[u] + w[u];}else dp[j] = dp1[u] + w[u];dfs2(j, u);}
}
void solve()
{cin >> n;for (int i = 1; i <= n; i++){dp[i] = dp1[i] = dp2[i] = 0;ans[i] = -inf;mp[i].clear();}for (int i = 1; i <= n; i++)cin >> c[i];for (int i = 1; i <= n; i++)cin >> w[i];for (int i = 1, u, v; i < n; i++){cin >> u >> v;mp[u].push_back(v);mp[v].push_back(u);}dfs1(1, -1);dfs2(1, -1);for (int i = 1; i <= n; i++){ans[c[i]] = max(ans[c[i]], dp1[i] + dp2[i] + w[i]);}for (int i = 1; i <= n; i++){if (ans[i] == -inf){cout << -1 << " ";}else cout << ans[i] << " ";}cout << endl;
}signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}