CF1873F Money Trees

CF1873F Money Trees

双指针好题，但是我用的队列（

考虑先找出所有极长的、满足任意一个数都能被它后面的那个数整除的连续段。显然这个操作可以在 \(\mathcal{O}(n)\) 的时间复杂度内完成。

求出每个极长连续段的答案，取 \(\max\) 即为最终答案。那么现在的问题就是求一个数列中，满足和不超过正整数 \(m\) 的子串的最长长度。

注意到这个问题可以使用双指针法解决：右端点从左向右扫，每 \(+1\) 就相当于加入一个值。同时维护当前选中的数的和，如果超过 \(m\) 就删除之前的数，直到和 \(\le m\)。在维护过程中更新答案即可。

时间复杂度 \(\mathcal{O}(n)\)。代码使用了 std::queue，和双指针本质相同。

#include<bits/stdc++.h>
using namespace std;
#define int long long
bool Mbegin;
void File_Work(){
	freopen("test.in","r",stdin);
	freopen("test.out","w",stdout);
}
namespace Fast_In_Out{
	char buf[1<<21],*P1=buf,*P2=buf;
	#define gc (P1==P2&&(P2=(P1=buf)+fread(buf,1,1<<21,stdin),P1==P2)?EOF:*P1++)
	int read(){
		int f=1,x=0;
		char c=gc;
		while(c<'0'||c>'9'){
			if(c=='-')
			    f=-1;
			c=gc;
		}
		while(c>='0'&&c<='9'){
			x=x*10+c-'0';
			c=gc;
		}
		return f*x;
	}
	void write(int x){
		if(x<0)
			x=-x,putchar('-');
		if(x>9)
			write(x/10);
		putchar(x%10+'0');
	}
	#undef gc
}
using namespace Fast_In_Out;
typedef pair<int,int> pii;
const int N=2e5+8,oo=1e18+8;
int n,m,a[N],b[N];
vector<pii> vec;
int work(int ll,int rr){
	queue<int> que;
	int now=0,res=0,siz=0;
	for(int i=ll;i<=rr;i++){
		if(now<=m){
			now+=a[i];
			que.push(a[i]);
			siz++;
		}
		while(now>m&&que.empty()==0){
			now-=que.front();
			que.pop();
			siz--;
		}
		res=max(res,siz);
	}
	return res;
}
void solve(){
	vec.clear();
	for(int i=1;i<=n;i++)
		a[i]=b[i]=0;
	n=read(),m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=n;i++)
		b[i]=read();
	b[0]=b[n+1]=oo;
	int pos=1;
	for(int i=1;i<=n;i++){
		if(b[i]%b[i+1]!=0){
			vec.push_back({pos,i});
			pos=i+1; 
		}
	}
	int ans=0;
	for(auto cur:vec){
		int l=cur.first,r=cur.second;
		int tmp=work(l,r);
//		write(tmp),putchar(' ');
		ans=max(ans,tmp);
	}
	write(ans),putchar('\n');
}
bool Mend;
signed main(){
//	File_Work();
	fprintf(stderr,"%.3lf MB\n\n\n",(&Mbegin-&Mend)/1048576.0);
	int testnum=read();
	while(testnum--)
		solve();
	fprintf(stderr,"\n\n\n%.0lf ms",1e3*clock()/CLOCKS_PER_SEC);
	return 0;
}