Editorial for ARITHMETIC PROGRESSION


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

uses math;
const fi='';
      maxn=100010;
var n,i,re,nn:longint;
    a,b,l,r,d,c:array[0..maxn] of longint;
    f:array[1..maxn,1..100] of longint;

procedure sort(l,r:longint);
var i,j,x,y,t:longint;
begin
     i:=l; j:=r; x:=a[(i+j) shr 1]; t:=d[(i+j) shr 1];
     repeat
           while (a[i]<x) or ((a[i]=x) and (d[i]<t)) do inc(i);
           while (a[j]>x) or ((a[j]=x) and (d[j]>t)) do dec(j);
           if i<=j then
           begin
                y:=a[i]; a[i]:=a[j]; a[j]:=y;
                y:=d[i]; d[i]:=d[j]; d[j]:=y;
                inc(i); dec(j);
           end;
     until i>j;
     if i<r then sort(i,r);
     if l<j then sort(l,j);
end;

procedure edit;
var i:longint;
begin
     c[0]:=-maxlongint;
     for i:=1 to n do
     begin
          if a[i]>c[nn] then
          begin
               r[nn]:=i-1;
               inc(nn);
               c[nn]:=a[i];
               l[nn]:=i;
          end;
          b[d[i]]:=nn;
     end;
     r[nn]:=n;
end;

function bs(ll,rr,val:longint):longint;
var mid,i,l,r:longint;
begin
     bs:=0; l:=ll; r:=rr;
     while l<=r do
     begin
          mid:=(l+r) shr 1;
          if d[mid]<val then l:=mid+1
          else r:=mid-1;
     end;
     for i:=mid+1 downto mid-1 do
         if (i>=ll) and (i<=rr) and (d[i]<val) then exit(d[i]);
end;

procedure pr;
var i,j,dif,x,y:longint;
begin
     for i:=1 to n do
     begin
          x:=b[i];
          for j:=x-1 downto 1 do
          begin
               dif:=c[x]-c[j];
               if dif>100 then break
               else
               begin
                    y:=bs(l[j],r[j],i);
                    if y=0 then continue;
                    f[i,dif]:=max(f[i,dif],f[y,dif]+1);
                    re:=max(re,f[i,dif]);
               end;
          end;
     end;
end;

begin
     assign(input,fi); reset(input);
     read(n);
     for i:=1 to n do
     begin
          read(a[i]); d[i]:=i;
     end;
     sort(1,n);
     edit;
     pr;
     writeln(re+1);
     close(input);
end.

Code mẫu của ladpro98

#include <bits/stdc++.h>
#define X first
#define Y second
const int N = 100005;
const int oo = 1000000009;
const int lim = 100;
using namespace std;
int n, res, f[N], b[N];
pair<int, int> a[N], u;
int main()
{
    scanf("%d", &n);
    int i, j, pos, res = 0, v;
    for(i=1; i<=n; i++) {
        scanf("%d", &v);
        a[i] = make_pair(v, i);
    }
    sort(a+1, a+n+1);

    for(j=1; j<=lim; j++) {
        pos = 0; for(i=1; i<=n; i++) f[i] = 1;
        for(i=2; i<=n; i++) {
            u = pair<int, int> (a[i].X - j, a[i].Y);
            while (pos < n && a[pos + 1] <= u) pos++;
            if (a[pos].X == u.X && a[pos].Y < u.Y)
                f[i] = f[pos] + 1;
            res = max(res, f[i]);
        }
    }
    printf("%d", res);
    return 0;
}

Code mẫu của RR

{$R+,Q+}
uses math;
const
  FINP='';
  FOUT='';
  MAXN=100001;
  hashkey=100003;
type
  list=^node;
  node=record
         u:longint;
         next:list;
       end;
var
  f1,f2:text;
  kq,n:longint;
  a:array[1..MAXN] of longint;
  h:array[0..hashkey] of list;
  d:array[1..MAXN,1..100] of longint;
procedure openF; inline;
begin
  assign(f1,FINP); reset(f1);
  assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
  close(f1); close(f2);
end;
procedure inp; inline;
var
  i:longint;
begin
  read(f1,n);
  for i:=1 to n do
    read(f1,a[i]);
end;
function find(x:longint):longint; inline;
var
  p:list;
  u:longint;
begin
  p:=h[abs(x) mod hashkey];
  while p<>nil do
    begin
      u:=p^.u; p:=p^.next;
      if a[u]=x then exit(u);
    end;
  exit(0);
end;
procedure push(x:longint); inline;
var
  p:list;
  u,gt:longint;
begin
  gt:=abs(a[x]) mod hashkey;
  p:=h[gt];
  while p<>nil do
    begin
      u:=p^.u;
      if a[u]=a[x] then begin p^.u:=x; exit; end;
      p:=p^.next;
    end;
  new(p); p^.u:=x; p^.next:=h[gt]; h[gt]:=p;
end;
procedure solve; inline;
var
  i,csc,k:longint;
begin
  kq:=1;
  for csc:=1 to 100 do d[1,csc]:=1;
  push(1);
  for i:=2 to n do
    for csc:=1 to 100 do
      begin
        k:=find(a[i]-csc);
        if k>0 then d[i,csc]:=d[k,csc]+1
        else d[i,csc]:=1;
        push(i);
        kq:=max(kq,d[i,csc]);
      end;
end;
procedure ans; inline;
begin
  writeln(f2,kq);
end;
begin
  openF;
  inp;
  solve;
  ans;
  closeF;
end.

Code mẫu của hieult

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>
//#include <conio.h>

//double const PI=4*atan(1);

using namespace std;

struct so{
      int gt,tt;
};

bool cmp1(so A1,so A2){
      return A1.gt<A2.gt;
}

bool cmp2(so A1,so A2){
      return A1.tt<A2.tt;
}

int n,f[100011][102],g[10111111],tong,kq;
so A[111111];

int main(){
   // freopen("LEM5.in","r",stdin);
      scanf("%d",&n);
      for(int i = 1;i<=n;i++){
            scanf("%d",&A[i].gt);
            A[i].tt = i;
      }
      sort(A+1,A+n+1,cmp1);
      tong = A[1].gt; A[1].gt = 0; 
     // for(int i = 1;i<=n;i++) printf("%d ",A[i].gt);
      for(int i = 1;i<n;i++){
           if(A[i+1].gt-tong-A[i].gt>100)
                 tong+=A[i+1].gt-tong-A[i].gt-101;
           A[i+1].gt-= tong;
      }

      sort(A+1,A+n+1,cmp2);
     // for(int i = 1;i<=n;i++) printf("%d ",A[i].gt);

      memset(g,0,sizeof(g));
      kq = 0;
      for(int i = 1;i<=n;i++){
            for(int j = 1;j<=100;j++){
                  if(A[i].gt-j>=0 &&g[A[i].gt-j]>0)
                        f[i][j] = f[g[A[i].gt-j]][j]+1;
                  else f[i][j] = 1;
                  kq = max(kq,f[i][j]);
                 // printf("%d\n",kq);
            }
            g[A[i].gt] = i;
      }
      printf("%d",kq);
     // getch();
}

Code mẫu của skyvn97

#include<algorithm>
#include<cstdio>
#include<map>
#include<vector>
#define MAXN   100100
#define MAXD   100
#define FOR(i,a,b) for (int i=(a),_b=(b);i<=_b;i=i+1)
#define REP(i,n) for (int i=0,_n=(n);i<_n;i=i+1)
#define fi   first
#define se   second
using namespace std;
int a[MAXN],pos[MAXN];
pair<vector<int>,int>* add[MAXN][MAXD+7];
map<int,pair<vector<int>,int> > haveVal;
int f[MAXN][MAXD];
int n;
void init(void) {
    scanf("%d",&n);
    FOR(i,1,n) scanf("%d",&a[i]);
}
bool CompPos(const int &x,const int &y) {
    return (a[x]<a[y]);
}
bool findVal(int &id,int val) {
    while (id>=1 && a[pos[id]]>val) id--;
    return (id>=1 && a[pos[id]]==val);
}
void prepare(void) {
    FOR(i,1,n) pos[i]=i;
    sort(pos+1,pos+n+1,CompPos);
    FOR(i,1,n) haveVal[a[i]].fi.push_back(i);
    for (map<int,pair<vector<int>,int> >::iterator it=haveVal.begin();it!=haveVal.end();it++) it->se.se=0;
    FOR(i,1,n) {
        int curPos=pos[i];
        int prevPos=pos[i-1];
        int id=i;
        FOR(k,1,MAXD) {
            if (i>1 && a[prevPos]-1>=a[curPos]-k) add[curPos][k]=add[prevPos][a[prevPos]-a[curPos]+k];
            else add[curPos][k]=findVal(id,a[curPos]-k)?&haveVal[a[curPos]-k]:NULL;
        }
    }
}
int getLastPos(int i,int j) {
    if (add[i][j]==NULL) return (-1);
    vector<int> &cur=add[i][j]->fi;
    int &id=add[i][j]->se;
    while (id<cur.size() && cur[id]<i) id++;
    return (id==0?-1:cur[id-1]);
}
void optimize(void) {
    int res=0;
    FOR(i,1,n) FOR(j,1,MAXD) {
        int k=getLastPos(i,j);
        if (k<1) f[i][j]=1; else f[i][j]=f[k][j]+1;
        res=max(res,f[i][j]);
    }
    printf("%d\n",res);
}
int main(void) {
    init();
    prepare();
    optimize();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.