题意：给定一个字符串集合S，定义P(S)为所有字符串的公共前缀长度与S中字符串个数的乘积，从中选出一个集合S，使得P（S）最大
思路：也是一道Trie树的应用，在每个节点在加上一个当前到此节点的字符串个数就行了
#include#include #include #include using namespace std; const int MAXN = 10000010; struct Trie{ int ch[MAXN][2]; int val[MAXN]; int n[MAXN]; int sz; void initTrie(){ sz = 1,memset(ch[0],0,sizeof(ch[0])); memset(val,0,sizeof(val)); memset(n,0,sizeof(n)); } int idx(char c){ return c - '0'; } void insert(char *s){ int u = 0,len = strlen(s); for (int i = 0; i < len; i++){ int c = idx(s[i]); if (!ch[u][c]){ memset(ch[sz],0,sizeof(ch[sz])); n[sz] = i+1; ch[u][c] = sz++; } u = ch[u][c]; val[u]++; } } }trie; int main(){ int t,m; char str[300]; scanf("%d",&t); while (t--){ scanf("%d",&m); trie.initTrie(); while (m--){ scanf("%s",str); trie.insert(str); } int ans = -1; for (int i = 1; i < trie.sz; i++) ans = max(ans,trie.n[i]*trie.val[i]); printf("%d\n",ans); } return 0; }