ABC214

AtCoder Beginner Contest 214

D - Sum of Maximum Weights

题意

给出一颗 $N$ 个顶点的树，每条边都具有边权值，定义与顶点有关的二元函数 $f(u, v)$ 为 顶点 $u$ 到顶点 $v$ 的最短路径上的边权的最大值。

求

$$\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} f(i,j)$$

其中 $N \leqslant 10^5$

思路

最一开始以为是树形dp，在那想半天换根，其实根本不用

题目只要求取路劲上边权的最大值，那么可以将边权排序，然后从小到大地加入到图中，每次加入新边 $e$ 时，两个顶点的连通集中的点必定通过 $e$，并且 $e$ 是路径上边权最大的边，对左右两个连通集中的点的答案产生贡献。

可以使用并查集维护连通集，总复杂度 $O(NlogN)$，并查集复杂度远小于 $O(logN)$。

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
struct Edge {
	int u, v, w;
	bool operator < (const Edge &y) const &{
		return w < y.w;
	}
};
const int N = 1e5 + 10;
int fa[N], cnt[N];
int getfa(int x) {
	if (fa[x] == x) return x;
	return fa[x] = getfa(fa[x]);
}
bool same(int x, int y) {
	return getfa(x) == getfa(y);
}
void join(int x, int y) {
	if (!same(x, y)) {
		cnt[getfa(y)] += cnt[getfa(x)];
		fa[getfa(x)] = getfa(y);
	}
}
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	vector<Edge> a(n-1);
	for (int i = 0; i < n-1; i++) {
		cin >> a[i].u >> a[i].v >> a[i].w;
		a[i].u--, a[i].v--;
	}
	for (int i = 0; i < n; i++) fa[i] = i, cnt[i] = 1;
	sort(a.begin(), a.end());
	int ans = 0;
	for (int i = 0; i < n-1; i++) {
		ans += a[i].w * cnt[getfa(a[i].u)] * cnt[getfa(a[i].v)];
		join(a[i].u, a[i].v);
	}
	cout << ans << '\n';
	return 0;
}

E - Packing Under Range Regulations

题意

在区间 $[1,10^9]$ 上有编号 $1,\ldots,N$ 个球要放，每个位置上只能放一个球，对于编号 $i$ 的球，要求：必须放在区间 $[L_i,R_i]$ 之间，给出每一个球对应的要求区间，判断是否存在可行解？

多组数据，$N\leqslant 2\times 10^5$

思路

考虑从从左到右扫过去，对于当前扫到的位置 $i$，如果该位置上有左端点 $L_j$ 那么将其对应的 $R_j$ 推入大根堆中，这样就可以保证堆中元素的左端点 $L_j\leqslant i$，那么只需要判断是否有 $R_j\geqslant i$，如果成立，则弹出，将当前位置放上堆顶对应的球，否则一定无解，因为每次都是贪心取得距离当前位置最近的顶点，如果将堆顶对应的球提前放入，那么一定会有另一个求无法放入其中，所以如果不满足条件一定无解。

实现的时候，需要对左端点进行离散处理，然后进行上述模拟操作，总复杂度 $O(NlogN)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int MOD = 998244353;
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		vp range(n);
		vi L(n+1);
		for (int i = 0; i < n; i++) {
			cin >> range[i].first >> range[i].second;
			L[i] = range[i].first;
		}
		L[n] = 1e9+1;
		sort(L.begin(), L.end());
		L.resize(unique(L.begin(), L.end()) - L.begin());
		vii LR(L.size());
		for (auto &i : range) {
			i.first = lower_bound(L.begin(), L.end(), i.first) - L.begin();
			LR[i.first].pb(i.second);
		}
		priority_queue<int, vi, greater<int>> q;
		int sz = L.size();
		int GG = 0;
		for (int i = 0, last; i < sz; i++) {
			while (!q.empty() && last < L[i]) {
				int r = q.top();
				q.pop();
				if (r >= last) last++;
				else {
					GG = 1;
					break;
				}
			}
			if (GG) break;
			last = L[i];
			for (auto j : LR[i]) {
				q.push(j);
			}
		}
		if (!q.empty()) GG = 1;
		cout << (GG ? "No" : "Yes") << '\n';
	}
	return 0;
}

F - Substrings

题意

给出一个长度为 $N$ 的由小写英文字母组成的字符串 $S$，选出一个由 $S$ 的子序列构成的字符串 $T$，并保证该子序列中的元素不相邻，也就是对 $T$ 的下标 $\{a_m\}$，$T=S_{a_1}S_{a_2}\cdots S_{a_m}$，有 $\forall i, a_i+1\neq a_{i+1}$。求一共有多少不同的字符串 $T$，答案对 $10^9+7$ 取模。

$N\leqslant 2\times 10^5$

思路

这个题能使用dp，而且复杂度很奇妙。

dp能够处理子序列问题，这在以前都很常见，我们先不考虑序列中元素不相邻这个要求，令 $f(i)$ 为 $S$ 串上前 $i$ 个字符组成的子序列的个数，保证字符 $S_i$ 总被使用到。

则有转移

$$f(i)=\sum_{j=k_i}^{i-1}f(j)$$

其中 $k_i$ 表示最大的满足 $S_{k_i}=S_i$ 的下标，因为要保证生成的子序列不同，如果遇到了和当前 $S_i$ 相同的字符那么之间的字符在加上字符 $S_i$ 会和 $S_{k_i}$ 重复，所以之前的都不用计算了。

这个时间复杂度是 $O(26N)$，因为考虑一种字符，它的最大的遍历距离是 $N$，比如 $abbccccba$，那么 $a$ 遍历距离为8, $b$ 遍历距离为1+5, $c$ 遍历距离为1+1+1，所以每种字符的遍历的最大距离都不会超过 $N$，于是复杂度就正确了。

现在加上条件，两个下标不能相邻，那么只需修改下转移方程：

$$f(i) = \sum_{j=k_i}^{i-2}f(j)$$

其中 $k_i$ 为最大的满足 $S_{k_i+1}\neq S_i$ 的下标，因为遇到了相同的字符 $S_k=S_i$ 那么它开始取的位置是 $k-2$ 处，所以 $f(k-1)$ 处的值还是要加上的。

总复杂度 $O(26N)$

点击显/隐代码

#include <bits/stdc++.h>
#define db double
#define ll long long
#define int ll
#define vi vector<int>
#define vii vector<vi >
#define pii pair<int, int>
#define vp vector<pii >
#define vip vector<vp >
#define mkp make_pair
#define pb push_back
#define Case(x) cout << "Case #" << x << ": "
using namespace std;
const int INF = 0x3f3f3f3f;
const int P = 1e9 + 7;
const int N = 2e5 + 10;
char s[N];
signed main(){
#ifdef _DEBUG
//	FILE *file = freopen("out", "w", stdout);
#endif
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> s + 2;
	int n = strlen(s + 2), ans = 0;
	vi dp(n+2);
	dp[0] = 1;
	for (int i = 2; i < n+2; i++) {
		for (int j = i-2; j >= 0; j--) {
			dp[i] = (dp[i] + dp[j]) % P;
			if (s[i] == s[j+1]) break;
		}
		ans = (ans + dp[i]) % P;
	}
	cout << ans << '\n';
	return 0;
}