自招模拟赛 Day3

cjdst

2026-07-02 20:13:15

发布于：广东

26阅读

0回复

0点赞

Day1 Day2 忘打了。

题目：https://www.acgo.cn/discuss/rest/84561

什么 DSU Round。

嗯对。按照做题顺序写。

B

本来是 C 的，不知道是不是我的原因，很多人都先开 C，后来老师 swap(B,C) 了。

Difficulty：3.0 / Easy

Tag：-

简单连通块问题。这里使用了并查集。

八连通其实只需要判断 $(x-1,y-1),(x-1,y),(x-1,y+1),(x,y-1)$ 四个方向即可。

没了。

namespace cjdst{
    class dsu{
		public:
		
		std::vector <int> father, siz;
		dsu(int n){
			father.resize(n + 5);
			siz.resize(n + 5, 1);
			for(int i = 1; i <= n; i++){
				father[i] = i;
			}
		}
		int find(int n){
			return (father[n] == n ? n : father[n] = find(father[n]));
		}
		void merge(int x, int y){
			x = find(x), y = find(y);
			if(x == y) return;
			if(siz[x] > siz[y]) std::swap(x, y);
			siz[y] += siz[x], father[x] = y;
		}
	};
	
	void solve(){
		int n, m;
		std::cin >> n >> m;
		std::vector <std::string> a(n + 5);
		for(int i = 1; i <= n; i++){
			std::cin >> a[i];
			a[i] = " " + a[i] + "     ";
		}
		dsu u(n * m);
		const int dir[][2] = {-1, -1, -1, 0, -1, 1, 0, -1};
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(a[i][j] == '.') continue;
				for(int k = 0; k < 4; k++){
					int x = i + dir[k][0], y = j + dir[k][1];
					if(x && y && a[x][y] == '*'){
						u.merge((i - 1) * m + j, (x - 1) * m + y);
					}
				}
			}
		}
		std::vector <int> vis(n * m + 5);
		std::vector <int> cur(n * m + 5);
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= m; j++){
				if(a[i][j] == '*' && !vis[u.find((i - 1) * m + j)]){
					vis[u.find((i - 1) * m + j)] = 1;
					cur[u.siz[u.find((i - 1) * m + j)]]++;
				}
			}
		}
		int ans = 0, ans2 = 0;
		for(int i = 1; i <= n * m; i++){
			if(cur[i]) ans++, ans2 = std::max(ans2, cur[i] * i);
		}
		std::cout << ans << ' ' << ans2 << '\n';
	}
}

时间复杂度： $O(nm\alpha(nm))$ 。

A

Difficulty：3.0 / Easy

Tag：-

经典题。简单连通块问题。这里使用了并查集。

四连通其实只需要判断 $(x-1,y),(x,y-1)$ 两个方向即可。

然后怎么判断是不是边界呢，其实也很简单，建立一个虚点，将所有边界点和这个虚点合并，然后最后查询每个点是否和虚点连通即可。

namespace cjdst{
    class dsu{
		public:
		
		std::vector <int> father, siz;
		dsu(int n){
			father.resize(n + 5);
			siz.resize(n + 5, 1);
			for(int i = 1; i <= n; i++){
				father[i] = i;
			}
		}
		int find(int n){
			return (father[n] == n ? n : father[n] = find(father[n]));
		}
		void merge(int x, int y){
			x = find(x), y = find(y);
			if(x == y) return;
			if(siz[x] > siz[y]) std::swap(x, y);
			siz[y] += siz[x], father[x] = y;
		}
	};
	
	void solve(){
		int n;
		std::cin >> n;
		std::vector <std::vector <int>> a(n + 5, std::vector <int>(n + 5));
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				std::cin >> a[i][j];
			}
		}
		dsu u(n * n + 1);
		for(int i = 1; i <= n; i++){
			if(!a[1][i]) u.merge(i, n * n + 1);
			if(!a[i][1]) u.merge((i - 1) * n + 1, n * n + 1);
			if(!a[i][n]) u.merge(i * n, n * n + 1);
			if(!a[n][i]) u.merge((n - 1) * n + i, n * n + 1);
		}
		const int dir[][2] = {-1, 0, 0, -1};
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(a[i][j]) continue;
				for(int k = 0; k < 2; k++){
					int x = i + dir[k][0], y = j + dir[k][1];
					if(x && y && !a[x][y]){
						u.merge((i - 1) * n + j, (x - 1) * n + y);
					}
				}
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				if(!a[i][j] && u.find((i - 1) * n + j) != u.find(n * n + 1)){
					a[i][j] = 2;
				}
			}
		}
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				std::cout << a[i][j] << ' ';
			}
			std::cout << '\n';
		}
	}
}

时间复杂度： $O(n^2\alpha(n^2))$ 。

C

Difficulty：3.1 / Easy

Tag：-

画一下图，猜测这是一个二分图染色问题。

其实这就是二分图染色问题。显然染色以后求出颜色数量更小的点即可。

那么这个应该怎么做呢，注意到我不会搜索，所以只能并查集了。

经典做法，开 $2n$ 个点，前 $n$ 个点权值为 $1$ ，后 $n$ 个点权值为 $0$ ，每条边看做 $x\to y+n$ ， $y\to x+n$ 两条边。

如果 $x,x+n$ 连通那就说明不是二分图。

否则查询 $x,x+n$ 分别所在连通块权值之和最小值。

namespace cjdst{
    class dsu{
		public:
		
		std::vector <int> father, siz, siz2;
		dsu(int n){
			father.resize(n + 5);
			siz.resize(n + 5, 1);
			siz2.resize(n + 5);
			for(int i = 1; i <= n; i++){
				father[i] = i;
			}
		}
		int find(int n){
			return (father[n] == n ? n : father[n] = find(father[n]));
		}
		void merge(int x, int y){
			x = find(x), y = find(y);
			if(x == y) return;
			if(siz[x] > siz[y]) std::swap(x, y);
			siz[y] += siz[x], siz2[y] += siz2[x], father[x] = y;
		}
	};
	
	void solve(){
		int n, m;
		std::cin >> n >> m;
		dsu u(n * 2);
		for(int i = 1; i <= n; i++){
			u.siz2[i] = 1;
		}
		for(int i = 1; i <= m; i++){
			int x, y;
			std::cin >> x >> y;
			u.merge(x, y + n);
			u.merge(y, x + n);
		}
		int ans = 0;
		std::vector <int> vis(n * 2 + 5);
		for(int i = 1; i <= n; i++){
			if(vis[u.find(i)]) continue;
			if(u.find(i) == u.find(n + i)){
				std::cout << "Impossible\n";
				return;
			}
			vis[u.find(i)] = vis[u.find(i + n)] = 1;
			ans += std::min(u.siz2[u.find(i)], u.siz2[u.find(i + n)]);
		}
		std::cout << ans << '\n';
	}
}

时间复杂度： $O(m\alpha(n))$ 。

D

Difficulty：4.4 / Medium-

Tag：换根 DP

我去怎么是传奇深中自招原题。

哎代码能力太弱了，lbc 来了直接 20min 秒了。

假设以 $1$ 为根。

首先不考虑父亲节点的影响。

考虑求出以某个点为根，每个子树的答案，再加上子树之间的答案，加起来。

注意到子树之间的 LCA 显然为根。所以转移方程就是 $\text{ans}_{\text{cur}}=(\sum_{u\in \text{son}_\text{cur}} \text{ans}_u)+(\sum_{u\in \text{son}_\text{cur}}\sum_{v\in \text{son}_\text{cur}} \text{size}_u\times \text{size}_v\times \text{cur})$ 。