首页 > 代码库 > UVA 11488 - Hyper Prefix Sets(Trie)
UVA 11488 - Hyper Prefix Sets(Trie)
UVA 11488 - Hyper Prefix Sets
题目链接
题意:给一些01串,定义一个P(s)表示:拥有相同长度前缀的字符串个数 * 该前缀长度,求最大的P(S)
思路:Trie,建好Trie树后dfs一遍记录答案最大值
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int SIGMA_SIZE = 2; struct Node { Node *ch[2]; int val; Node() { ch[0] = ch[1] = NULL; val = 0; } }; struct Trie { Node *root; int ans; int idx(char c) { return c - '0'; } void init() { ans = 0; root = new Node(); } void insert(char *s) { int n = strlen(s); Node *u = root; for (int i = 0; i < n; i++) { int c = idx(s[i]); if (u->ch[c] == NULL) { u->ch[c] = new Node(); } u = u->ch[c]; u->val++; } } void dfs(Node *u, int d) { if (u == NULL) return; ans = max(ans, d * u->val); for (int c = 0; c < SIGMA_SIZE; c++) dfs(u->ch[c], d + 1); } void del(Node *u) { if (u == NULL) return; for (int c = 0; c < SIGMA_SIZE; c++) del(u->ch[c]); delete u; } int solve() { dfs(root, 0); del(root); return ans; } }; Trie gao; int t, n; char str[205]; int main() { scanf("%d", &t); while (t--) { gao.init(); scanf("%d", &n); while (n--) { scanf("%s", str); gao.insert(str); } printf("%d\n", gao.solve()); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。