Codeforces 391 题解

非常常规的一套Codeforces题解

A

题意

给出一个字符串,求出其中最多能够组成单词“Bulbasaur”的个数(可以将字符串中的字母拆散)

题解

用一个数组记录单词中各个字母的出现次数,出现次数最小的值就是能够组成的单词数

代码

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
void judge(char s)
{
if(s=='B')con[0]++;
if(s=='u')con[1]++;
if(s=='l')con[2]++;
if(s=='b')con[3]++;
if(s=='a')con[4]++;
if(s=='s')con[5]++;
if(s=='r')con[6]++;
}

void solve()
{
string s;
while(cin>>s)
{
fill(con,con+7,0);
for(int i=0;i<s.size();i++)
judge(s[i]);
int res=INF;
for(int i=0;i<7;i++)
{
if(i==1||i==4)
res=min(res,con[i]/2);
else
res=min(res,con[i]);
}
cout<<res<<endl;
}
}

B

题意

给出n个数,从这n个数中取出一个组合,使得这个组合中的最大公因子不为1,同时要组合中的数的个数要最大,输出这个组合中的数的个数

题解

  • 首先求出范围内的素数集,然后把每一个素数当成组合中的最大公因子,看这个组合能够有大(看给出的这些数中有多少能够整除当前素数),最后取所有组合的模的最大值
  • 对每一个数进行判断他是否是当前这个素数的倍数这样会造成时间超限,因此采用空间换时间的策略,为数据范围内的每一个数记录其出现次数,然后再将所有能够整除当前素数的值的出现次数进行相加(类似与埃式素数筛选法)

代码

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
int con[MAX];
bool is_prime[MAX];
int prime[MAX];
int num;

//素数筛选
void init_pri()
{
num=0;
memset(is_prime,1,sizeof(is_prime));
is_prime[0]=is_prime[1]=0;
for(int i=2;i<MAX;i++)
{
if(is_prime[i])
{
prime[num++]=i;
for(int j=i;j<MAX;j+=i)
is_prime[j]=0;
}
}
}

void solve()
{
int n;
init_pri();
while(cin>>n)
{
memset(con,0,sizeof(con));
int x;
for(int i=0;i<n;i++)
{
cin>>x;
con[x]++;
}
int res=1;
for(int i=0;i<num;i++)
{
int tem=0;
for(int j=prime[i];j<MAX;j+=prime[i])
tem+=con[j]; //求出当前组合的模
res=max(res,tem);
}
cout<<res<<endl;
}
}