Editorial for Tin mật
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 max=500050; var m,n,i,j,x,re,num:longint; f:array[0..max,0..1] of longint; g,s:array[0..max] of longint; a:array[1..11111] of longint; procedure put(nd,pos:longint); var z,y:longint; begin z:=a[pos]; if f[nd,z]=0 then begin inc(num); f[nd,z]:=num; end; y:=f[nd,z]; if pos=x then inc(g[y]) else put(y,pos+1); s[nd]:=s[y]+g[y]; if f[nd,1-z]>0 then inc(s[nd],s[f[nd,1-z]]+g[f[nd,1-z]]); end; procedure check(nd,pos:longint); var y,z:longint; begin z:=a[pos]; if f[nd,z]=0 then exit; y:=f[nd,z]; re:=re+g[y]; if pos=x then re:=re+s[y] else check(y,pos+1); end; begin read(n,m); for i:=1 to n do begin read(x); for j:=1 to x do read(a[j]); put(0,1); end; for i:=1 to m do begin read(x); for j:=1 to x do read(a[j]); re:=0; check(0,1); writeln(re); end; end.
Code mẫu của happyboy99x
#include<cstdio> struct trieNode { int next[2], nfinish, ncross; } trie[500000+5]; int m, n, a[10000+5], nnode; void mark(int * a, int n) { int u = 0; ++trie[0].ncross; for(int i = 0; i < n; ++i) { if(trie[u].next[a[i]] == 0) trie[u].next[a[i]] = ++nnode; u = trie[u].next[a[i]]; ++trie[u].ncross; } ++trie[u].nfinish; } void query(int * a, int n) { int u = 0, res = 0, ok = 1; for(int i = 0; i < n; ++i) if(trie[u].next[a[i]]) { u = trie[u].next[a[i]]; res += trie[u].nfinish; } else { ok = 0; break; } if(ok) res += trie[u].ncross - trie[u].nfinish; printf("%d\n", res); } int enter(int * a) { int l; scanf("%d", &l); for(int i = 0; i < l; ++i) scanf("%d", a+i); return l; } int main() { scanf("%d%d", &m, &n); for(int i = 0; i < m; ++i) mark(a, enter(a)); for(int i = 0; i < n; ++i) query(a, enter(a)); return 0; }
Code mẫu của RR
{$R+,Q+} uses math; const FINP=''; FOUT=''; type trie=^node; node=record last,g:longint; l,r:trie; end; var f1,f2:text; m,n:longint; root:trie; procedure openF; begin assign(f1,FINP); reset(f1); assign(f2,FOUT); rewrite(f2); end; procedure closeF; begin close(f1); close(f2); end; procedure add(var a:trie); var p:trie; begin new(p); p^.l:=nil; p^.r:=nil; p^.last:=0; p^.g:=0; a:=p; end; procedure inp; var i,l,j,u:longint; p:trie; begin add(root); read(f1,m,n); for i:=1 to m do begin read(f1,l); p:=root; for j:=1 to l do begin read(f1,u); if u=0 then begin if p^.l=nil then add(p^.l); p:=p^.l; inc(p^.g); end else begin if p^.r=nil then add(p^.r); p:=p^.r; inc(p^.g); end; end; dec(p^.g); inc(p^.last); end; end; procedure ans; var i,l,j,u,kq:longint; p:trie; ok:boolean; begin for i:=1 to n do begin read(f1,l); kq:=0; p:=root; ok:=true; for j:=1 to l do begin read(f1,u); if not ok then continue; if u=0 then begin if p^.l=nil then ok:=false else p:=p^.l; end else begin if p^.r=nil then ok:=false else p:=p^.r; end; if ok then inc(kq,p^.last); end; if ok then inc(kq,p^.g); writeln(f2,kq); end; end; begin openF; inp; ans; closeF; end.
Code mẫu của ll931110
{$MODE DELPHI} program SEC; const input = ''; output = ''; maxn = 50000; type ptree = ^ttree; ttree = record v1,v2,ve: integer; left,right: ptree; end; var fi,fo: text; root: ptree; m,n: integer; procedure openfile; begin assign(fi, input); reset(fi); assign(fo, output); rewrite(fo); end; procedure Trie_construct; var i,j,x,v: integer; p,q: ptree; begin new(root); root^.left := nil; root^.right := nil; root^.v1 := 0; readln(fi, m, n); for i := 1 to m do begin p := root; read(fi, x); for j := 1 to x do begin read(fi, v); if v = 0 then q := p^.left else q := p^.right; if q = nil then begin new(q); q^.left := nil; q^.right := nil; q^.v1 := 0; q^.v2 := 1; q^.ve := 0; if v = 0 then p^.left := q else p^.right := q; end else inc(q^.v2); p := q; end; inc(p^.v1); inc(p^.ve); end; end; procedure Trie_calc(p: ptree); begin if p^.left <> nil then begin p^.left.v1 := p^.left.v1 + p^.v1; Trie_calc(p^.left); end; if p^.right <> nil then begin p^.right.v1 := p^.right.v1 + p^.v1; Trie_calc(p^.right); end; end; procedure solve; var i,j,x,v: integer; t1,t2,et: integer; p: ptree; begin for i := 1 to n do begin t1 := 0; t2 := 0; et := 0; p := root; read(fi, x); for j := 1 to x do begin read(fi, v); if v = 0 then p := p^.left else p := p^.right; if p = nil then begin t2 := 0; readln(fi); break; end; t1 := p^.v1; t2 := p^.v2; if j = x then et := p^.ve; end; writeln(fo, t1 + t2 - et); end; end; procedure closefile; begin close(fo); close(fi); end; begin openfile; Trie_construct; Trie_calc(root); solve; closefile; end.
Code mẫu của skyvn97
#include<bits/stdc++.h> #define MAX 50005 using namespace std; struct nod { int pa; int ch[2]; int nc; int np; int ims; nod(){} nod(const int &_pa) { pa=_pa; ch[0]=-1; ch[1]=-1; nc=0; np=0; ims=0; } }; vector<nod> trie; int id[MAX]; int m,n; void insert(const int &i,const int &j) { trie.push_back(nod(i)); trie[i].ch[j]=trie.size()-1; //printf("Inserted nod %d 's child %d at location %d\n",i,j,trie.size()-1); } void init(void) { trie.clear(); trie.push_back(nod(-1)); int i,j,t,u,v; scanf("%d",&m); scanf("%d",&n); for (i=1;i<=m;i=i+1) { scanf("%d",&t); u=0; for (j=1;j<=t;j=j+1) { scanf("%d",&v); if (trie[u].ch[v]<0) insert(u,v); u=trie[u].ch[v]; } trie[u].ims++; } for (i=1;i<=n;i=i+1) { scanf("%d",&t); u=0; for (j=1;j<=t;j=j+1) { scanf("%d",&v); if (trie[u].ch[v]<0) insert(u,v); u=trie[u].ch[v]; } id[i]=u; } } void visit(const int &u) { int i,v; for (i=0;i<2;i=i+1) { v=trie[u].ch[i]; if (v<0) continue; trie[v].np=trie[u].np+trie[u].ims; visit(v); trie[u].nc=trie[u].nc+trie[v].nc+trie[v].ims; } } void answer(void) { int i; for (i=1;i<=n;i=i+1) printf("%d\n",trie[id[i]].np+trie[id[i]].nc+trie[id[i]].ims); } int main(void) { init(); visit(0); answer(); return 0; }
Code mẫu của khuc_tuan
#include <iostream> using namespace std; struct Node { Node * next[2]; int counter, f; Node() { next[0] = next[1] = NULL; counter = f = 0; } }; Node * root; int dfs(Node * root) { if(root==NULL) return 0; root->f = dfs(root->next[0]) + dfs(root->next[1]); return root->f + root->counter; } int main() { int n, m; scanf("%d%d", &n, &m); root = new Node(); for(int k=0;k<n;++k) { int l, x; Node * p = root; scanf("%d", &l); for(int i=0;i<l;++i) { scanf("%d", &x); if(p->next[x] == NULL) p->next[x] = new Node(); p = p->next[x]; } p->counter ++ ; } dfs(root); for(int k=0;k<m;++k) { int l, x; Node * p = root; scanf("%d", &l); int dem = 0, i; for(i=0;i<l;++i) { scanf("%d", &x); if(p->next[x]==NULL) { for(int j=i+1;j<l;++j) scanf("%d", &x); break; } p = p->next[x]; dem += p->counter; } if(i==l) dem += p->f; printf("%d\n", dem); } return 0; }
Comments