UVa11488-Hyper Prefix Sets（trie树）
本帖最后由 wuyvzhang 于 2016-8-2 17:24 编辑 <br /><br />H
Hyper Prefix Sets
Prefix goodness of a set string is length of longest common prefix*number of strings in the set. For example the prefix goodness of the set {000,001,0011} is 6.You are given a set of binary strings. Find the maximum prefix goodness
among all possible subsets of these binary strings.
Input
First line of the input contains T(≤20) the number of test cases. Each of the test cases start with n(≤50000) the number of strings. Each of the next n lines contains a string containing only 0 and 1. Maximum length of each of these string is 200.
Output
For each test case output the maximum prefix goodness among all possible subsets of n binary strings.
Sample Input Output for Sample Input
4
4
0000
0001
10101
010
2
01010010101010101010
11010010101010101010
3
010101010101000010001010
010101010101000010001000
010101010101000010001010
5
01010101010100001010010010100101
01010101010100001010011010101010
00001010101010110101
0001010101011010101
00010101010101001
6
20
66
44
Problem Setter : Abdullah Al Mahmud
Special Thanks : Manzurur Rahman Khan
#include
#include
#include
#include
#include
#include
#include
using namespace std;
const int maxn = 5000000;
vector vs;
int cnt,ans,n;
int ch;
int val;
inline int getIdx(char a){
return a-'0';
}
void insert(string st){
int u = 0;
for(int i = 0; i < st.size(); i++){
int k = getIdx(st);
if(!ch){
memset(ch,0,sizeof ch);
val++;
ans = max(ans,val*(i+1));
ch = cnt++;
}else{
val]++;
ans = max(ans,val]*(i+1));
}
u = ch;
}
}
int main(){
int ncase;
cin >> ncase;
while(ncase--){
vs.clear();
memset(val,0,sizeof val);
memset(ch,0,sizeof ch);
cnt = 1;
ans = 0;
cin >> n;
while(n--){
string st;
cin >> st;
insert(st);
}
cout
www.138320.com SO娱乐城：真_人.足球.彩票齐全| 开户送10元.首存送58元.手机可投ち注任何游戏顶级信用ち提现即时到账SO.CC
页:
[1]