昨晚 CF(CF2261) E

cjdst

2026-10-18 09:11:38

发布于：广东

20阅读

0回复

0点赞

虽然水完了，但毕竟是首 E，还是纪念一下。

题目一次操作就是把一个 () 子串移到开头和结尾。

显然要考虑对一个连续的左括号段操作。

可以分成目标连续段在开头、目标连续段不在开头的情况。

在开头：一个序列只有一个开头段，所以可以考虑贪心模拟。
1. 如果操作在段末，相当于把 ) 移到结尾，可能会合并后面一段；
2. 如果操作在其它段，相当于给开头添加了一个 (。
  所以记录下只用操作 1 获得最多的左括号数量 $P_i$ ，然后答案就是 $\max P_i+m-i$ 。注意最后对 $\frac{n}{2}$ 取个 min。
不在开头：一次操作相当于减小了一个 ( 和清除了它右边的 )，将 ( 看成 $1$ ，将 ) 看成 $-1$ ，那么就求包含不超过 $m$ 个右括号下的最大子段和。ST 表二分即可。

#include <bits/stdc++.h>
#include <assert.h>
namespace cjdst{
	typedef long long ll;
	typedef unsigned long long ull;
	typedef std::pair <int, int> pii;
	typedef std::pair <ll, ll> pll;

	void init(){
		std::ios::sync_with_stdio(0);
		std::cin.tie(0);
		std::cout.tie(0);
	}
	
	const int N = 400000, M = 20;
	int st1[N + 5][M + 1], st2[N + 5][M + 1];
	std::string a;
	int pre[N + 5], pre2[N + 5];
	int curs[N + 5];
	int n, m;

	void solve(){
		std::cin >> n >> m >> a;
		a = " " + a + "     ";
		for(int i = 1; i <= n; i++){
			pre[i] = pre[i - 1] + (a[i] == '(' ? 1 : -1);
			pre2[i] = pre2[i - 1] + (a[i] == '(' ? 0 : 1);
			st1[i][0] = st2[i][0] = pre[i];
		}
		int cur = m, ans = 0;
		for(int i = 1; i <= n; i++){
			if(a[i] == '(') ans++;
			else{
				if(!cur) break;
				cur--;
			}
			curs[cur] = ans;
		}
		for(int i = 0; i <= m; i++){
			ans = std::max(ans, curs[i] + i);
		}
		ans = std::min(ans, n / 2);
		for(int i = 1; i <= M; i++){
			for(int j = 1; j <= n; j++){
				if(j + (1 << i) > n) break;
				st1[j][i] = std::min(st1[j][i - 1], st1[j + (1 << i - 1)][i - 1]);
				st2[j][i] = std::max(st2[j][i - 1], st2[j + (1 << i - 1)][i - 1]);
			}
		}
		for(int i = 1; i <= n; i++){
			int cur = i;
			for(int j = M; j >= 0; j--){
				if(cur + (1 << j) > n) continue;
				if(st1[cur][j] < pre[i]) continue;
				if(pre2[cur + (1 << j) - 1] - pre2[i - 1] > m) continue;
				ans = std::max(ans, st2[cur][j] - pre[i - 1]);
				cur += (1 << j);
			}
		}
		std::cout << ans << '\n';
		for(int i = 1; i <= n; i++){
			for(int j = 0; j <= M; j++){
				st1[i][j] = st2[i][j] = 0;
			}
		}
	}
}


int main(){
	cjdst::init();
	int T = 1;
	std::cin >> T;
	for(int _ = 1; _ <= T; _++){
		cjdst::solve();
	}
	std::cout.flush();

	return 0;
}