题意:给定一个长度为n的数组a[1..n],有一幅完全图,满足(u,v)的边权为a[u] xor a[v] 求边权和最小的生成树,你需要输出边权和还有方案数对1e9+7取模的值。 由于边权是xor得到,容易想到用trie统计。。 按照当前最高位0/1将当前区间内的点分成两个部分s/t,那么答案肯定是s的最小生成树+t的最小生成树+s-t的最小边,s-t最小边用trie统计,最小生成树递归处理。 那么方案数的话就是每次那个连接两个块之间的最小边的数量,所以trie树统计一下节点个数就好。 字典树那个地方每次查询一个数…

2017年9月8日 0条评论 5点热度 阅读全文

Description 一个字符串的前缀是指包含该字符第一个字母的连续子串,例如:abcd的所有前缀为a, ab, abc, abcd。 给出一个字符串S,求其所有前缀中,字符长度与出现次数的乘积的最大值。 例如:S = “abababa” 所有的前缀如下: “a”, 长度与出现次数的乘积 1 * 4 = 4, “ab”,长度与出现次数的乘积 2 * 3 = 6, “aba”, 长度与出现次数的乘积 3 * 3 = 9, “abab”, 长度与出现次数的乘积 4 * 2 = 8, “ababa”, 长度与出现次数的…

2017年8月3日 0条评论 2点热度 阅读全文