D - Connect the Dots Codeforces Round 976 (Div. 2)

原题

 D - Connect the Dots

思路

直接去做的话会超时, 因此用差分去优化

代码

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

int f[200020];
int z;
int b[11][200020];

// 并查集的 find 函数 
int find(int x)
{
	return f[x] != x ? f[x] = find(f[x]) : x;
}

// 检查是否一致, 一致则合并 
void check(int x, int y)
{
	x = find(x);
	y = find(y);
	if (x != y)
	{
//		每一次合并都会减少一个单独的区域 
		z--;
		f[x] = y;
	}
}

void solve()
{
	int n, m;
	cin >> n >> m;
	
	for (int i = 0; i < n + 5; i++)
	{
		f[i] = i;
		for (int d = 0; d < 11; d++)
		{
			b[d][i] = 0;
		}
	}
	
//		z 是答案, 一开始 n 个点各自都是一个区域 
	z = n;
	
//		输入 a d k 
	for (int i = 0; i < m; i++)
	{
		int a, d, k;
		cin >> a >> d >> k;
//			差分数组 
		b[d][a]++;
		b[d][a + d * k]--;
	}
	
//		d 从 1 到 10, 表示所选区域长度从 1 到 10
	for (int d = 1; d <= 10; d ++ )
	{
//			i 从 1 到 d, 表示起点从 1 到 d 
		for (int i = 1; i <= d; i++)
		{
//				s 初始化为 0 
			int s = 0;
//				
			for (int j = i; j <= n; j += d)
			{
//					j 是否与 j + d 相连, 求一个差分数组的前缀和即可 
				s += b[d][j];
				
				if (s > 0)
				{
					check(j, j + d);
				}
			}
		}
	}
//		输出答案 
	cout << z << endl;
}


int main()
{
	int t;
	cin >> t;
	
	while (t -- )
	{
		solve(); 
	}
	return 0;
}