Editorial for Dãy số
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
const fi=''; fo=''; maxn=100000; var n,sum,re,min:longint; a:array[1..maxn] of longint; procedure rf; var i:longint; begin assign(input,fi); reset(input); readln(n); sum:=0; for i:=1 to n do begin read(a[i]); sum:=sum+a[i]; end; close(input); end; procedure pr; var i,j:longint; begin re:=0; if sum>0 then begin min:=a[n]; sum:=a[n]; for i:=1 to n-1 do begin sum:=sum+a[i]; if sum<min then min:=sum; end; if min>0 then re:=1; for i:=n-1 downto 1 do begin if min<0 then min:=a[i]+min else min:=a[i]; if min>0 then inc(re); end; end; end; procedure wf; begin assign(output,fo); rewrite(output); write(re); close(output); end; begin rf; pr; wf; end.
Code mẫu của happyboy99x
#include <algorithm> #include <bitset> #include <cctype> #include <cfloat> #include <climits> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <functional> #include <list> #include <map> #include <numeric> #include <queue> #include <set> #include <stack> #include <string> #include <utility> #include <vector> using namespace std; typedef pair<int, int> ii; typedef vector<ii> vii; typedef vector<vii> vvii; typedef vector<int> vi; typedef vector<vi> vvi; #define sz(a) int((a).size()) #define fi first #define se second #define pb push_back #define mp make_pair #define all(c) (c).begin(), (c).end() #define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it) #define present(c,x) ((c).find(x) != (c).end()) #define cpresent(c,x) (find(all(c),x) != (c).end()) #define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i) #define repd(i,n) for(int i = (n)-1; i >= 0; --i ) #define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i) #define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i) #define INF 1000000000 #define N 100005 int a[N], s[N], mnl[N], mxr[N], n; //minLeft, maxRight int main() { //freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); scanf( "%d", &n ); rep(i, n) scanf( "%d", a+i ); repd(i, n) s[i] = s[i+1] + a[i]; int sum = 0; fo(i,1,n-1) mnl[i] = min( mnl[i-1], sum+=a[i-1] ); sum = 0; repd(i,n-1) mxr[i] = max( mxr[i+1], sum+=a[i+1] ); sum = 0; rep(i, n) sum += (s[i] + mnl[i] > 0) && (s[i] - mxr[i] > 0); printf( "%d\n", sum ); /*rep(i, n) printf( "%d ", s[i] ); putchar(10); rep(i, n) printf( "%d ", mnl[i] ); putchar(10); rep(i, n) printf( "%d ", mxr[i] ); putchar(10);*/ return 0; }
Code mẫu của ladpro98
program nkseq_AC; uses math; const fi=''; var a,left,right,minleft,minright:array[0..100001] of longint; n,res:longint; procedure input; var inp:text; i:longint; begin assign(inp,fi); reset(inp); readln(inp,n); for i:=1 to n do read(inp,a[i]); close(inp); end; procedure init; var i:longint; begin left[1]:=a[1]; for i:=2 to n do left[i]:=left[i-1]+a[i]; right[n]:=a[n]; for i:=n-1 downto 1 do right[i]:=right[i+1]+a[i]; minleft[1]:=left[1]; for i:=2 to n do minleft[i]:=min(minleft[i-1],left[i]); minright[n]:=left[n]; for i:=n-1 downto 1 do minright[i]:=min(minright[i+1],left[i]); end; procedure process; var i:longint; begin for i:=1 to n do begin if (minleft[i-1]+right[i]>0) and (minright[i]-left[i-1]>0) then inc(res); end; end; begin input; init; process; write(res); end.
Code mẫu của RR
uses math; var res,i,n:longint; sum,l,r,a:array[0..100111] of longint; begin read(n); for i:=1 to n do begin read(a[i]); sum[i]:=sum[i-1]+a[i]; end; l[1]:=sum[1]; for i:=2 to n do l[i]:=min(l[i-1],sum[i]); r[n]:=sum[n]; for i:=n-1 downto 1 do r[i]:=min(r[i+1],sum[i]); for i:=1 to n do if (r[i]-sum[i-1]>0) and (sum[n]-sum[i-1]+l[i]>0) then inc(res); writeln(res); end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> int min(int x,int y) { if(x<y) return x; return y; } main() { int n,a[100001],A[100001],B[100002],l[100001],r[100001],KQ=0; scanf("%d",&n); A[0]=0;B[n+1]=0; for(int i=1;i<=n;i++) { scanf("%d",&a[i]); A[i]=A[i-1]+a[i]; } l[1]=a[1],r[n]=a[n];l[0]=0; for(int i=n;i>=1;i--) B[i]=B[i+1]+a[i]; for(int i=2;i<=n;i++) l[i]=min(l[i-1],A[i]); for(int i=n-1;i>=1;i--) r[i]=min(r[i+1]+a[i],a[i]); for(int i=1;i<=n;i++) { if(r[i]>0&&B[i]+l[i-1]>0) KQ++; } printf("%d",KQ); //getch(); }
Code mẫu của ll931110
Program NKSEQ; Const input = ''; output = ''; max = 100000; Type arr = array[1..max] of longint; Var a,l,rmin,rmax,left,right: arr; n: longint; Procedure init; Var f: text; i: longint; Begin Assign(f, input); Reset(f); Readln(f, n); For i:= 1 to n do read(f, a[i]); Close(f); End; Procedure solve; Var f: text; i,num: longint; Begin left[1]:= a[1]; For i:= 2 to n do left[i]:= left[i - 1] + a[i]; right[n]:= a[n]; For i:= n - 1 downto 1 do right[i]:= right[i + 1] + a[i]; l[1]:= left[1]; For i:= 2 to n do if left[i] < l[i - 1] then l[i]:= left[i] else l[i]:= l[i - 1]; rmin[n]:= right[n]; For i:= n - 1 downto 1 do if right[i] < rmin[i + 1] then rmin[i]:= right[i] else rmin[i]:= rmin[i + 1]; rmax[n]:= right[n]; For i:= n - 1 downto 1 do if right[i] > rmax[i + 1] then rmax[i]:= right[i] else rmax[i]:= rmax[i + 1]; num:= 0; If (a[1] > 0) and (l[n] > 0) then inc(num); If (a[n] > 0) and (a[n] + l[n - 1] > 0) then inc(num); For i:= 2 to n - 1 do if (a[i] > 0) and (right[i] - rmax[i + 1] > 0) and (right[i] + l[i - 1] > 0) then inc(num); Assign(f, output); Rewrite(f); Writeln(f, num); Close(f); End; Begin init; solve; End.
Code mẫu của khuc_tuan
#include <iostream> using namespace std; int n; int a[100010], s[100010], minl[100010], minr[100010]; int main() { scanf("%d", &n); for(int i=0;i<n;++i) { scanf("%d", a+i); s[i] = a[i] + (i==0?0:s[i-1]); minl[i] = s[i]; if(i>0) minl[i] <?= minl[i-1]; } for(int i=n-1;i>=0;--i) { minr[i] = s[i]; if(i+1<n) minr[i] <?= minr[i+1]; } int res = 0; for(int i=0;i<n;++i) { bool ok = true; if(minr[i]-(i==0?0:s[i-1])<=0) ok = false; int seg = s[n-1] - (i==0?0:s[i-1]); if(i>0 && seg+minl[i-1]<=0) ok = false; res += ok; } cout << res << endl; return 0; }
Comments