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.
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