2017 Multi-University Training Contest - Team 1 1002&&HDU 6034 Balala Power!【字符串,贪心+排序】

Balala Power!

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

Problem Description

Sample Input

1
a
2
aa
bb
3
a
ba
abc

Sample Output

Case #1: 25
Case #2: 1323
Case #3: 18221

Source

2017 Multi-University Training Contest - Team 1

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=6034

题意:给你n个由小写字母组成的字符串,让你给26个字母分配0-25,每个字符串形成一个26进制的数字,问怎么分

配权值这n个数的和最大。(不能有前导0,但是单个0可以)

题解:每个字符对答案的贡献都可以看作一个 26 进制的数字,问题相当于要给这些贡献加一个 0 到 25 的权重

使得答案最大。最大的数匹配 25,次大的数匹配 24,依次类推。排序后这样依次贪心即可,唯一注意的是不能出现

前导 0。关键就是排序,其实结构体排序可以按照数组字典序排序的!

下面给出AC代码:

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const ll mod=1e9+7;
 5 const ll N=1e5+10;
 6 ll fac[N]={1};
 7 ll temp[27];
 8 ll Hash[27];
 9 bool leap[27];
10 char str[N];
11 struct Node
12 {
13     ll cnt[N];
14     ll id;
15     bool operator<(const Node &p)const
16     {
17         for(ll i=N-1;i>=0;i--)
18         {
19             if(cnt[i]>p.cnt[i])
20                 return true;
21             else if(cnt[i]<p.cnt[i])
22                 return false;
23             else;
24         }
25     }
26 }p[27];
27 int main()
28 {
29     ll n,tcase=1;
30     for(ll i=1;i<N;i++)
31         fac[i]=fac[i-1]*26%mod;
32     while(scanf("%lld",&n)!=EOF)
33     {
34         memset(p,0,sizeof(p));
35         memset(Hash,-1,sizeof(Hash));
36         memset(leap,false,sizeof(leap));
37         ll r=0;
38         for(ll i=1;i<=n;i++)
39         {
40             scanf("%s",str);
41             ll len=strlen(str);
42             r=max(r,len-1);
43             if(len!=1)
44                 leap[str[0]-'a']=1;
45             for(ll i=0;i<len;i++)
46                 p[str[i]-'a'].cnt[len-(i+1)]++;
47         }
48         for(ll i=0;i<26;i++)
49         {
50             for(ll j=0;j<N;j++)
51             {
52                 if(p[i].cnt[j]>=26)
53                 {
54                     p[i].cnt[j+1]+=p[i].cnt[j]/26;
55                     p[i].cnt[j]%=26;
56                 }
57             }
58             p[i].id=i;
59         }
60         sort(p,p+26);
61         for(ll i=0;i<26;i++)
62             Hash[p[i].id]=26-(i+1);
63         for(ll i=0;i<26;i++)
64         {
65             if(leap[p[i].id]&&Hash[p[i].id]==0)
66             {
67                 for(ll j=25;j>=0;j--)
68                 {
69                     if(!leap[p[j].id])
70                     {
71                         for(ll k=25;k>=j+1;k--)
72                         {
73                             Hash[p[k].id]=Hash[p[k-1].id];
74                         }
75                         Hash[p[j].id]=0;
76                         break;
77                     }
78                 }
79                 break;
80             }
81         }
82         ll ans=0;
83         for(ll i=0;i<26;i++)
84         {
85             for(ll j=0;j<N;j++)
86             {
87                 ans=(ans+fac[j]*p[i].cnt[j]*Hash[p[i].id]%mod);
88             }
89         }
90         printf("Case #%lld: %lld\n",tcase++,ans%mod);
91     }
92     return 0;
93 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

1200 同余方程

1200 同余方程 2012年NOIP全国联赛提高组 时间限制: 1 s 空间限制: 128000 KB 题目等级 : 钻石 Diamond 题目...

2834
来自专栏IT可乐

由HashMap哈希算法引出的求余%和与运算&转换问题

1583
来自专栏二进制文集

LeetCode 004 Median of Two Sorted Arrays 详细分析

题目链接:https://leetcode.com/problems/median-of-two-sorted-arrays/

1111
来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

1453
来自专栏IT可乐

深入理解计算机系统(2.6)------整数的运算

  前面两篇博客我们详细讲解了计算机中整数的表示,包括有符号和无符号(补码编码)的详细介绍。那么这篇博客我们将对它们的运算有个详细的了解。   在讲解之前首先看...

2667
来自专栏用户2442861的专栏

对vector等STL标准容器进行排序操作

STL几乎封装了所有的数据结构中的算法,从链表到队列,从向量到堆栈,对hash到二叉树,从搜索到排序,从增加到删除......可以说,如果你理解了STL,你会...

2612
来自专栏CDA数据分析师

学会这8个(组)excel函数,轻松解决工作中80%的难题

文 | 兰色幻想-赵志东 函数是excel中最重要的分析工具,面对400多个excel函数新手应该从哪里入手呢?下面是实际工作中最常用的8个(组)函数,学会后工...

1977
来自专栏Albert陈凯

技术面试要了解的算法和数据结构知识

目录 在线练习 在线编程面试 数据结构 算法 贪心算法 位运算 复杂度分析 视频教程 面试宝典 计算机科学资讯 文件结构 在线练习 Le...

3225
来自专栏小樱的经验随笔

2017 Multi-University Training Contest - Team 1 1006&&HDU 6038 Function【DFS+数论】

Function Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 131072/131072 K...

2825
来自专栏Bingo的深度学习杂货店

Q70 Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top. Each time y...

3445

扫码关注云+社区

领取腾讯云代金券