暑假集训 Day4 总结

B.不安分的魔法学院

这道题就是食物链的原题。

正解思路：

这道题目用扩展域很方便，简单又实用，下面我们就用扩展域的方法做这道题了。首先，我们要设定三个域。读入每一句话，对于第一种话，我们先判断这两个法师是否是一个学派，如果是的话，就让并查集合并三个域中这两个学派。 对于第二种话，我们先判断这两个法师是否是同一个学派或者 $y$ 克制 $x$，如果不是是的话，就让并查集实现 add(x,y+2*n) 同时 add(x+n,y) 同时 add(x+2*n,y)。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+20;
int n, k, ans;
int f[N];
int find(int x) {
	if (f[x] == x) {
		return x;
	}

	return f[x] = find(f[x]);
}
void merge(int r1, int r2) {
	int x = find(r1);
	int y = find(r2);

	if (x != y) {
		f[x] = y;
	}
}
int main() {
	cin >> n >> k;

	for (int i = 1; i <= 3 * n; i++) {
		f[i] = i;
	}

	while (k--) {
		int op, x, y;
		cin >> op >> x >> y;

		if (x > n || y > n) {
			ans++;
			continue;
		}

		if (op == 1) {

			if (find(x) == find(y + n) || find(x + n) == find(y)) {
				ans++;
				continue;
			}

			merge(x, y);
			merge(x + n, y + n);
			merge(x + n + n, y + n + n);
		} else if (op == 2) {

			if (find(x) == find(y) || find(x) == find(y + n)) {
				ans++;
				continue;
			}

			merge(x + n, y);
			merge(x + n + n, y + n);
			merge(x, y + n + n);
		}
	}

	cout << ans;
	return 0;
}

C.最短路径的数量

这道题很水，边权为一，不用最短路，普通广搜就行了。

正解思路：

对于每一个点，如果之前搜过，那么判断如果两个点汇聚在一起时两个点离起点的距离相等，那么就可以把另一个点的所有答案加到当前点上面。如果这个点没走过，那么就更新离起点的距离，并标记。

AC 代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 2e5+20;
const int M = 1e9+7;
int n, m;
int dp[N], dis[N], vis[N];
vector<int> d[N];
queue<int> q;
void bfs(int t) {
	q.push(t);
	vis[t] = 1;

	while (q.size()) {
		int u = q.front();
		q.pop();
		vis[u] = 1;

		for (int i = 0; i < d[u].size(); i++) {
			int v = d[u][i];

			if (vis[v] == 1) {
				if (dis[u] + 1 == dis[v]) {
					dp[v] = (dp[v] + dp[u]) % M;
				}
			} else {
				dis[v] = dis[u] + 1;
				dp[v] += dp[u];
				q.push(v);
				vis[v] = 1;
			}
		}
	}
}
int main() {
	cin >> n >> m;
	memset(dis, 0x3f, sizeof dis);

	for (int i = 1; i <= m; i++) {
		int a, b;
		cin >> a >> b;
		d[a].push_back(b);
		d[b].push_back(a);
	}

	dis[1] = 0;
	dp[1] = 1;
	bfs(1);
	cout << dp[n];
	return 0;
}

E.非递减彩色路径

正解思路：

对于这一道题，我们要先缩点，把所有颜色相等的点所称一个超级节点，而这一步就正好可以用并查集来实现。缩完点后，我们就要开始删边，让颜色浅的点指向颜色深的点。接下来，我们还要做一次排序，把每一个连通块按照颜色深浅排序。最后，进行 dp 操作。遇到两个颜色相同的点时，取价值更大的作为当前值；遇到颜色不同的时，$dp_v = \max(dp_v,dp_u+1)$。最后输出 $dp_{find(n)}$。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;
int n, m;
int a[N], dp[N], f[N];
vector<pair<int, int>> d(N + 1);
vector<vector<int>> g(N + 1);
vector<int> b(N + 1);
int find(int x) {
	if (f[x] == x) {
		return x;
	}

	return f[x] = find(f[x]);
}
void merge(int r1, int r2) {
	int x = find(r1);
	int y = find(r2);

	if (x != y) {
		f[x] = y;
	}
}
bool cmp(int x, int y) {
	return a[x] < a[y];
}
signed main() {
	cin >> n >> m;

	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		b[i] = i;
		f[i] = i;
	}

	for (int i = 1; i <= m; i++) {
		int u, v;
		cin >> u >> v;
		d.push_back({u, v});

		if (a[v] == a[u]) {
			merge(u, v);
		}
	}

	for (auto [u, v] : d) {
		int fu = find(u);
		int fv = find(v);

		if (a[fu] < a[fv]) {
			g[fu].push_back(fv);
		} else if (a[fu] > a[fv]) {
			g[fv].push_back(fu);
		}
	}

	for (int i = 1; i <= n; i++) {
		if (i == find(i)) {
			b.push_back(i);
		}
	}

	sort(b.begin(), b.end(), cmp);
	memset(dp, -1, sizeof dp);
	dp[find(1)] = 1;

	for (auto u : b) {
		if (dp[u] == -1) {
			continue;
		}

		for (int j = 0; j < g[u].size(); j++) {
			int v = find(g[u][j]);
			if (a[v] == a[u]) {
				dp[v] = max(dp[v], dp[u]);
			} else if (a[u] < a[v]) {
				dp[v] = max(dp[v], dp[u] + 1);
			}
		}
	}

	if (dp[find(n)] == -1) {
		cout << 0;
		return 0;
	}

	cout << dp[find(n)];
	return 0;
}