Hướng dẫn giải của Hoán vị dài nhất
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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.
Bình luận