UESTC 846 -- 方師傅的01串

題目大意：方師傅過生日啦，于是蟹毛買了N個

01

串，想送給方師傅，但是蟹毛覺得這些

01

串不夠美，于是他想從中選出一些送給方師傅，蟹毛對于p個

01

串的美值定義為： 這些

01

串的最長公共字首的長度×p，是以蟹毛想從N個

01

串中選出一些，使得這些

01

串的美值最高，請告訴蟹毛最好的美值是多少。

代碼實作：

#include<iostream>
#include<string>
#include<cstdlib>
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int max_v;
struct tree{
    int cnt;
    tree *next[2];
}*root;
tree *Create(){
    tree *p;
    p=(tree *)malloc(sizeof(tree));
    p->cnt=0;
    for(int i=0;i<2;++i) p->next[i]=NULL;
    return p;
}
void Insert(string &str){
    tree *p=root;
    int i=0,x;
    while(str[i]){
        x=str[i++]-'0';
        if(p->next[x]==NULL) p->next[x]=Create();
        p=p->next[x];
        p->cnt++;
    }
}
void Search(tree *p,int le){
    max_v=Max(max_v,p->cnt*le);
    if(p->next[0]!=NULL) Search(p->next[0],le+1);
    if(p->next[1]!=NULL) Search(p->next[1],le+1);

}
int main(){
    int n;
    string str;
    while(cin>>n){
        root=Create();
        while(n--){
            cin>>str;
            Insert(str);
        }
        max_v=0;
        Search(root,0);
        cout<<max_v<<endl;
    }
}
           

結構體tree裡維護兩個變量：從cnt 和 deep，結果即為 cnt*deep 的最大值

#include<iostream>
#include<string>
#include<cstdlib>
#define Max(a,b) ((a)>(b)?(a):(b))
using namespace std;
int max_v;
struct tree{
    int cnt,deep;
    tree *next[2];
}*root;
tree *Create(){
    tree *p;
    p=(tree *)malloc(sizeof(tree));
    p->cnt=0,p->deep=0;
    for(int i=0;i<2;++i) p->next[i]=NULL;
    return p;
}
void Insert(string &str){
    tree *p=root;
    int i=0,x;
    while(str[i]){
        x=str[i++]-'0';
        if(p->next[x]==NULL) p->next[x]=Create();
        p->next[x]->deep=p->deep+1;
        p=p->next[x];
        p->cnt++;
        max_v=Max(max_v,p->cnt*p->deep);
    }
}
int main(){
    int n;
    string str;
    while(cin>>n){
        root=Create();
        max_v=0;
        while(n--){
            cin>>str;
            Insert(str);
        }
        cout<<max_v<<endl;
    }
}