暑假集训 Day2 总结

前言：

总分 $477$，感觉很开心。

D.统计区间

暴力拿了 $31$ 分，超时了。

正解思路：

可以运用哈希表，对前缀和进行优化，这样就可以不用双重 for 循环，也就不会超时了。首先，我们要知道，$sum_i-sum_{l-1}=k$ 等价于 $sum_i-k=sum_{l-1}$。所以，我们可以看看如果 $sum_i-k$ 出现过，就把答案加上 $mp_{sum_i-k}$，然后令 $mp_{sum_i}++$。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;
unordered_map<int, int> mp;
int n, k, ans;
int a[N], sum[N];
signed main() {
	freopen("tjqj.in", "r", stdin);
	freopen("tjqj.out", "w", stdout);
	cin >> n >> k;

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

	mp[0] = 1;

	for (int i = 1; i <= n; i++) {
		if (mp[sum[i] - k]) {
			ans += mp[sum[i] - k];
		}

		mp[sum[i]]++;
	}

	cout << ans;
	return 0;
}

F.我讨厌非整数

比赛打 DFS 暴力拿了 $44$ 分。

正解思路：

这道题是一道 dp。我们先建立一个三维的 dp 数组。四重 for 循环，第一层，枚举选的个数 $k$，从 $1$ 到 $n$；在第二层前，要初始化 dp 数组，并使 $dp_{0,0,0}=1$，然后枚举原数组，下标为 $i$，代表前几个数；第三层，枚举第一层的 $k$，下标为 $j$，表示目前转移到了取几个的情况；第四层枚举余数 $l$，余数从 $0$ 开始，不超过 $k$。状态转移方程分两种，一是不选的情况， 除了 $i$ 要加一其他不变，公式为 $dp_{i+1,j,l}=(dp_{i+1,j,l}+dp_{i,j,l})\bmod 998244353$；如果要选的话，就要改变选的个数与余数，公式为 $dp_{i+1,j+1,(l+a_i)\bmod998244353}=dp_{i+1,j+1,(l+a_i)\bmod998244353}+dp_{i,j,l}\bmod998244353$。最终答案就为 $\sum dp_{n,k,0}\bmod 998244353$。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M = 998244353;
int n, ans;
int dp[110][110][110];
signed main() {
	freopen("hate.in", "r", stdin);
	freopen("hate.out", "w", stdout);
	cin >> n;
	vector<int> a(n + 1);

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

	for (int k = 1; k <= n; k++) {
		memset(dp, 0, sizeof dp);
		dp[0][0][0] = 1;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j <= k; j++) {
				for (int l = 0; l <= k; l++) {
					if (dp[i][j][l] == 0) {
						continue;
					}

					dp[i + 1][j][l] = (dp[i + 1][j][l] + dp[i][j][l]) % M;

					if (j < k) {
						int ll = (l + a[i]) % k;
						dp[i + 1][j + 1][ll] = (dp[i + 1][j + 1][ll] + dp[i][j][l]) % M;
					}
				}
			}
		}

		ans = (ans + dp[n][k][0]) % M;
	}

	cout << ans;
	return 0;
}

G.图的破坏

赛时输出样例骗了 $2$ 分。

正解思路：

这题可以运用并查集，逆推，从全部删光推向完好无损，然后答案逆序输出即可。并查集的查找与合并都是板子，其他没啥可讲的，就是判断如果新来的节点和之前的一个节点有联系，就把连通分量减一。

AC 代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5+20;
int n, m, sum;
vector<int> d[N];
vector<int> f(N + 1);
stack<int> ans;
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;
	}
}
signed main() {
	freopen("break.in", "r", stdin);
	freopen("break.out", "w", stdout);
	cin >> n >> m;

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

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

	for (int i = n; i >= 1; i--) {
		ans.push(sum);
		sum++;

		for (int j = 0; j < d[i].size(); j++) {
			if (i < d[i][j]) {
				if (find(i) != find(d[i][j])) {
					sum--;
				}

				merge(i, d[i][j]);
			}
		}
	}

	while (ans.size()) {
		cout << ans.top() << endl;
		ans.pop();
	}

	return 0;
}