BZOJ 2251 Trie树

思路:

i~n加到Trie树里 经过的边权+1

DFS一遍 搞定~

//By SiriusRen
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define N 3005
int n,all;char a[N];
struct Trie{int next[2],num;}trie[N*N];
void insert(int x){
int now=0;
for(int i=x;i<=n;i++){
if(!trie[now].next[a[i]])
trie[now].next[a[i]]=++all;
now=trie[now].next[a[i]],trie[now].num++;
}
}
void dfs(int x){
if(trie[x].num>1)printf("%d\n",trie[x].num);
if(trie[x].next[0])dfs(trie[x].next[0]);
if(trie[x].next[1])dfs(trie[x].next[1]);
}
int main(){
scanf("%d%s",&n,a+1);
for(int i=1;i<=n;i++)a[i]-='0';
for(int i=1;i<=n;i++)insert(i);
dfs(0);
}

BZOJ 2251 Trie树

上一篇:Chapter 21_5.2 tab扩展


下一篇:Effective C++ 之 Item 2:尽量以 const, enum, inline 替换 #define