Hướng dẫn giải của Khai bút đầu xuân
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 ladpro98
program sopenp; uses math; type e=record v,p:longint; end; const fi=''; maxn=1 shl 20; maxH=2*trunc(1e6); var f,a:array[1..maxn] of longint; b:array[1..maxn] of e; count:array[0..maxH] of longint; n,l,r,i,d:longint; inp:text; procedure play(bound,m:longint); var l,r,c,v:longint; begin l:=1;c:=0; for r:=1 to n do begin v:=a[r]; if count[v] = 0 then inc(c); inc(count[v]); while c>bound do begin v:=a[l]; dec(count[v]); if count[v]=0 then dec(c); inc(l); end; f[r]:=f[r]+m*(r-l+1); end; end; procedure output; var i:longint; res:int64; begin res:=0; for i:=1 to n do inc(res,int64(f[i])); write(res); end; procedure input; var inp:text; i:longint; begin assign(inp,fi);reset(inp); readln(inp,n,l,r); for i:=1 to n do begin read(inp,b[i].v); b[i].p:=i; end; close(inp); end; procedure sort(l,r:longint); var i,j:longint; p,t:e; begin if l>=r then exit; i:=l;j:=r; p:=b[random(r-l+1)+l]; repeat while b[i].v<p.v do inc(i); while b[j].v>p.v do dec(j); if i<=j then begin if i<j then begin t:=b[i]; b[i]:=b[j]; b[j]:=t; end; inc(i);dec(j); end; until i>j; sort(l,j);sort(i,r); end; procedure discrete; var i:longint; begin d:=2; a[b[1].p]:=d; for i:=2 to n do begin if b[i].v<>b[i-1].v then inc(d); a[b[i].p]:=d; end; end; begin input; sort(1,n); discrete; play(r,1); fillchar(count,sizeof(count),0); play(l-1,-1); output; end.
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; MAXN=1100000; var new,ind,a:array[1..MAXN] of longint; count:array[1..MAXN] of byte; low,high,n:longint; f1,f2:text; 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,low,high); for i:=1 to n do read(f1,a[i]); for i:=1 to n do ind[i]:=i; end; procedure swap(var a,b:longint); var temp:longint; begin temp:=a; a:=b; b:=temp; end; procedure sort(l,r:longint); var mid,i,j:longint; begin i:=l; j:=r; mid:=a[l+random(r-l+1)]; repeat while a[i]<mid do inc(i); while a[j]>mid do dec(j); if i<=j then begin swap(a[i],a[j]); swap(ind[i],ind[j]); inc(i); dec(j); end; until i>j; if i<r then sort(i,r); if l<j then sort(l,j); end; procedure solve; var i,j:longint; begin j:=0; for i:=1 to n do if a[i]>a[i-1] then begin inc(j); new[ind[i]]:=j end else new[ind[i]]:=j; end; function cal(x:longint):longint; var j,sl,i,kq:longint; begin fillchar(count,sizeof(count),0); sl:=0; j:=1; kq:=0; for i:=1 to n do begin inc(count[new[i]]); if count[new[i]]=1 then inc(sl); while sl>x do begin if j>0 then begin dec(count[new[j]]); if count[new[j]]=0 then dec(sl); end; inc(j); end; kq+=i-j+1; end; exit(kq); end; procedure ans; begin writeln(f2,cal(high)-cal(low-1)); end; begin openF; inp; sort(1,n); solve; ans; closeF; end.
Code mẫu của hieult
#include<cstdio> #include<cmath> #include<cstring> #include<cstdlib> #include<cassert> #include<ctime> #include<algorithm> #include<iterator> #include<iostream> #include<cctype> #include<string> #include<vector> #include<map> #include<set> #include<queue> #include<list> //#include<conio.h> #define ep 0.000000001 #define maxn 10011 #define oo 1111111 #define modunlo 1000000000 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) #define fi first #define se second double const PI=4*atan(1); using namespace std; typedef pair<int, int> II; typedef vector<int> VI; typedef vector<II> VII; typedef vector<VI> VVI; typedef vector<VII> VVII; int a[1111111],n,l,u,f[1111111]; pair<int, int> A[1111111]; long long tinh(int x){ memset(f,0,sizeof(f)); if(x==0) return 0; int cuoi = -1; int so = 0; long long kq = 0; for(int i = 0;i<n;i++){ if(so<=x && cuoi!=n) for(cuoi = cuoi+1;cuoi<n;cuoi++){ if(f[a[cuoi]]>0) f[a[cuoi]]++; else{ so++; f[a[cuoi]] = 1; } if(so>x) break; } kq += cuoi-i; f[a[i]]--; if(f[a[i]]==0) so--; //cuoi--; } return kq; } int main(){ //freopen("input.in","r",stdin); //freopen("output.out","w",stdout); scanf("%d %d %d",&n,&l,&u); for(int i = 0;i<n;i++){ scanf("%d",&A[i].fi); A[i].se = i; } sort(A, A + n); a[A[0].se] = 0; for(int i = 1; i < n; i++){ if(A[i].fi > A[i - 1].fi){ a[A[i].se] = a[A[i - 1].se] + 1; } else a[A[i].se] = a[A[i - 1].se]; } long long kq1,kq2; kq1 = tinh(u); // for(int i = 0;i<n;i++) M[a[i]] = 0; kq2 = tinh(l-1); printf("%lld",kq1-kq2); // getch(); }
Code mẫu của ll931110
program SEQ5; const input = ''; output = ''; maxn = 1 shl 20; var a,pos,c,x,y: array[1..maxn] of longint; b: array[1..maxn] of cardinal; n,l,u: longint; res: int64; procedure init; var f: text; i: longint; begin assign(f, input); reset(f); readln(f, n, l, u); for i := 1 to n do begin readln(f, b[i]); pos[i] := i; end; close(f); end; procedure qsort(low,high: longint); var i,j,x1: longint; p,x2: cardinal; begin if low >= high then exit; i := low; j := high; p := b[random(high - low + 1) + low]; repeat while b[i] < p do inc(i); while b[j] > p do dec(j); if i <= j then begin if i < j then begin x2 := b[i]; b[i] := b[j]; b[j] := x2; x1 := pos[i]; pos[i] := pos[j]; pos[j] := x1; end; inc(i); dec(j); end; until i > j; qsort(low,j); qsort(i,high); end; procedure construct; var i,ct: longint; begin ct := 1; a[pos[1]] := 1; for i := 2 to n do begin if b[i] > b[i - 1] then inc(ct); a[pos[i]] := ct; end; end; procedure solve; var i,j,k,ct: longint; begin fillchar(c, sizeof(c), 0); j := 1; ct := 1; c[a[1]] := 1; for i := 1 to n do begin while (ct < l) and (j <= n) do begin inc(j); if j <= n then begin if c[a[j]] = 0 then inc(ct); inc(c[a[j]]); end else break; end; x[i] := j; dec(c[a[i]]); if c[a[i]] = 0 then dec(ct); end; j := 1; fillchar(c, sizeof(c), 0); c[a[1]] := 1; ct := 1; for i := 1 to n do begin while (ct <= u) and (j <= n) do begin inc(j); if j <= n then begin if c[a[j]] = 0 then inc(ct); inc(c[a[j]]); end; end; if j > n then begin for k := i to n do y[k] := n; break; end; y[i] := j - 1; dec(c[a[i]]); if c[a[i]] = 0 then dec(ct); end; res := 0; for i := 1 to n do if x[i] <> 0 then res := res + int64(y[i] - x[i] + 1); end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, res); close(f); end; begin init; qsort(1,n); construct; solve; printresult; end.
Bình luận