ABC212 复盘

[ABC212C] Min Difference

思路解析

与 \(a_i\) 差值最小的某个 \(b_j\) 要么是第一个大于它的值，要么是第一个小于它的值，而这两个值都可以用二分求得，于是我们直接将 \(b\) 数组排序，然后对于每一个 \(a_i\) 都用二分找到上文提到的两个值即可。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 10;
int n, m, a[N], b[N];
signed main() {
	cin >> n >> m;
	for(int i = 1; i <= n; i++) {
		cin >> a[i];
	}
	for(int i = 1; i <= m; i++) {
		cin >> b[i];
	}
	sort(b + 1, b + m + 1);
	b[0] = -2e9, b[m + 1] = 2e9;
	long long ans = 2e9;
	for(int i = 1; i <= n; i++) {
		int lt = *(upper_bound(b + 1, b + m + 1, a[i]) - 1);
		int rt = *lower_bound(b + 1, b + m + 1, a[i]);
		ans = min(ans, min(a[i] - lt, rt - a[i]));
	}
	cout << ans;
	return 0;
}

[ABC212D] Querying Multiset

思路解析

可见将整个集合加一个值如果暴力做会 TLE，所以我们选择用一个 lazytag 记录下所有操作二的值的和，在加入集合和查询值时就根据 lazytag 加或减即可。由于查询只查询最小值，所以可以选择用小根堆存储。

时间复杂度：小根堆自带 \(O(\log N)\)（\(N\) 为元素个数）的常数，执行 \(Q\) 次询问，最多会有 \(Q\) 个元素，总复杂度为 \(O(Q \log Q)\)。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
int Q, add = 0;
priority_queue<int, vector<int>, greater<int> > q;
signed main() {
	cin >> Q;
	while(Q--) {
		int op, x;
		cin >> op;
		if(op == 1) {
			cin >> x;
			q.push(x - add);
		} else if(op == 2) {
			cin >> x;
			add += x;
		} else if(op == 3) {
			cout << q.top() + add << '\n';
			q.pop();
		}
	}
	return 0;
}

[ABC212E] Safety Journey

思路解析

首先根据题目的条件我们可以想到 dp，用 \(f_{i,j}\) 表示走了 \(i\) 步，现在在 \(j\) 的方案数，可见转移即是 \(f_{i,u} \gets \sum{f_{i-1,v}}\)，这里的 \(v\) 表示每个与 \(u\) 相连的点。可见如此做时间复杂度为 \(O(kn(\frac{n(n-1)}{2}-m))=O(k(\frac{n^3-n^2}{2}-nm)) \approx O(kn^3-knm)\)，考虑优化。

可以发现如果我们像上文一样建边总边数可以达到 \(\frac{n(n-1)}{2}-m \approx n^2-m\)，这个大小是很难被接受的，于是我们想到可以建反边，也就是只建被删除的那 \(m\) 条边，这样总边数就只有 \(m\) 条，可以接受，然后对于统计答案就只需要将转移式改成 \(f_{i,u} \gets \sum^{n}_{j=1}{f_{i-1,j}}-\sum{f_{i-1,v}}\) 即可，其中 \(\sum^{n}_{j=1}{f_{i-1,j}}\) 对于每个 \(u\) 都不会变，可以提前处理好。

注意计算 \(f_{i,u}\) 时要先减去 \(f_{i-1,u}\)，同时勤取模。

时间复杂度：虽有三层循环，但第二层内遍历的是每一条边，而总共只有 \(m\) 条边，因此为 \(O(km)\)，可以通过。

code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N = 5010, q = 998244353;
int n, m, k, f[N][N];
vector<int> g[N];
void mod(int &x) {
	x = (x % q + q) % q;
}
signed main() {
	cin >> n >> m >> k;
	for(int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		g[u].push_back(v); g[v].push_back(u);
	}
	f[0][1] = 1;
	for(int i = 1; i <= k; i++) {
		int sum = 0;
		for(int j = 1; j <= n; j++) sum += f[i - 1][j], mod(sum);
		for(int j = 1; j <= n; j++) {
			f[i][j] = sum - f[i - 1][j]; mod(f[i][j]);
			for(auto it : g[j]) {
				f[i][j] -= f[i - 1][it]; mod(f[i][j]);
			}
		}
	}
	cout << f[k][1];
	return 0;
}