2014 UESTC Training for Data Structures J - 方师傅的01串

J - 方师傅的01串

Time Limit: 3000/1000MS (Java/Others)
    Memory Limit: 65535/65535KB (Java/Others)

Submit Status

方师傅过生日啦,于是蟹毛买了N个01串,想送给方师傅。

但是蟹毛觉得这些01串不够美,于是他想从中选出一些送给方师傅。

蟹毛对于p个01串的美值定义为:
这些01串的最长公共前缀的长度×p

所以蟹毛想从N个01串中选出一些,使得这些01串的美值最高。

请告诉蟹毛最好的美值是多少。

Input

输入第1行包含1个整数N,表示蟹毛买到的01串的个数。

接下来N行,每行包含1个01串。

N≤50000,每个01串长度不超过200

Output

输出包含1个整数,代表最高的美值。

Sample input and output













Sample Input Sample Output
4
0000
0001
10101
010
6
5
01010101010100001010010010100101
01010101010100001010011010101010
00001010101010110101
0001010101011010101
00010101010101001

44

 题意求多个01串的最长公共前缀的长度×p的最大值

无比简单的trie,简单到可以直接用二叉树模拟,就是直接用数组模拟,

N的子节点是2*n和2*n+1,N的父节点是N/2;

左节点是0,右节点是1,直接建树加一个dfs搜索一下整棵树就OK啦


#include <iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
struct node
{
struct node* left;
struct node* right;
int data;
};

int maxn=-1;

using namespace std;

void build(char* z,node* p)
{
node* pi;
if (z[0]==‘\0‘) return;
if (z[0]==‘1‘) {
if (p->left==NULL){
pi=(node*)malloc(sizeof(node));
pi->left=NULL;
pi->right=NULL;
pi->data=0;
p->left=pi;
}
(p->left)->data++;
build(z+1,p->left);
return;
}
if (z[0]==‘0‘){
if (p->right==NULL){
pi=(node*)malloc(sizeof(node));
pi->left=NULL;
pi->right=NULL;
pi->data=0;
p->right=pi;
}
(p->right)->data++;
build(z+1,p->right);
return;
}
}
void suan(node* p,int j)
{
if (p->data*j>maxn) maxn=p->data*j;
if (p->left!=NULL) suan((p->left),j+1);
if (p->right!=NULL) suan((p->right),j+1);
}
int main()
{
int n;
char z[202]={‘\0‘};
scanf("%d",&n);
node *head;
head=(node*)malloc(sizeof(node));
head->left=NULL;
head->right=NULL;
head->data=0;
while (n--){
scanf("%s",z);
build(z,head);
}
suan(head,0);
printf("%d\n",maxn);
return 0;
}

2014 UESTC Training for Data Structures J - 方师傅的01串,布布扣,bubuko.com

时间: 04-28

2014 UESTC Training for Data Structures J - 方师傅的01串的相关文章

2014 UESTC Training for Data Structures K - 方师傅与栈

K - 方师傅与栈 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status 方师傅有一个1?N的排列,排列的顺序是固定的,他想要把这个排列重新排列成他喜欢的顺序. 于是他买了一个栈,他会按顺序将排列扔进栈内,在某些时刻将栈顶元素取出,这样出栈后的排列就可以重新排序啦. 例如,原序列是1,2,他先将1入栈,再将2入栈,然后将2出栈,最后将1出栈,那么新序列就变

2014 UESTC Training for Data Structures C - 东风不与周郎便

C - 东风不与周郎便 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status "揽二乔于东南兮,乐朝夕之与共" 一首铜雀台赋,将愤怒与恐惧散播在了孙吴大军之中. 对抗曹军,万事俱备,只欠东风. 现在已经找到n个风眼,这些风眼的东风有强有弱,诸葛亮说他每次祈风都能够将一段风眼的东风增强,但需人去帮他布阵.同时他需要时刻掌控风眼的状况,以确定下一步的

2014 UESTC Training for Data Structures A - Islands

A - Islands Time Limit: 30000/10000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status Deep in the Carribean, there is an island even stranger than the Monkey Island, dwelled by Horatio Torquemada Marley. Not only it has a re

2014 UESTC Training for Data Structures F - 天下归晋

F - 天下归晋 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status 晋朝统一天下已有十年,曹魏.孙吴.蜀汉这些曾与天下相争的王朝,都成为了过眼云烟,仅留于故事之中. "爷爷,讲嘛讲嘛,再讲一次赤壁之战的故事嘛!" "你个死小子,都讲多少遍了,还听!" "就是想听打仗嘛!" "你小子啊...行,

2014 UESTC Training for Data Structures E - 休生伤杜景死惊开

E - 休生伤杜景死惊开 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status 陆伯言军陷八卦阵之中,分明只是一条直路,却怎的也走不到尽头.阵中尽是石堆,以某一石堆为参考,无论向走还是向右,总是会回到出发的石堆,最后幸得一黄姓老翁带路才得脱出. 陆伯言逃离八卦阵后,来到山顶观察此阵,记从左往右第i堆石堆的高度为Ai,发现任何两堆较矮的石堆都能和它们之间的一

2014 UESTC Training for Data Structures D - 长使英雄泪满襟

看出司马懿在等蜀军粮草不济,孔明于是下令分兵屯田以备久战. 司马懿日日只是闭营不出.孔明每日思虑对策至天明,却也无可奈何. 漫天星辰中有一类星叫做将星,它们随着将魂的燃烧会越发明亮. 今夜五丈原的星空格外璀璨. 司马懿一声轻叹.五丈原的星,要落了. Input 第一行输入三个整数,n,W,H,分别表示有n颗星,矩形宽W,高H,. 接下来n行,每行三个整数,xi,yi,wi.表示第i颗星星的在天空的位置是(xi,yi),亮度是wi. 1≤n≤100000,1≤W,H≤1000000,0≤x,y≤1

2014 UESTC Training for Data Structures G - 程序设计竞赛

G - 程序设计竞赛 Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status "你动规无力,图论不稳,数据结构松散,贪心迟钝,没一样像样的,就你还想和我同台竞技,做你的美梦!今天这场比赛,就是要让你知道你是多么的无能!!" 不训练,无以为战.有n项能力是ACM竞赛要求的,训练则能提升,忽略则会荒废. 这m天,你能做到如何. Input 第一行两个整

2014 UESTC Training for Data Structures H - Cookies Test

H - Cookies Test Time Limit: 3000/1000MS (Java/Others)     Memory Limit: 65535/65535KB (Java/Others) Submit Status As chief programmer at a cookie production plant you have many responsibilities, one of them being that the cookies produced and packag

2017 UESTC Training for Data Structures

2017 UESTC Training for Data Structures A    水,找区间极差,RMQ怼上去. #include<bits/stdc++.h> using namespace std; #pragma comment(linker, "/STACK:102400000,102400000") #define rep(i,a,b) for (int i=a;i<=b;i++) #define per(i,b,a) for (int i=b;i&