自招模拟赛 Day3

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})$。

然后考虑父亲节点。

显然可以换根，父亲节点及它连的那一坨连通块将变为儿子节点和它的子树。所以类似的转移即可。

容斥一下，这个子树的贡献可以通过父亲节点的答案减去新根原有子树贡献的答案。

然后就能算了。

代码不给了。

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