Two Pointers Method Step3 I.Segment with the Required Subset 双指针 + 01布尔背包 + 两个栈维护

题意

给定长度为\(n\)的数组\(a\),一个字段\(a[l:r]\)被称为good当且仅当能够选出若干个数使得他们的和为\(s\),任务是找到最短的good段

\[1 \leq n \leq 10^5\\ 1 \leq s \leq 10^3\\ 1\leq a_i \leq s\\ \]

分析

显然这样的性质具有单调性，也就是对于固定的\(r\)，我们不需要重新枚举\(l\)

因此此题可以用双指针做，维护这个性质显然可以用01布尔背包，可以用bitset优化个常数。

具体怎么删除呢？这里用到技巧是开动态的两个栈来维护，对于加入的数先加入\(st2\)，显然\(st2\)里的数的下标是逆序的，删除的时候，若\(st1\)中为空，就把这个时候\(st2\)的所有元素都加入到\(st1\)中，这个时候从栈顶开始就是正序的，因此直接pop栈顶元素即可。

判断good的时候只需要遍历两个栈中的元素然后判断能否拼出\(s\)即可

每个数最多进栈出栈两次，总复杂度\(O(ns)\)

代码

#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define all(x) (x).begin(),x.end()

using namespace std;
typedef long long ll;

ll rd(){
	ll x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9') {
		ch = getchar();
	}
	while(ch >= '0' && ch <= '9') {
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return x;
}

struct Stk{
	vector<int> stk;
	vector<bitset<1005>> bit;
	void init(){
		bitset<1005> tmp;
		tmp[0] = 1;
		bit.push_back(tmp);
	}
	void push(int x){
		stk.push_back(x);
		bitset<1005> tmp = bit.back();
		bit.push_back(tmp | (tmp << x));
	}
	int top(){
		return stk.back();
	}
	bitset<1005> get(){
		return bit.back();
	}
	void pop(){
		stk.pop_back();
		bit.pop_back();
	}
	bool empty(){
		return stk.empty();
	}
}s1,s2;

void add(int x){
	s2.push(x);
}

void del(){
	if(s1.empty()) {
		while(!s2.empty())
			s1.push(s2.top()),s2.pop();
	}
	s1.pop();
}

int s;
int n;

int a[100005];

bool good(){
	bitset<1005> v1 = s1.get();
	bitset<1005> v2 = s2.get();
	for(int i = 0;i <= s;i++){
		if(v1[i] && v2[s - i]) 
			return 1;
	}
	return 0;
}

int main(){
	s1.init();
	s2.init();
	n = rd();
	s = rd();
	for(int i = 1;i <= n;i++){
		a[i] = rd();
	}
	int l = 1;
	int ans = 1e9;
	for(int i = 1;i <= n;i++){
		add(a[i]);
		while(good()) {
			ans = min(ans,i - l + 1);
			del();
			l++;
		}
	}
	if(ans == 1e9) ans = -1;
	cout << ans << '\n';
}