Hướng dẫn giải của Hàng cây
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
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; }
Bình luận