Editorial for Hàng cây
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
const fi=''; fo=''; maxn=100000; var n,re,dem:longint; a,b,d:array[1..maxn] of longint; procedure rf; var i:longint; begin assign(input,fi); reset(input); readln(n); for i:=1 to n do begin read(a[i]); b[i]:=i; end; close(input); end; procedure sort(l,r:longint); var i,j,x,y,xx:longint; begin i:=l; j:=r; x:=a[(i+j) div 2]; xx:=b[(i+j) div 2]; repeat while (a[i]<x) or ((a[i]=x) and (b[i]<xx)) do i:=i+1; while (a[j]>x) or ((a[j]=x) and (b[j]>xx)) do j:=j-1; if i<=j then begin y:=a[i]; a[i]:=a[j]; a[j]:=y; y:=b[i]; b[i]:=b[j]; b[j]:=y; i:=i+1; j:=j-1; end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; function check(x:longint):boolean; begin check:=(x>0) and (x<=n); end; procedure pr; var cur,i:longint; begin sort(1,n); fillchar(d,sizeof(d),0); dem:=0; re:=0; cur:=1; repeat inc(re); while d[b[cur]]=1 do inc(cur); d[b[cur]]:=1; inc(dem); for i:=0 to 1 do if check(b[cur]-1+2*i) and (d[b[cur]-1+2*i]=0) then begin inc(dem); d[b[cur]-1+2*i]:=1; end; inc(cur); until dem=n; 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 <iostream> #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 bool dead[N]; int n; int main() { //freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); scanf( "%d", &n ); priority_queue< ii, vii, greater<ii> > qu; fo(i,1,n) { int t; scanf( "%d", &t ); qu.push(ii(t, i)); } int res = 0; for(; !qu.empty(); qu.pop()) { int v = qu.top().se; if( dead[v] == 0 ) { dead[v] = dead[v-1] = dead[v+1] = 1; ++res; } } printf( "%d\n", res ); return 0; }
Code mẫu của ladpro98
program firs; uses math; const fi=''; maxN=123456; type e=record v,pos:longint; end; var a:array[1..maxN] of e; p:array[1..maxN] of longint; check:array[1..maxN] of boolean; 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 begin read(inp,a[i].v); a[i].pos:=i; end; close(inp); end; procedure swap(i,j:longint); var t:e; begin t:=a[i]; a[i]:=a[j]; a[j]:=t; end; procedure sort(l,r:longint); var i,j:longint; p:e; begin if l>=r then exit; p:=a[random(r-l+1)+l]; i:=l;j:=r; repeat while (a[i].v<p.v) or ((a[i].v=p.v) and (a[i].pos<p.pos)) do inc(i); while (a[j].v>p.v) or ((a[j].v=p.v) and (a[j].pos>p.pos)) do dec(j); if i<=j then begin if i<j then swap(i,j); inc(i); dec(j); end; until i>j; sort(l,j);sort(i,r); end; procedure init; var i:longint; begin for i:=1 to n do p[a[i].pos]:=i; end; procedure process; var i:longint; begin for i:=1 to n do if not check[i] then begin inc(res); check[i]:=true; if a[i].pos>1 then check[p[a[i].pos-1]]:=true; if a[i].pos<n then check[p[a[i].pos+1]]:=true; end; end; begin input; sort(1,n); init; process; write(res); end.
Code mẫu của RR
//Written by RR {$ifdef rr} {$r+,q+} {$mode objfpc} {$inline off} {$else} {$r-,q-} {$mode objfpc} {$inline on} {$endif} uses math; const FINP = ''; FOUT = ''; MAXN = 100111; snode = 262144; var f1,f2 : text; n,dead : longint; nn : array[1..snode] of longint; a : array[1..MAXN] of longint; 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 read(f1,a[i]); end; procedure init(i,l,r:longint); inline; var mid,x,y:longint; begin if (l=r) then begin nn[i]:=l; exit; end; mid:=(l+r)>>1; init(i<<1,l,mid); init(i<<1+1,mid+1,r); x:=nn[i<<1]; y:=nn[i<<1+1]; if a[x]<=a[y] then nn[i]:=x else nn[i]:=y; end; procedure update(i,l,r,u:longint); inline; var mid,x,y:longint; begin if (l>r) then exit; if (u<l) or (r<u) then exit; if (u=l) and (r=u) then exit; mid:=(l+r)>>1; update(i<<1,l,mid,u); update(i<<1+1,mid+1,r,u); x:=nn[i<<1]; y:=nn[i<<1+1]; if a[x]<=a[y] then nn[i]:=x else nn[i]:=y; end; procedure solve; var time,u:longint; begin dead:=0; time:=0; while dead<n do begin inc(time); u:=nn[1]; if (u>1) and (a[u-1]<MAXN) then begin a[u-1]:=MAXN; update(1,1,n,u-1); inc(dead); end; if (a[u]<MAXN) then begin a[u]:=MAXN; update(1,1,n,u); inc(dead); end; if (u<n) and (a[u+1]<MAXN) then begin a[u+1]:=MAXN; update(1,1,n,u+1); inc(dead); end; end; writeln(f2,time); end; begin openF; inp; init(1,1,n); solve; closeF; end.
Code mẫu của hieult
#include <stdio.h> //#include <conio.h> void Quicksort(long A[],long a[],long x,long y) { long t=A[(x+y)/2]; long i=x; long j=y; while(i<=j) { while(A[i]<t) i++; while(A[j]>t) j--; if(i<=j) { long tg=A[i]; A[i]=A[j]; A[j]=tg; long tga=a[i]; a[i]=a[j]; a[j]=tga; i++; j--; } } if(j>x) Quicksort(A,a,x,j); if(i<y) Quicksort(A,a,i,y); } main() { long n,A[100002],a[100002],Free[100002],u=1,v,dem=0; scanf("%ld",&n); for(long i=1;i<=n;i++) { scanf("%ld",&A[i]); a[i]=i; Free[i]=0; } A[n+1]=0; Quicksort(A,a,1,n); while(u!=n&&u!=n+1) { if(A[u]!=A[u+1]) u++; else { v=u+1; while(A[v]==A[v+1]) v++; Quicksort(a,Free,u,v); u=v+1; } } //printf("%ld %ld %ld ",n,a[1],Free[a[1]]); for(long i=1;i<=n;i++) if(Free[a[i]]==0) { Free[a[i]]=1; Free[a[i]-1]=1; Free[a[i]+1]=1; dem++; } printf("%ld",dem); //getch(); }
Code mẫu của ll931110
{$MODE DELPHI} program FIRS; uses math; const input = ''; output = ''; maxn = 100000; maxv = 10000000; type rec = record val,pos: integer; end; var a: array[1..maxn] of integer; s: array[1..8 * maxn] of rec; n,res,u,v: integer; procedure init; var f: text; i: integer; begin assign(f, input); reset(f); readln(f, n); for i := 1 to n do read(f, a[i]); close(f); for i := 1 to 8 * maxn do s[i].val := maxv; end; procedure combine(i: integer); begin s[i].val := min(s[2 * i].val,s[2 * i + 1].val); if s[2 * i + 1].val < s[2 * i].val then s[i].pos := s[2 * i + 1].pos else s[i].pos := s[2 * i].pos; end; procedure build(i,low,high: integer); var mid: integer; begin if low > high then exit; if low = high then begin s[i].val := a[low]; s[i].pos := low; exit; end; mid := (low + high) div 2; build(2 * i,low,mid); build(2 * i + 1,mid + 1,high); combine(i); end; procedure update(i,low,high: integer); var mid: integer; begin if (v < low) or (high < u) then exit; if s[i].val = maxv then exit; if (u <= low) and (high <= v) then begin s[i].val := maxv; s[i].pos := 0; exit; end; mid := (low + high) div 2; update(2 * i,low,mid); update(2 * i + 1,mid + 1,high); combine(i); end; procedure solve; var t: integer; begin res := 0; repeat t := s[1].pos; if t <> 0 then begin inc(res); u := t - 1; v := t + 1; if t = 1 then u := 1 else if t = n then v := n; update(1,1,n); end; until s[1].pos = 0; end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, res); close(f); end; begin init; build(1,1,n); solve; printresult; end.
Code mẫu của skyvn97
#include<stdio.h> #include<queue> #define MAX 100100 using namespace std; typedef pair<int,int> ii; bool b[MAX]; int n,c; priority_queue<ii,vector<ii>,greater<ii> > q; void init(void) { int i,x; scanf("%d",&n); for (i=1;i<=n;i=i+1) { scanf("%d",&x); q.push(ii(x,i)); b[i]=true; } } void process(void) { c=0; ii x; int i; while (!q.empty()) { while ((!q.empty()) && (!b[q.top().second])) q.pop(); if (!q.empty()) { x=q.top(); q.pop(); c=c+1; for (i=-1;i<=1;i=i+1) b[x.second+i]=false; } } printf("%d",c); } int main(void) { init(); process(); }
Code mẫu của khuc_tuan
#include <iostream> #include <cstdio> #include <cstring> #include <string> #include <cmath> #include <sstream> #include <cstdlib> #include <algorithm> #include <map> #include <set> #include <queue> using namespace std; #define Rep(i,n) for(int i=0,lll=(n);i<lll;++i) #define For(i,a,b) for(int i=(a),lll=(b);i<=lll;++i) #define Ford(i,a,b) for(int i=(a),lll=(b);i>=lll;--i) #define pb push_back #define MP make_pair #define fi first #define se second #define nextint __nextint() inline int __nextint() { int x; scanf("%d", &x); return x; } const int MAXN = 100010; int n; int a[MAXN]; int mm[MAXN * 4]; // bool mark[MAXN]; void init(int n, int l, int r) { if(l==r) { // cout << l << " " << a[l] << " day " << endl; mm[n] = a[l]; return; } else { int m = (l+r) / 2; init(2 *n, l,m ); init(2*n+1,m+1,r); mm[n] = min(mm[n*2], mm[n*2+1]); } } int findmin(int n, int l, int r) { // cout << "find min " << n << " " << l << " " << r << endl; if(l==r) return l; int m = (l+r) / 2; if(mm[n] == mm[2*n]) return findmin(2*n,l,m); else return findmin(2*n+1,m+1,r); } int getvalue(int n,int l, int r, int pos) { if(l==r) return mm[n]; else { int m = (l+r) / 2; if(pos <= m) return getvalue( 2 * n, l, m, pos); else return getvalue( 2 * n + 1, m +1, r, pos); } } void update(int n, int l, int r, int pos, int val) { if(l==r) { mm[n] = val; return; } else { int m = (l+r) / 2; if(pos <= m) update( 2 * n, l, m, pos, val); if(m < pos) update(2*n+1,m+1,r,pos,val); mm[n] = min(mm[n*2], mm[n*2+1]); } } int main() { scanf("%d", &n); Rep(i,n) scanf("%d", a+i); init(1,0,n-1); //cout << mm[1] << " " << mm[2] << " " << mm[3] << endl; int ngay = 0; while(true) { int pos = findmin( 1, 0, n-1); int value = getvalue( 1, 0, n-1, pos); // printf("%d %d\n", pos, value); if(value >= 1000000) break; else { ++ngay; update( 1, 0, n-1, pos, 1000000); if(pos > 0) update( 1, 0, n-1, pos - 1, 1000000); if(pos + 1 < n) update( 1, 0, n-1, pos + 1, 1000000); } } printf("%d\n", ngay); return 0; }
Comments