Editorial for Tổ chức đối lập
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=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.
Comments