Editorial for Hoán vị dài nhất


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

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;

int n, a[100100], pos[100100], prev[100100], next[100100];

int solve()
{
    int res = 0;
    for (int i = 0; i <= n; i++) pos[i] = -1;
    for (int i = 0; i < n; i++) 
    {
        prev[i] = pos[a[i]];
        if (pos[a[i]] >= 0) next[pos[a[i]]] = i;
        pos[a[i]] = i;
    }
    for (int i = 0; i < n; i++) 
        if (pos[a[i]] >= 0) next[pos[a[i]]] = n;

    for (int i = 0; i < n; i++)
        if (a[i] == 1)
        {
            res = max(res, 1);
            int R = i, bound = next[i], mx = 1;
            for (int j = i - 1; j >= 0 && next[j] > i; j--)
            {
                bound = min(bound, next[j]);
                R = min(R, next[j] - 1);
                mx = max(mx, a[j]);
                if (mx <= res || bound - j < mx) continue;
                while (R - j + 1 < mx && R + 1 < bound && a[R + 1] < mx) R++;
                if (R - j + 1 == mx) res = mx;
            }
        }

    return res;
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) scanf("%d", a + i);
    int ans = solve();
    reverse(a, a + n);
    ans = max(ans, solve());
    cout << ans << endl;
}

Code mẫu của ladpro98

#include <bits/stdc++.h>
const int N = 100005;
using namespace std;
int res, n, a[N], pos[N];

void Play(int len) {
    int mi = n, ma = 0;
    for(int i=1; i<=len; i++) {
        if (pos[i] == 0) break;
        mi = min(mi, pos[i]);
        ma = max(ma, pos[i]);
        if (ma - mi == i-1)
            res = max(res, i);
    }
}

int main()
{
    //freopen("NKLP.in", "r", stdin);
    scanf("%d\n", &n);
    int i, l, r;
    for(i=1; i<=n; i++) scanf("%d", &a[i]);
    n++;a[n] = a[n-1]; l = 1;
    for(r=1; r<=n; r++) {
        if (pos[a[r]]>0) {
            if (res < r-l) Play(r-l);
            while (a[l] != a[r]) {
                pos[a[l]] = 0; l++;
            }l++;
        }
        pos[a[r]] = r;
    }
    printf("%d", res);
    return 0;
}

Code mẫu của RR

//Written by Nguyen Thanh Trung
//O(N) algorithm
{$R+,Q+}
{$Mode objFPC}
uses math;
const
  FINP          =       '';
  FOUT          =       '';
  MAXN          =       100111;
type
  status        =       record
                                left,right      :       longint;
                                wrong,ln        :       longint;
                        end;
var
  f1,f2         :       text;
  n,kq          :       longint;
  a,dd          :       array[1..MAXN] of longint;
  sum           :       array[-1..MAXN] of int64;
  last,now      :       status;

procedure openF;
    begin
      assign(f1,FINP); reset(f1);
      assign(f2,FOUT); rewrite(f2);
    end;
procedure closeF;
    begin
      close(f1);
      close(f2);
    end;
procedure inp;
    var
      i:longint;
    begin
      read(f1,n);
      for i:=1 to n do
        begin
          read(f1,a[i]);
          sum[i]:=sum[i-1]+a[i];
        end;
    end;
procedure update;
    var
      i:longint;
    begin
      if now.left<1 then now.left:=1;
      if now.right>n then now.right:=n;
      if last.left<>now.left then
        if last.left<now.left then
          for i:=last.left to now.left-1 do
            begin
              dd[a[i]]-=1;
              if dd[a[i]]=1 then now.wrong-=1
              else if dd[a[i]]=0 then now.wrong+=1;
            end
        else for i:=last.left-1 downto now.left do
            begin
              dd[a[i]]+=1;
              if dd[a[i]]=1 then now.wrong-=1
              else if dd[a[i]]=2 then now.wrong+=1;
            end;
      if last.right<>now.right then
        if last.right>now.right then
          for i:=last.right downto now.right+1 do
            begin
              dd[a[i]]-=1;
              if dd[a[i]]=1 then now.wrong-=1
              else if dd[a[i]]=0 then now.wrong+=1;
            end
        else for i:=last.right+1 to now.right do
            begin
              dd[a[i]]+=1;
              if dd[a[i]]=1 then now.wrong-=1
              else if dd[a[i]]=2 then now.wrong+=1;
            end;
      if now.wrong<>0 then exit;
      if sum[now.right]-sum[now.left-1]<>(int64(now.ln+1)*now.ln)>>1 then exit;
      kq:=max(kq,now.ln);
    end; //update
procedure solve;
    var
      one,x:longint;
      save:status;
    begin
      for one:=1 to n do
        if a[one]=1 then
          begin
            dd[1]:=1;
            with save do
              begin
                left:=one; right:=one;
                ln:=1; wrong:=0;
              end;
            kq:=max(kq,1);
          //TH1: so lon nhat o ben trai so 1
            last:=save;
            x:=one-1;
            while (x>=1) and (a[x]<>1) do
              begin
                with now do
                  begin
                    ln:=max(ln,a[x]); wrong:=last.wrong+ln-last.ln;
                    left:=x; right:=x+ln-1;
                  end;
                x-=1; update;
                last:=now;
              end;
            now:=save; update;
          //TH2: so lon nhat o ben phai so 1
            last:=save;
            x:=one+1;
            while (x<=n) and (a[x]<>1) do
              begin
                with now do
                  begin
                    ln:=max(ln,a[x]); wrong:=last.wrong+ln-last.ln;
                    right:=x; left:=x-ln+1;
                  end;
                x+=1; update;
                last:=now;
              end;
            now:=save; update;
          end; //for one
    end; //solve

begin
  openF;
  inp;
  kq:=0;
  solve;
  writeln(f2,kq);
  closeF;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>

long long has[100001],A[100001],B[100001],KQ=0;

void kt(int n,int a[],long long x[])
{
    int t=0,max,flag=0;
    while(t++<n+1)
    {
        if(a[t]==1)
        {
                 if(KQ<1)
                      KQ = 1;
                flag = 1;
                max = 1;
        }
        else if(flag!=0)
        {
            if(a[t]>max) max = a[t];
            if(max<=t && x[t]-x[t-max]==has[max] && KQ<max)
                KQ = max;
        }
    }
}

int main()
{
    int n,a[100001],b[100001];
    scanf("%d",&n);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        b[n+1-i] = a[i];
    }
    A[0]= 0; B[0] = 0;has[0] =0;
    for(int i = 1;i<=n;i++)
    {
        has[i] = has[i-1]+i*i + i + 1;
        A[i] = A[i-1]+a[i]*a[i] + a[i] +1;
        B[i] = B[i-1]+b[i]*b[i]+b[i]+1;
    }
    kt(n,a,A);kt(n,b,B);
    printf("%lld",KQ);
   // getch();
}

Code mẫu của skyvn97

#include<bits/stdc++.h>
using namespace std;

const int N = 100000;
int last[N], a[N], d[N], n;

void enter() {
    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i], --a[i];
}

void precal() {
    fill(last, last+n, n);
    d[n-1] = n; last[a[n-1]] = n-1;
    for(int i = n-2; i >= 0; --i) {
        d[i] = min(d[i+1], last[a[i]]);
        last[a[i]] = i;
    }
}

bool mark[N];

void solve() {
    int res = 0, now = 0;
    for(int i = 0, j = 0; i < n; ++i) {
        while(j < d[i]) {
            mark[a[j++]] = true;
            while(now < n && mark[now]) ++now;
            res = max(res, now);
        }
        mark[a[i]] = false;
        now = min(now, a[i]);
    }
    cout << res << endl;
}

int main() {
    ios::sync_with_stdio(false);
    enter();
    precal();
    solve();
    return 0;
}

Code mẫu của khuc_tuan

const
fin = '';
fout= '';
maxn= 100001;
type
arr1 = array[1..maxn] of longint ;
var
fi, fo : text ;
vt1, a, back : arr1 ;
maxb, maxa : arr1 ;
result, n : longint ;
procedure nhap;
var
i : longint ;
begin
assign( fi, fin);
reset( fi);
read( fi, n);
for i:=1 to n do read( fi, a[i]);
close( fi);
end;
procedure init_back;
var
i : longint ;
begin
for i:=1 to n do
begin
back[i] := vt1[a[i]];
vt1[a[i]] := i;
end;
end;
procedure ii( var max, pos : arr1 );
var
i,l,r,g : longint ;
begin
for i:=1 to n do
begin
l := 1;
r := n;
while l<=r do
begin
g := (l+r) div 2;
if max[g]<pos[i] then max[g] := pos[i];
if g<i then l := g+1
else if g>i then r := g-1
else break;
end;
end;
end;
function getmax( var max, pos : arr1; x, y : longint ) : longint ;
var res : longint ;
procedure getmax2( l, r : longint );
var
g : longint ;
begin
if l>r then exit;
g := (l+r) div 2;
if (x<=l) and (r<=y) then
begin
if res<max[g] then res := max[g];
exit;
end;
if (x<=g) and (g<=y) then
if res<pos[g] then res := pos[g];
if (x<g) then getmax2( l, g-1);
if (g<y) then getmax2( g+1, r);
end;
begin
res := 0;
getmax2( 1, n);
getmax := res ;
end;
function getindexmax( x, y, mm : longint ) : longint ;
var ind : longint ;
procedure gg( l, r : longint);
var
g : longint ;
begin
if l>r then exit;
if ind<>0 then exit;
g := (l+r) div 2;
if (x<=l) and (r<=y) and (maxa[g]<mm) then exit;
if (x<=g) and (g<=y) then
if mm=a[g] then ind := g;
if (x<g) then gg( l, g-1);
if (g<y) then gg( g+1, r);
end;
begin
ind := 0;
gg( 1, n);
getindexmax := ind;
end;
procedure init_vt1;
var
i : longint ;
begin
vt1[n+1] := n+1;
for i:=n downto 1 do
if a[i]=1 then vt1[i] := i
else vt1[i] := vt1[i+1];
end;
procedure process;
var
t, l, r, g, en, st : longint ;
begin
en := 0;
for st:=1 to n do
begin
if en<st then en := st ;
while (en<n) and (getmax( maxb, back, st, en+1) <st) do inc(en);
g := vt1[st];
l := g;
r := en;
while l<=r do
begin
if r-st+1<=result then break;
t := getmax( maxa, a, st, r);
if t=r-st+1 then
begin
if result<t then result := t;
break;
end;
if t>r-st+1 then
begin
{ if mark[r]<=t then break;
if mark[r]>t then mark[r] := t;}
r := getindexmax( st, r, t) - 1;
end;
end;
end;
end;
procedure xuly;
begin
init_back;
init_vt1;
ii( maxb, back);
ii( maxa, a);
process;
end;
procedure ghi;
begin
assign( fo, fout);
rewrite( fo);
writeln( fo, result);
close( fo);
end;
begin
nhap;
xuly;
ghi;
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.