【蓝桥杯】专题练习

前缀和

3956. 截断数组 - AcWing题库

一看到题目很容易想到的思路是对数组求前缀和，然后枚举两个分段点就好，时间复杂度是On^2，n是1e5会t，需要优化。

朴素的代码，会超时：

#include <bits/stdc++.h>
using ll=long long;
const int N=2e5+10;
int a[N],s[N];
void solve()
{
	int n;
	std::cin>>n;
	for(int i=1;i<=n;i++)
	{
		std::cin>>a[i];
		s[i]=s[i-1]+a[i];
	} 
	int target=s[n]/3;
	int cnt=0;
	for(int i=1;i<=n;i++)
	{
		if(s[i]!=target) continue;
		for(int j=i+1;j<n;j++)
		{
			if(s[n]-s[j]!=target) continue;
			cnt++;				
		}
	}
	std::cout<<cnt<<'\n';
}
signed main() 
{
	int t;
	t=1;
	//std::cin>>t;
	while(t--)
	{
		solve();
	} 
	return 0;
}

?思考一下，上面的代码是枚举所有可能的（i,j)符合条件就++。试想一下如果我们手算这个题会怎么做呢？是不是确定第一段之后去数有第二段有多少种情况？比如：

4?

1 2 3 3

i走到2时发现满足条件，我们去后面找有几个满足条件的，发现只有一个，加上1，没有再满足条件的i了，因此答案就是1。

反过来是不是也一样呢？数一数前面有多少种情况，一旦后面有满足条件的j就加上前面的和。

因为后段至少有两个数，因此i属于[1,n-2],判断s[1]是否等于target。前段至少有两个数，故而j属于[3,n],判断s[n]-s[j-1]是否等于target。

i从1-n-2顺着走，判断是否满足条件，满足则cnt++，说明目前前段有cnt种情况，只需要有一个j>i且满足条件就可以确定以j为第二段的一共有cnt种情况，答案加上cnt即可。

?AC代码：

#include <bits/stdc++.h>
using ll=long long;
const int N=2e5+10;
int a[N],s[N];
void solve()
{
	int n;
	std::cin>>n;
	for(int i=1;i<=n;i++)
	{
		std::cin>>a[i];
		s[i]=s[i-1]+a[i];
	} 
	if(s[n]%3||n<3)
	{
		std::cout<<0<<'\n';
		return ;
	}
	int target=s[n]/3;
	ll cnt=0,res=0; 
	for(int i=1;i<=n-2;i++)
	{
		if(s[i]==target) cnt++;
		int j=i+2;
		if(s[n]-s[j-1]==target) res+=cnt;
	}
	std::cout<<res<<'\n';
}
signed main() 
{
	int t;
	t=1;
	//std::cin>>t;
	while(t--)
	{
		solve();
	} 
	return 0;
}

发散一下，发现这种需要求l满足某个条件，r满足某个条件的情况一共有多少，都可以这样，数前面满足条件的个数，一旦后面符合条件了，可以确定以r结尾的情况有cnt种，res+=cnt，On就可以解决。

差分

3729. 改变数组元素 - AcWing题库

给定数组i，每次对前i个数操作，把后面的a[i]个数字变成1，输出操作后的数组。

（感觉我好像不是很会算时间复杂度，下次再问吧。。

这题标签是差分，我想了好久也没有想出来。。后来想着用前缀和标注前面有多少个1，这样也是不对的，譬如0 3 0 0 1 3，最后就变成7个1了，然后就想到标记1的区间并更新。

博主比较憨，一说区间就想到左右区间，发现顺着做1-n，也比较麻烦因为如果前面是0，后面出现非0了还要回退更新。因此，不妨倒着做看看，从n-1，倒着做有个好处就是完全不需要回退！！比如 1 0 2 0，从后往前走，最后一位是0了说明它就只能是0，因为后面不存在数字能更新它！！因此右区间是固定的，我们只需要找左区间并更新。

举个栗子看看：

0 3 0 0 1 3

最后一位是3，则左区间就是i-3+1，如果当前数在左区间的右边就需要变成1。

需要维护左区间让它尽量多的感染数字变成1，左区间要取小的。

思路就出来辣：

从n-1：

? ? ? ? 左区间=min（左区间，i-a[i]+1）

? ? ? ? if(i<左区间）a[i]=1

#include<bits/stdc++.h>
const int N=2e5+10;
int a[N];

void solve()
{
	int n;
	std::cin>>n;
	
	for(int i=1;i<=n;i++)
	{
		std::cin>>a[i];
		a[i]=std::min(a[i],i);
	} 
	int l=1e9;
	for(int i=n;i>=1;i--)
	{
		l=std::min(l,i-a[i]+1);
		if(l<=i) a[i]=1;
	}
	for(int i=1;i<=n;i++) std::cout<<a[i]<<" ";
	std::cout<<'\n';
}
signed main()
{
	int t=1;
	std::cin>>t;
	while(t--)
	{
		solve();
	}
	return 0;
}