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)
blank

相关推荐

  • 汽车电子设计之SBC芯片简单认识[通俗易懂]

    汽车电子设计之SBC芯片简单认识[通俗易懂]参考英飞凌SBC官网资料:https://www.infineon.com/cms/cn/product/automotive-system-ic/system-basis-chips-sbc/SBC芯片在汽车电子领域可谓占一席之地了。那么什么是SBC?怎么用?用在哪里?主要特性?1.什么是SBC?SBC的系统框图系统基础芯片(SBC,SystemBasisChip),从广义上来说,是一种包含电源、通信、监控诊断、安全监控等特性以及GPIO的独立芯片。随着汽车电子模块的日益小型化,对低功耗和

  • 罗盘时钟代码[通俗易懂]

    罗盘时钟代码[通俗易懂]HTML<%@pagecontentType=”text/html;charset=UTF-8″language=”java”%><!DOCTYPEhtml><htmllang=”en”><head><metacharset=”UTF-8″><metaname=”viewport”content=”width=device-width,initial-scale=1.0″>&lt

  • 2020年开始,中国程序员前景一片灰暗,是这样吗?[通俗易懂]

    2020年开始,中国程序员前景一片灰暗,是这样吗?[通俗易懂]背景:汇总了下老王在其他平台的原创回复,欢迎关注老王原创公众号【软件老王】,关注不迷路。1、感觉中国程序员前景一片灰暗,是这样吗?老王观点:(1)个人认为谈不上灰暗,过去十年是互联网快速爆发的十年,每个行业发展了一定程度,都会慢慢趋于平稳,软件行业也不例外。(2)其实最近也有这种感觉,感觉软件行业比以前难做了,随着政府推动的互联网+,软件行业已经进入各行各业,认为后面可能会像美国一样,成为一个基础行业,待遇和机会也会趋同于其他行业,但是不知道能不能像美国那样,到50多岁了还能写的上代码。(3

    2022年10月11日
  • 图论(二):图的四种最短路径算法

    图论(二):图的四种最短路径算法本文总结了图的几种最短路径算法的实现:深度或广度优先搜索算法,弗洛伊德算法,迪杰斯特拉算法,Bellman-Ford算法1),深度或广度优先搜索算法(解决单源最短路径)从起始结点开始访问所有的深度遍历路径或广度优先路径,则到达终点结点的路径有多条,取其中路径权值最短的一条则为最短路径。下面是核心代码:voiddfs(intcur,intdst){/

  • js动态定义全局变量与使用

    js动态定义全局变量与使用ECharts          varobj={}       varnum=1;       functionna(){           varnames=’name’+(num++);           window[names]=’我爱你’+num;       }       functionx

  • 小程序跳转公众号_小程序跳转APP

    小程序跳转公众号_小程序跳转APP即用即走——这个是从微信小程序上线就开始打的概念。即用即走使得小程序可以代替许多APP,或是做APP的整体嫁接,或是作为阉割版功能的承载体。对用户使用上来说,确实方便,要用的时候打开,不用的时候关掉,即用即走。但是却并不会关注相关联的公众号。那么怎么在小程序中加入公众号的关注功能呢?简单来说就这么几步:1,登入微信公众号的管理后台微信公众平台。2,选择要跳转的公众号登录进去,点击小程序管理。3,直接点击关联小程序即可,如果关联过其他小程序点击添加即可,该操作只能由公众号管理员完成,.

    2022年10月23日

发表回复

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

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