526互联

Educational Codeforces Round 149 (Rated for Div. 2) B. Comparison String

发布时间 2023-09-05 21:22:53作者: zsxuan

给一个长度为 \(n\) 的字符串 \(s\) ，只包含字符“<”、“>”。
一个长度为 \(n + 1\) 的数组 \(a\) 与 \(s\) 是兼容的当且仅当对于任意 \(i\) ：

  1. \(s_i\) is \(<\) ，当且仅当 \(a_i < a_{i - 1}\)
  2. \(s_i\) is \(>\) ，当且仅当 \(a_i > a_{i - 1}\)

定义一个数组的 \(cost\) 为这个数组中不同数的个数。

求一个 \(cost\) 最小的且与 \(s\) 匹配的数组，只需要输出 \(cost\) 。

观察一：一个 \(<\) 或 \(>\) 可以作为连接两个节点 \((u, v)\) 的边，且 \(|u - v| = 1\) 。

观察二：整个 \(s\) 由若干段单调的段组成。

观察三：每次单调性发生改变时。如单增改为单减，为保证值域尽可能小，可以将递减的起点设为最高点。另一种情况同理。

观察四：答案为最长单调段长度 \(+ 1\) 。

view 
#include <bits/stdc++.h>
void solve() {
	int n; std::cin >> n;
	std::string Str; std::cin >> Str;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		int j = i;
		while (j <= n && Str[j - 1] == Str[i - 1]) j++;
		j -= 1;
		ans = std::max(ans, j - i + 1);
		i = j;
	}
	std::cout << ans + 1 << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}