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.

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

Please read the guidelines before commenting.


There are no comments at the moment.