【RbOI R1】A&D 题解
点击图片跳转比赛：
A.Anxious Robin
从左到右扫一遍，按照题意模拟即可。
这里解释一下我的代码：
因为只判断了六种字母，所以遇到 - 会直接过滤，无需特判。
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
char c[25];
int main() {
scanf("%s", c);
for(int i = 0; i < strlen(c); ++i) {
if(c[i] == 'A') putchar('5');
else if(c[i] == 'D') putchar('4');
else if(c[i] == 'G') putchar('3');
else if(c[i] == 'B') putchar('2');
else if(c[i] == 'E') {
if(c[i + 1] == '-') putchar('6');
else putchar('1');
}
}
return 0;
}
D.Sleepy Robin
给的其实是一个无向完全图，求的其实是一个最小生成树。
我们把每件事抽象成一个点，消耗的额外体力抽象成\长为 \(a_{i,j}\) 的边（断句已给出）。容易发现，题目其实是求留下 \((N-1)\) 条边，使 \(N\) 个点联通，并使所选边的边权和最小。
对此，我们有两种算法，\(Kruskal\) 和 \(Prim\) 别惦记你内破博客了
个人感觉 \(Prim\) 比 \(Kruskal\) 好理解，看个人选择罢，反正左右都是贪心。
\(Kruskal\) ver.
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
const int N = 1e5 + 5;
int n, F[N], ans, cnt;
struct edge {
int u, v, w;
} e[N];
bool cmp(edge a, edge b) {
return a.w < b.w;
}
int find(int x) {
if(F[x] == x) return x;
return F[x] = find(F[x]);
}
int weal, tot;
void kruskal() {
sort(e + 1, e + 1 + tot, cmp);
for(int i = 1; i <= tot; ++i) {
int fa_u = find(e[i].u), fa_v = find(e[i].v);
if(fa_u == fa_v) continue;
ans += e[i].w, F[fa_u] = fa_v;
if(++cnt == n - 1) return;
}
}
int main() {
// freopen("D10.in", "r", stdin);
// freopen("D10.out", "w", stdout);
scanf("%d", &n);
for(int i = 1; i <= n; i++) F[i] = i;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
scanf("%d", &weal);
if(i != j) e[++tot].u = i, e[tot].v = j, e[tot].w = weal;
}
}
kruskal();
printf("%d\n", ans);
return 0;
}
\(Prim\) ver.
展开代码
#include <bits/stdc++.h>
#define ll long long
#define MyWife Cristallo
using namespace std;
const int N = 1e5 + 5;
int n, m, s, ans, aans = 0x7fffffff;
int head[N], to[2 * N], weal[2 * N], dis[N], nxt[2 * N], tot;
bool vis[N];
void add(int u, int v, int w) {
to[++tot] = v;
weal[tot] = w;
nxt[tot] = head[u];
head[u] = tot;
}
struct node {
int dis, pos;
};
bool operator < (const node &x, const node &y) {
return x.dis > y.dis;
}
priority_queue<node> q;
inline void prim() {
// for(int i = 1; i <= n; ++i) dis[i] = 0x7fffffff;
// ans = 0x7fffffff;
// while(!q.empty()) q.pop();
int cnt = 0;
dis[s] = 0;
q.push((node){0, s});
while(!q.empty()) {
node tem = q.top();
q.pop();
int x = tem.pos, d = tem.dis;
if(vis[x]) continue;
vis[x] = 1, ++cnt;
ans += d;
for(int i = head[x]; i; i = nxt[i]) {
int y = to[i], w = weal[i];
if(dis[y] > w) {
dis[y] = w;
if(!vis[y]) q.push((node){dis[y], y});
}
}
}
if(cnt < n) ans = 0x7fffffff;
}
int main() {
// freopen("D01.in", "r", stdin);
scanf("%d", &n);
int w;
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
scanf("%d", &w);
if(i != j) {add(i, j, w); add(j, i, w);}
}
}
for(int i = 1; i <= n; ++i) dis[i] = 0x7fffffff;
s = 1;
prim();
printf("%d\n", ans);
return 0;
}
彩蛋
