求助 WA on 8
查看原帖
求助 WA on 8
131591
蒟蒻君HJT泽渡透香楼主2023/9/1 16:51

求各位佬佬帮看看哪里错了

思路是求出 fif_i 表示前 ii 个集合搞完是否可能使得 SS 为空;maima_i 表示 mai∼ima_i\sim i 这些集合中没有重复元素,且使得 maima_i 最小(双指针求)。

个人认为问题可能出在求最终答案的部分:枚举最后一次 SS 为空的位置 t,man−1≤t≤nt, ma_n-1\le t \le n,需要满足 ft=1f_t=1,若 t+1∼nt+1\sim n 中有 ki=0k_i=0 的,答案为 mm,否则答案为 ∑i=t+1nki\displaystyle \sum_{i=t+1}^n k_i。

#include <bits/stdc++.h>
std::vector <int> a[200005];
int n, m, k[200005], ans, f[200005], las[200005], ma[200005], buc[200005], cnt;
std::set <int> S, P;
void solve(){
	scanf("%d%d", &n, &m); S.clear(); P.clear();
	for(int i = 1; i <= n; ++i) f[i] = 0;
	f[0] = 1; ans = 0; cnt = 0;
	for(int i = 1; i <= n; ++i){
		a[i].clear(); scanf("%d", &k[i]);
		a[i].resize(k[i] + 1);
		for(int j = 1; j <= k[i]; ++j) scanf("%d", &a[i][j]), las[a[i][j]] = 0, buc[a[i][j]] = 0;
		if(!k[i]) P.insert(i);
	}
	ma[0] = 1; S.insert(0);
	for(int i = 1; i <= n; ++i){
		ma[i] = ma[i - 1];
		for(int j = 1; j <= k[i]; ++j){
			++buc[a[i][j]];
			if(buc[a[i][j]] > 1) ++cnt;
		}
		while(cnt){
			for(int j = 1; j <= k[ma[i]]; ++j){
				--buc[a[ma[i]][j]];
				if(buc[a[ma[i]][j]] == 1) --cnt;
			}
			++ma[i];
		}
		if(!k[i]) f[i] = 1;
		else if(i == 1) f[i] = 0;
		else {
			int l = ma[i - 1], r = i - 1;
			auto it = P.lower_bound(l); auto ti = S.lower_bound(l - 1);
			if(it != P.end() && (*it) <= r) f[i] = 1;
			else {
				for(int j = 1; j <= k[i]; ++j){
					int v = a[i][j];
					if(ti != S.end() && las[v] >= (*ti) + 1) f[i] = 1;
				}
			}
		}
		for(int j = 1; j <= k[i]; ++j) las[a[i][j]] = i;
		if(f[i]) S.insert(i);
	}
	int an = 0, ye = 0;
	for(int i = n; i >= ma[n]; --i){
		an += k[i]; if(!k[i]) ye = 1;
		if(!f[i - 1]) continue;
		if(ye) ans = std::max(ans, m);
		else ans = std::max(ans, an);
	}
	printf("%d\n", ans);
	return ;
}
int main(){
	int T = 1;
	scanf("%d", &T);
	while(T--) solve();
	return 0;
}



2023/9/1 16:51
加载中...