2017 Multi-University Training Contest 1

  1. 1001 Add More Zero
  2. 1002 Balala Power!
  3. 1003 Colorful Tree

此题解没写完
题目 HDU 6033-6044
题解

1001 Add More Zero

已知m,求k,满足 \(2^{m-1} -1 < 10^k \leq 2^m -1\)

\(ans=\lfloor log_{10}^{2^m-1}\rfloor=\lfloor log_{10}^{2^m}\rfloor=\lfloor m log_{10}^{2}\rfloor\)

1
2
3
4
5
6
7
8
#include <cstdio>
double LG2=0.301029995663981195213738894724493026768189881462108541310;
int T,m;
int main()
{
while(scanf("%d",&m)==1)
printf("Case #%d: %d\n",++T,int(m*LG2));
}

1002 Balala Power!

将a-z映射到0-25,将字符串变成26进制数字,使得所有数字的和最大。注意前导不为0,结果mod 1e9+7. 字符串个数<=1e5;字符串长度<=1e5;字符串总长度<=1e6

求每个字母的贡献,0匹配最小的且不作为开头的字母,其他由小到大匹配1到25

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include <cstdio>
#include <cstring>
#include <algorithm>
const int mod=1e9+7,N=100010;
struct node {
int s[N],len;
bool no_start,zero;
}a[26];
int T,n,maxnum,ans,base[N];
char s[N];
inline bool cmp(const node &A,const node &B)
{
if(A.len!=B.len) return A.len>B.len;
for(int i=A.len-1;i>=0;i--)
if(A.s[i]!=B.s[i])
return A.s[i]>B.s[i];
return 0;
}
inline int TIMES(node b,int c)
{
if(!c||!b.len) return 0;
long long num=0;
for(int i=0;i<b.len;i++)
num=(num+(long long)b.s[i]*c%mod*base[i]%mod)%mod;
return (int)num;
}
int main()
{
base[0]=1;
for(int i=1;i<N;i++)
base[i]=(long long)base[i-1]*26%mod;
while(scanf("%d",&n)!=EOF)
{
for(int i=0;i<26;i++)
{
memset(a[i].s,0,sizeof(a[i].s));
a[i].len=a[i].no_start=a[i].zero=0;
}
ans=0;maxnum=26;
for(int i=1;i<=n;i++)
{
scanf("%s",s);
int len=strlen(s);
if(len>1) a[s[0]-'a'].no_start=1;
for(int j=0;j<len;j++)
{
a[s[j]-'a'].s[len-j-1]++;
a[s[j]-'a'].len=std::max(a[s[j]-'a'].len,len-j);
}

}
for(int i=0;i<26;i++)
{
for(int j=0;j<a[i].len;j++)
if(a[i].s[j]>=26)
a[i].s[j+1]+=a[i].s[j]/26,a[i].s[j]%=26;
while(a[i].s[a[i].len])
{
a[i].s[a[i].len+1]+=a[i].s[a[i].len]/26;
a[i].s[a[i].len]%=26;
a[i].len++;
}
}
std::sort(a,a+26,cmp);
if(a[25].len)
for(int i=25;i>=0;i--)
{
if(a[i].no_start) continue;
a[i].zero=1;break;
}
for(int i=0;i<26;i++)
if(!a[i].zero)
ans=(ans+TIMES(a[i],--maxnum))%mod;
printf("Case #%d: %d\n",++T,ans);
}
}

1003 Colorful Tree

n个节点的树,每个节点颜色为ci。两点之间的值为经过的颜色数。计算所有 \(\frac {n \times (n-1)}{2}\) 条路径值之和。