HDU 6034 Balala Power!【排序/进制思维】

HDU 6034 Balala Power!【排序/进制思维】

大家好,又见面了,我是全栈君。

 

Balala Power!【排序/进制思维】

Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 6703    Accepted Submission(s): 1680

Problem Description

HDU 6034 Balala Power!【排序/进制思维】


Talented 
Mr.Tang has 
n strings consisting of only lower case characters. He wants to charge them with Balala Power (he could change each character ranged from a to z into each number ranged from 0 to 25, but each two different characters should not be changed into the same number) so that he could calculate the sum of these strings as integers in base 26 hilariously.

Mr.Tang wants you to maximize the summation. Notice that no string in this problem could have leading zeros except for string “0”. It is guaranteed that at least one character does not appear at the beginning of any string.

The summation may be quite large, so you should output it in modulo 109+7 .

 
Input
The input contains multiple test cases.

For each test case, the first line contains one positive integers 
n , the number of strings. (1n100000
Each of the next n lines contains a string si consisting of only lower case letters. (1|si|100000,|si|106
 
Output
For each test case, output ”
Case #x : ” in one line (without quotes), where 
x indicates the case number starting from 1 and y denotes the answer of corresponding case.
 

 

Sample Input
1 a
2 aa bb
3 a ba abc

 
Sample Output
Case #1: 25
Case #2: 1323
Case #3: 18221
 
【题意】:给出n个字符串,对于字符a~z,赋值0~25,求在26进制下的最大值。
【分析】:

二十六
进制即为用二十六个字母替代从0到25的二十六个数字,与二进制,八进制,十进制,十六进制一样,二十六进制也可与其它进制法互相转换。

举例
例1:二十六进制转换为十进制过程。
以GWW为例,则为G(6)*26^2+W(22)*26^1+W(22)*26^0=4650
结果即为4650

注明:一般的二十六进制字母序数为:
A=0,Z=25
或A=1,Z=0

HDU 6034 Balala Power!【排序/进制思维】
HDU 6034 Balala Power!【排序/进制思维】

//官方:每个字符对答案的贡献都可以看作一个 26 进制的数字,问题相当于要给这些贡献加一个 0 到 25 的权重使得答案最大。最大的数匹配 25,次大的数匹配 24···依次类推。
 
//题目要求字符串代表的26进制数之和最大,就要将高权值尽可能地赋给26进制数中在高位出现频率更高的字母,这样,问题就分成了三部分。第一,字母按价值排序;第二,字母赋值;第三,求和。

第一步,排序问题,为了方便比较,我们建立一个26*100000的数表,记录每个字母在每一位上的出现频数,从高位开始比较出现频数最高的字母赋值为25。在这里要注意到,因为有些字母可能会在某一位出现若干多次(超过26),这样该字母在本位上的价值可能会超过更高位上的字母价值,因此,我们运用数制进位的思想,将出现频数超过26的字母向上进位,这样就保证了在高位字母价值的绝对优势。在比赛时手动进行了字母排序,不仅耗费了大量的精力,而且最终超时了。赛后看标程,才深深地体会到cmp函数的神奇。

第二步,排序完成后,字母们整齐的码在一维数组里。按价值由高到低赋值即可。但是,还要注意前导0的问题,出现在字符串首的字母是不能被赋值为0的,在这里我们将价值最低且没有出现在字符串首的字母标记出来。然后将剩余的字母按价值赋值。

第三步,求和。即26进制转10进制。我的方法和标程略有差别,标程引入了sum[ ]数组,但是时间复杂度貌似差别不大,

另外,还有一些小细节。
1.计算26^n,用打表代替快速幂取模,可以大大降低时间复杂度
2.由于进位的问题,在字符串比较和进制转化时,注意要比最长字符串的长度ml再多比较一位。

题解

 

【代码】:

 

转载于:https://www.cnblogs.com/Roni-i/p/7821854.html

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/107994.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Optimal Keypad[通俗易懂]

    Optimal Keypad[通俗易懂]Description OptimusMobilesproducesmobilephonesthatsupportSMSmessages.TheMobileshaveakeypadof12keys,numbered1to12.Thereisacharacterstringassignedtoeachkey.Totypeinthe

  • 机器学习之朴素贝叶斯分类算法

    机器学习之朴素贝叶斯分类算法一、数学知识相关1.独立事件–前提2.条件概率3.全概率公式4.贝叶斯公式5.朴素贝叶斯公式其中:P(A)叫做A事件的先验概率,即一般情况下,认为A发生的概率。 P(B|A)叫做似然度,是A假设条件成立的情况下发生B的概率。 P(A|B)叫做后验概率,在B发生的情况下发生A的概率,也就是要求的概率。P(B)叫做标准化常量,即在一般情况下,认为B…

    2022年10月15日
  • Linux:Tomcat部署war包

    Linux:Tomcat部署war包1、xftp上传Tomcat2、解压Tomcat:tar-zvxf文件unzip文件等解压命令3、将war包放在Tomcat中的webapps目录下(如果webapps中有任何其他war包或解压后的文件都需要删除)4、修改以上穿过去的文件的拥有者(非root用户下时)5、查看需要使用的端口的占用情况(ro…

    2022年10月28日
  • net:err_unknown_url_scheme

    net:err_unknown_url_scheme

  • python中randint函数是什么意思_randint是什么函数

    python中randint函数是什么意思_randint是什么函数randint(a,b)随机生成整数:[a-b]区间的整数(包含两端)1fromrandomimportrandint2print("随机生成10个随机整数。")

  • 京东云服务器使用教程视频_京东通信app下载

    京东云服务器使用教程视频_京东通信app下载形势分析对公司而言,服务器并不是大事。互联网公司都有服务器和机房。但对个人开发者而言,服务器长久以来确是一大难题。但近年,国外亚马逊牵头开始做AWS云服务,并迅速获得极大成功。国内阿里巴巴及时跟进,推出阿里云平台。服务器对个人开发者而言不再是遥不可及,反而变得触手可及。甚至很多企业不再自己搭建服务器,转而使用云服务平台以节省成本。目前国内云服务平台已是百家争鸣,比起早年互联网环境已好很多。除阿里云外

    2022年10月14日

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号