Hướng dẫn giải của Tổ chức đối lập
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=10001; var n,k,re:longint; b,sl,pos,cur:array[1..maxn] of longint; a:array[1..maxn shl 1] of longint; procedure rf; var i:longint; begin assign(input,fi); reset(input); read(k,n); for i:=1 to n-1 do begin read(b[i]); inc(sl[b[i]]); end; pos[1]:=1; cur[1]:=1; for i:=2 to n+1 do begin pos[i]:=pos[i-1]+sl[i-1]; cur[i]:=pos[i]; end; for i:=1 to n-1 do begin a[cur[b[i]]]:=i+1; inc(cur[b[i]]); end; close(input); end; function dfs(x:longint):longint; var i,r:longint; begin r:=1; for i:=pos[x] to pos[x+1]-1 do r:=r+dfs(a[i]); if r>=k then begin r:=0; inc(re); end; dfs:=r; end; procedure pr; var i:longint; begin re:=0; i:=dfs(1); end; procedure wf; begin assign(output,fo); rewrite(output); writeln(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(); i != _e; ++i) #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 10005 int a[N], n, k, d[N]; //a[i] = lowest ancestor of i //d[i] = number of decestor of i int main() { #ifndef ONLINE_JUDGE freopen( "input.txt", "r", stdin ); //freopen( "output.txt", "w", stdout ); #endif scanf("%d%d",&k,&n); a[1] = 0; fo(i,2,n) { scanf("%d",a+i); for(int j = a[i]; j; j = a[j]) ++d[j]; } int res = 0; fod(i,n,1) if( d[i] + 1 >= k ) { ++res; for(int j = a[i]; j; j = a[j]) d[j] -= d[i]+1; } printf("%d\n", res); return 0; }
Code mẫu của ladpro98
program v8org; uses math; const maxn=12345; fi=''; var adj,link:array[1..maxn] of longint; head,f:array[1..maxn] of longint; k,n,m,res:longint; procedure input; var inp:text; i,p:longint; begin assign(inp,fi);reset(inp); readln(inp,k);readln(inp,n); for i:=2 to n do begin read(inp,p); inc(m); adj[m]:=i; link[m]:=head[p]; head[p]:=m; end; close(inp); end; procedure dfs(i:longint); var j:longint; begin if head[i]=0 then begin if k>1 then f[i]:=1 else begin f[i]:=0; inc(res); end; exit; end; j:=head[i]; f[i]:=1; while j<>0 do begin dfs(adj[j]); inc(f[i],f[adj[j]]); j:=link[j]; end; if f[i]>=k then begin f[i]:=0; inc(res); end; end; begin input; dfs(1); write(res); end.
Code mẫu của RR
PROGRAM V8ORG; CONST fi=''; fo=''; maxn=10000; VAR n,k:integer; sc:array[1..maxn] of integer; son:array[1..maxn,1..maxn] of integer; sl:array[1..maxn] of integer; dd:integer; Procedure ReadInput; Var f:text; u,i:integer; Begin Assign(f,fi); Reset(f); Readln(f,k); Readln(f,n); For i:=2 to n do begin Read(f,u); inc(sc[u]); son[u,sc[u]]:=i; end; End; Procedure DFS(u:integer); Var i,v:integer; Begin sl[u]:=1; For i:=1 to sc[u] do begin v:=son[u,i]; DFS(v); sl[u]:=sl[u]+sl[v]; end; If sl[u]>=k then begin inc(dd); sl[u]:=0; end; End; Procedure WriteOutput; Var f:text; Begin Assign(f,fo); Rewrite(f); Writeln(f,dd); Close(f); End; BEGIN ReadInput; DFS(1); WriteOutput; 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 100111 #define oo 1111111111 #define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++) 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 n,k,cha[11111],d[11111],x,KQ=0; int main(){ //freopen("V8ORG.in","r",stdin); scanf("%d %d",&k,&n); for(int i = 2;i<=n;i++){ scanf("%d",&cha[i]); d[i] = 0; x = i; do{ x = cha[x]; d[x]++; }while(x!=1); } cha[1] = 1; // for(int i = 1;i<=n;i++) printf("%d %d\n",i,cha[i]);getch(); for(int i = n;i>=1;i--){ if(d[i]>=k-1){ KQ++; x = i; do{ // printf("%d\n",x); x = cha[x]; d[x] -= (d[i]+1); }while(x!=1); } } printf("%d",KQ); // getch(); }
Code mẫu của ll931110
{$MODE DELPHI} program V8ORG; const input = ''; output = ''; maxn = 10000; type pnode = ^tnode; tnode = record val: integer; link: pnode; end; var n,k,count: integer; d,t,pre: array[1..maxn] of integer; dep: array[1..maxn] of pnode; procedure add(i,x: integer); var p: pnode; begin new(p); p^.val := x; p^.link := dep[i]; dep[i] := p; end; procedure init; var f: text; i: integer; begin assign(f, input); reset(f); read(f, k, n); t[1] := 1; d[1] := 0; for i := 1 to n do dep[i] := nil; for i := 2 to n do begin read(f, pre[i]); t[i] := 1; d[i] := d[pre[i]] + 1; add(d[i],i); end; close(f); end; procedure solve; var v,i: integer; p: pnode; begin for i := n downto 1 do begin p := dep[i]; while p <> nil do begin v := p^.val; if t[v] >= k then inc(count) else t[pre[v]] := t[pre[v]] + t[v]; p := p^.link; end; end; if t[1] >= k then inc(count); end; procedure printresult; var f: text; begin assign(f, output); rewrite(f); writeln(f, count); close(f); end; begin init; solve; printresult; end.
Code mẫu của khuc_tuan
type PNode = ^Node; Node = record i : integer; next : PNode; end; var n, k, res : integer; ke : array[1..10000] of PNode; function dfs(i : integer) : integer; var p : PNode; sc, j : integer; begin p := ke[i]; sc := 1; while p<>nil do begin j := p^.i; sc := sc + dfs(j); p := p^.next; end; if sc>=k then begin inc(res); sc := 0; end; dfs := sc; end; var p : PNode; i,x : integer; begin read( k, n); for i:=2 to n do begin read(x); new(p); p^.i := i; p^.next := ke[x]; ke[x] := p; end; res := 0; dfs(1); writeln( res); end.
Bình luận