【蓝桥杯】专题练习

2023-12-26 01:02:30

前缀和

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;
}

文章来源:https://blog.csdn.net/m0_74183164/article/details/135120216
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。