LVJR2 赛后题解

XiaoQuQu / 2023-05-06 / 原文

赛后补题请到洛谷比赛。

A

考虑分类讨论。显然当 \(a=0,b=0\) 时，答案等于 \(0\)。

当 \(a=0\) 或 \(b=0\) 时，直接将等于 \(0\) 的数乘以一个很大的数字，将不等于零的数除以一个很大的数字，答案为 \(v\)。
当 \(a,b\) 均不为 \(0\) 时，可以选择先将一个数字减到 \(0\)，或将一个数字除到 \(0\)，答案为 \(\min(u+v,2\times v)\)。

signed main()
{
    a = read() , b = read() , u = read() , v = read();
    if (a == 0 && b == 0) puts("0") , exit(0);
    if (a == b) cout << min(u,v * 2) << endl , exit(0);
    if (a == 0 || b == 0) cout << v << endl , exit(0);
    cout << min(u + v,v * 2) << endl;
    return 0;
}

代码来自选手 ybm。

B

考虑在什么情况下，DFS 有可能出错。显然，当且仅当这个图带环的时候，DFS 会求错最短路，于是直接使用并查集判断 \(1\) 所在的连通块 是否有环即可。

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e4 + 5; 
int n, m, T, fa[MAXN];

int find(int x) {
	if (fa[x] == x) return x;
	else return fa[x] = find(fa[x]);
} 

int main(void) {
	cin >> T;
	while (T--) {
		cin >> n >> m;
		for (int i = 1; i <= n; ++i) fa[i] = i;
		bool flag = 1;
		for (int i = 1; i <= m; ++i) {
			int u, v, fu, fv;
			cin >> u >> v;
			fu = find(u), fv = find(v);
			if (fu == fv && fu == find(1)) flag = 0;
			else fa[fu] = fv;
		}
		if (flag) cout << "1.000" << endl;
		else cout << "0.000" << endl; 
	}
}

C

考虑 DP。设 \(f_{i,j}\) 表示 \(b_{1\cdots i}\) 包含 \(g_{1\cdots j}\) 的最小代价，于是我们有如下转移。

当 \(i<j\) 时，\(f_{i,j}=\inf\)。
当 \(b_i=g_j\) 时，\(f_{i,j}=f{i-1,j-1}\)。
当 \(b_i\ne g_j\) 时，\(f_{i,j}=\min(f_{i-1,j-1}+1,f_{i-1,j})\)，分别表示将 \(b_i\) 改为 \(g_j\) 或让 \(b_{1\cdots i-1}\) 包含 \(g_{1\cdots j}\)。
边界情况为 \(f_{i,0}=0\)。

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1010
char s1[MAXN], s2[MAXN];
int ans, f[MAXN][MAXN];
int n, m;
int main()
{
    cin >> (s1 + 1) >> (s2 + 1);
    n = strlen(s1 + 1);
    m = strlen(s2 + 1);
    f[0][0] = 0;
    for (int i = 1; i <= n; i++)
    {
        f[i][0] = 0;
        for (int j = 1; j <= min(i, m); j++)
        {
            if (s1[i] == s2[j])
                f[i][j] = f[i - 1][j - 1];
            else
                f[i][j] = f[i - 1][j - 1] + 1;
            if (i > j)
                f[i][j] = min(f[i][j], f[i - 1][j]);
        }
    }
    printf("%d\n", f[n][m]);
    return 0;
}

代码来自选手 lyk。