Codeforces Educational Round 180 题解
Codeforces Educational Round 180 题解
A - Race
题目概述
给定三个不同的整数点a, x, y，判断是否存在一个整数点z（z ≠ a），使得无论奖杯出现在x还是y，Bob的起点z到奖杯的距离都严格小于Alice的起点a到奖杯的距离。
解题思路
将x和y看作区间端点，若a不在此区间内，则Bob可以选择区间中点；反之则无法满足条件。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)void solved()
{int a, x, y;cin >> a >> x >> y;if (x > y){swap(x, y);}if (a < x || a > y){cout << "YES" << endl;}else{cout << "NO" << endl;}
}signed main()
{close;int T;cin >> T;while (T--){solved();}
}
B - Shrinking Array
题目概述
给定数组，每次操作可合并两个相邻元素为区间内任意值。求最小操作次数使数组满足存在相邻差值≤1。
解题思路
- 若原数组已有相邻差≤1，直接0次
- 查找极大/极小点，只需1次操作
- 否则无法达成
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)void solved()
{int n;cin >> n;vector<int> arr(n + 2, 0);for (int i = 1; i <= n; i++){cin >> arr[i];}for (int i = 1; i <= n - 1; i++){if (abs(arr[i] - arr[i + 1]) <= 1){cout << 0 << endl;return;}}for (int i = 2; i <= n - 1; i++){if ((arr[i] >= arr[i - 1] and arr[i] >= arr[i + 1]) or (arr[i] <= arr[i - 1] and arr[i] <= arr[i + 1])){cout << 1 << endl;return;}}cout << -1 << endl;
}signed main()
{close;int T;cin >> T;while (T--){solved();}return 0;
}
C - Coloring Game
题目概述
求三元组(i,j,k)数量，使得无论Bob选择哪个元素涂蓝，红元素之和严格大于蓝元素。
解题思路
排序后双指针枚举，满足a[i]+a[j] > a[k]且a[i]+a[j]+a[k] > max_element。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)void solved()
{int n;cin >> n;vector<int> arr(n + 1, 0);for (int i = 1; i <= n; i++){cin >> arr[i];}int ans = 0;sort(arr.begin() + 1, arr.end());for (int i = 1; i < n; i++){int l = n;int r = i + 1;for (int j = 1; j < i; j++){while (r <= n and arr[i] + arr[j] > arr[r]){++r;}while (l > i and arr[i] + arr[j] + arr[l] > arr[n]){--l;}int le = l + 1;int ri = r - 1;ans += max(0ll, (ri - le + 1));}}cout << ans << endl;
}
signed main()
{close;int T;cin >> T;while (T--){solved();}return 0;
}
D - Reachability and Tree
题目概述
给定树，确定边方向使得可达对数为n。当且仅当存在一个度为2的节点时可行。
解题思路
以度为2的节点为根，子树交替反向构造。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
int n;
const int N = 2e5 + 10;
map<int, int> mp;
int degree[N];
vector<int> edg[N];
int vis[N];
int fa[N];
int s;
void clean()
{cin >> n;for (int i = 1; i <= n; i++){degree[i] = 0;vis[i] = 0;edg[i].clear();}for (int i = 1; i <= n - 1; i++){int u, v;cin >> u >> v;degree[u] += 1;degree[v] += 1;edg[u].push_back(v);edg[v].push_back(u);}
}
void dfs(int i, int father)
{if (i == s){int cnt = 0;for (auto ne : edg[i]){vis[ne] = cnt;cnt += 1;fa[ne] = i;dfs(ne, i);}}else{for (auto ne : edg[i]){if (ne == father){continue;}fa[ne] = i;vis[ne] = 1 - vis[i];dfs(ne, i);}}
}
void solved()
{clean();s = -1;for (int i = 1; i <= n; i++){if (degree[i] == 2){s = i;}}if (s == -1){cout << "NO" << endl;return;}dfs(s, 0);cout << "YES" << endl;for (int i = 1; i <= n; i++){if (i == s){continue;}if (vis[i] == 0){cout << i << " " << fa[i] << endl;}else{cout << fa[i] << " " << i << endl;}}
}
signed main()
{close;int T;cin >> T;while (T--){solved();}return 0;
}
E - Tree Colorings
题目概述
求恰好m种美丽染色方案的最小树节点数。美丽染色定义为根绿，蓝绿连通，黄绿连通。
解题思路
动态规划预处理，状态转移方程为dp[m] = min(dp[k] + dp[m/k] +1)，其中k为因子分解。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
const int N = 5e5;
int dp[N + 1];
const int inf = 1e18;
void pre()
{for (int i = 1; i <= N; i++){dp[i] = inf;}dp[1] = 0;// 构造总价值为1的需要子树的大小为0for (int i = 1; i <= N; i++){// 价值为i作为别人的子树if (dp[i] != inf){int value = i + 2;for (int j = 1;; j++){if (j * value > N){break;}if (dp[j] != inf){dp[j * value] = min(dp[j * value], dp[j] + dp[i] + 1);}}}}
}
void solved()
{int n;cin >> n;if (dp[n] == inf){cout << -1 << endl;}else{cout << dp[n] + 1 << endl;}
}
signed main()
{close;pre();int T;cin >> T;while (T--){solved();}
}
F - Variables and Operations
题目概述
多源最短路预处理，判断在k次减操作后能否使变量结果依赖于操作顺序。
解题思路
Floyd预处理最短路，对每个查询计算可能的最小临界值。
代码实现
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
#define close ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
using namespace std;const int INF = 4e17;
const int MAXN = 502;int dist[MAXN][MAXN];
vector<pair<int, int>> edg[MAXN];void solve()
{int n, m;cin >> n >> m;for (int i = 0; i < m; i++){int x, y, w;cin >> x >> y >> w;edg[x].push_back({y, w});}for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){dist[i][j] = INF;}dist[i][i] = 0;}for (int v = 1; v <= n; ++v){for (auto const &[u, w] : edg[v]){dist[u][v] = min(dist[u][v], w);}}for (int k = 1; k <= n; k++){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){if (dist[i][k] != INF && dist[k][j] != INF){dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);}}}}int q;cin >> q;while (q--){string ans(n, '0');vector<int> a(n + 1, 0);int k;cin >> k;for (int i = 1; i <= n; i++){cin >> a[i];}for (int i = 1; i <= n; i++){int lmin = INF;int rmin = a[i];vector<int> nexM(n + 1, INF);for (auto const &[u, w] : edg[i]){rmin = min(rmin, a[u] + w);nexM[u] = min(nexM[u], w);}for (int j = 1; j <= n; j++){if (dist[j][i] < nexM[j] and j != i){lmin = min(lmin, a[j] + dist[j][i] - k);}}if (lmin < rmin){ans[i - 1] = '1';}}cout << ans << '\n';}
}signed main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);solve();return 0;
}