0
已解决
资深天翼
#pragma GCC optimize(3)
#pragma GCC target("avx")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("inline")
#pragma GCC optimize("-fgcse")
#pragma GCC optimize("-fgcse-lm")
#pragma GCC optimize("-fipa-sra")
#pragma GCC optimize("-ftree-pre")
#pragma GCC optimize("-ftree-vrp")
#pragma GCC optimize("-fpeephole2")
#pragma GCC optimize("-ffast-math")
#pragma GCC optimize("-fsched-spec")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("-falign-jumps")
#pragma GCC optimize("-falign-loops")
#pragma GCC optimize("-falign-labels")
#pragma GCC optimize("-fdevirtualize")
#pragma GCC optimize("-fcaller-saves")
#pragma GCC optimize("-fcrossjumping")
#pragma GCC optimize("-fthread-jumps")
#pragma GCC optimize("-funroll-loops")
#pragma GCC optimize("-fwhole-program")
#pragma GCC optimize("-freorder-blocks")
#pragma GCC optimize("-fschedule-insns")
#pragma GCC optimize("inline-functions")
#pragma GCC optimize("-ftree-tail-merge")
#pragma GCC optimize("-fschedule-insns2")
#pragma GCC optimize("-fstrict-aliasing")
#pragma GCC optimize("-fstrict-overflow")
#pragma GCC optimize("-falign-functions")
#pragma GCC optimize("-fcse-skip-blocks")
#pragma GCC optimize("-fcse-follow-jumps")
#pragma GCC optimize("-fsched-interblock")
#pragma GCC optimize("-fpartial-inlining")
#pragma GCC optimize("no-stack-protector")
#pragma GCC optimize("-freorder-functions")
#pragma GCC optimize("-findirect-inlining")
#pragma GCC optimize("-fhoist-adjacent-loads")
#pragma GCC optimize("-frerun-cse-after-loop")
#pragma GCC optimize("inline-small-functions")
#pragma GCC optimize("-finline-small-functions")
#pragma GCC optimize("-ftree-switch-conversion")
#pragma GCC optimize("-foptimize-sibling-calls")
#pragma GCC optimize("-fexpensive-optimizations")
#pragma GCC optimize("-funsafe-loop-optimizations")
#pragma GCC optimize("inline-functions-called-once")
#pragma GCC optimize("-fdelete-null-pointer-checks")
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
int n,w,ans,cnt;
int a[150000];
int main(){
scanf("%d",&n);
scanf("%d",&w);
int h=n,i=0;
while(h--){
i++;
scanf("%d",&a[i]);
}
int x=n;
i=0;
while(x--){
i++;
ans=0;
for(int j=i;j<=n;j++){
ans+=a[j];
if(ans==w){
cnt++;
break;
}
}
}
printf("%d",cnt);
return 0;
}
"完美"70
陈曦在2021-08-06 16:35:14追加了内容
时间复杂度最高1008ms
0
已采纳
新手天翼
@陈曦 你这样用双重循环铁定会TLE，解决如下：
1.循环剪枝：当加到的数值大于w时，循环break结束。
2.排个序，将大于w的数字都舍去，只在小于w里的数值中枚举，也可以应用上面的剪枝。
或者用别的方法：
1.深度优先搜索：dfs（i, j, sum），搜索从i到j的值，存进sum中，返回如下：dfs(i+1, j, sum-a[i])或者dfs(i, j+1, sum+a[j])或者dfs(i+1, j+1, sum+a[i]+a[j])，这样搜索枚举也可以节约时间，搜索边界是if（sum==a）｛return ans+1;｝
2.在条件允许的情况下，使用二维前缀和sum[i][j]，i，j代表从i到j，sum[i][j]存的值是i到j的和。不必使用双重循环，再输入时：for(...){
输入；
sum[1][t++]=输入的数;
}
然后（不必双重循环）
for(...){
sum[i][1]+=数组[i];
}
还有不懂的洛谷私信我
刘乐宸在2021-08-08 20:07:24追加了内容
@陈曦 会了吗？
0
资深光能
等网好的时候再提交
0
缔造者之神
这个要优化算法了，超时1000ms！（我试着提交了一下）
不行的话直接看测试点（我可以帮忙）
0
初级天翼
仔细算一下时间复杂度，再提交
曹灿阳在2021-08-06 21:48:10追加了内容
都这种时候了，火车头就不要再加了
0
中级天翼
再提交一遍，说不定能卡过去
0
被禁言
中级光能
不行，用滑动窗口
while(1){
...
}
0
初级天翼
我疑惑，这么多头文件干嘛的
0
初级天翼
干啥的
