[Acwing] 第 19 场周赛

前言

传送门 :

3992. 树上有猴

t a g : tag : tag: 合法问题 有效区间 数学分析 题意 : 给定一个 a [ ] a[] a[],对于 a [ i ] a[i] a[i]表示使得当前的 c n t + a [ i ] cnt+a[i] cnt+a[i],询问有多少个合法的 c n t cnt cnt 其中各个期间的 c n t cnt cnt需要满足 m ≥ c n t ≥ 0 m \ge cnt \ge 0 m≥cnt≥0

思路 : 首先因为每个状态都是独立的,因此我们可用对 a [ i ] a[i] a[i]求前缀和 s [ i ] s[i] s[i],表示当前这个时间段和初始相差的数量

则我们可用设一开始的数量为 x x x

0 ≤ x ≤ w 0 ≤ x + s 1 ≤ w 0 ≤ x + s 2 ≤ w . . . . . \begin{aligned} & 0 \le x \le w\\ & 0 \le x+s_1 \le w\\ & 0 \le x+s_2 \le w\\ &..... \end{aligned} ​0≤x≤w0≤x+s1​≤w0≤x+s2​≤w.....​

化简式子我们我们可用得

0 ≤ x ≤ w − s 1 ≤ x ≤ w − s 2 ≤ x + ≤ w . . . . . \begin{aligned} & 0 \le x \le w\\ & -s_1 \le x \le w\\ & -s_2 \le x+ \le w\\ &..... \end{aligned} ​0≤x≤w−s1​≤x≤w−s2​≤x+≤w.....​

因此我们只需要找到所有区间的交集即可,即使得左边最大右边最小

Code :

int a[N],sum[N];

int n,m;


void solve(){
	cin>>n>>m;
	for(int i=1;i>a[i],sum[i] = sum[i-1] + a[i];
	
	
	int maxn = m ;
	int minn = 0;
	
	for(int i=1;in>>m;
	int minn = INF , maxn  = 0 ;
	
	for(int i=1;i>x;sum[x]++;
		//对区间按高度进行分类
		minn  = min(minn,x);
		maxn  = max(maxn,x);
	}
	
	for(int i=1;i minn;){
		int j = i ,  total = 0 ;
		/**
		下面即为关键
		**/
		while(j > minn && total + sum[maxn] - sum[j-1]