Problem
小b有一个01序列A,她想知道A有多少个非空连续子序列和为S。
你能帮帮她吗?
Solution
暴力,可以搞一下剪枝。
另外也可以枚举位置,建一个mp[num],记录枚举到i位置时,前面的每个前缀和num出现过几次,每次把当前前缀和减去m在之前出现的数量加入答案即可。
Code
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| #include<cstdio> #include<iostream> #include<algorithm> #include <iomanip> #include<map> #include<cstring> #define io_opt ios::sync_with_stdio(false);cin.tie(0);cout.tie(0) #define ll long long using namespace std; int n,s,ans; int a[30020]; int main(){ io_opt; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; a[i]+=a[i-1]; } cin>>s; int cs=(s==0||s==1)?0:s-1; for(int i=1;i<=n-cs;i++){ for(int j=i+cs;j<=n;j++){ if(a[j]-a[i-1]>s) break; if(a[j]-a[i-1]==s) ans++; } } cout<<ans<<endl; return 0; }
|