郑州专业网站建设公司详情,wordpress淘宝模板,淘宝客免费建网站,十大景观设计网站前缀和
3956. 截断数组 - AcWing题库 一看到题目很容易想到的思路是对数组求前缀和#xff0c;然后枚举两个分段点就好#xff0c;时间复杂度是On^2#xff0c;n是1e5会t#xff0c;需要优化。 朴素的代码#xff0c;会超时#xff1a;
#include bits/stdc.h
u…前缀和
3956. 截断数组 - AcWing题库 一看到题目很容易想到的思路是对数组求前缀和然后枚举两个分段点就好时间复杂度是On^2n是1e5会t需要优化。 朴素的代码会超时
#include bits/stdc.h
using lllong long;
const int N2e510;
int a[N],s[N];
void solve()
{int n;std::cinn;for(int i1;in;i){std::cina[i];s[i]s[i-1]a[i];} int targets[n]/3;int cnt0;for(int i1;in;i){if(s[i]!target) continue;for(int ji1;jn;j){if(s[n]-s[j]!target) continue;cnt; }}std::coutcnt\n;
}
signed main()
{int t;t1;//std::cint;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种情况只需要有一个ji且满足条件就可以确定以j为第二段的一共有cnt种情况答案加上cnt即可。 AC代码
#include bits/stdc.h
using lllong long;
const int N2e510;
int a[N],s[N];
void solve()
{int n;std::cinn;for(int i1;in;i){std::cina[i];s[i]s[i-1]a[i];} if(s[n]%3||n3){std::cout0\n;return ;}int targets[n]/3;ll cnt0,res0; for(int i1;in-2;i){if(s[i]target) cnt;int ji2;if(s[n]-s[j-1]target) rescnt;}std::coutres\n;
}
signed main()
{int t;t1;//std::cint;while(t--){solve();} return 0;
} 发散一下发现这种需要求l满足某个条件r满足某个条件的情况一共有多少都可以这样数前面满足条件的个数一旦后面符合条件了可以确定以r结尾的情况有cnt种rescntOn就可以解决。
