谔谔的题目传送门

题意:

每次操作使字符串中的一种字符数量增加一倍,问最少几次操作后字符串长度能大于等于LL

思路:

根据这个题意,我们可以看出,其实这个题就是一个贪心的思想,只要一开始选数量最多的那种字符,然后一直将其倍增就好了,为什么呢?因为既然是要求最少的操作次数,那么每次操作能增加的字符数量一定要尽量多,所以我们一开始就选最多的那种字符,就能使每次操作增加的字符数量最大化,这样最后的次数一定是最少的。同时这样倍增一次后,该字符数量还是最多的,那么我们下一次操作就还是选这种字符。

举个例子,在 AKIOI\texttt{AKIOI} 这个字符串中,字符 I\texttt{I} 的个数显然是最多的,那么我们一直将其数量倍增,最后能达到的总长度一定比选其他字符要长。

同时我们也可以看出,这道题不可能暴力模拟,因为根据L264L\le2^{64}这个数据就能看出,谁想暴力,谁就爆零。

那么我们该怎么办呢?推规律呗!

s=Sxs=|S|-x(也就是除开我们要倍增的那种字符以外的字符个数),LiL_i为第ii次操作后的字符串长度。

L1=s+2x=s+21xL_1=s+2\cdot x=s+2^1\cdot x

L2=s+22x=s+22xL_2=s+2\cdot 2\cdot x=s+2^2\cdot x

L3=s+222x=s+23xL_3=s+2\cdot 2\cdot 2\cdot x=s+2^3\cdot x

\cdots

Ln=s+2nxL_n=s+2^n\cdot x

由此,这个式子就推出来了,有人可能会说,你这个计算的是nn次操作后的字符串长度啊,不符合题意啊!这好办,既然要求字符串长度大于等于LL,也就是LnL_n要大于等于LL,那我们列个不等式就行了。

s+2nxLs+2^n\cdot x\ge L

2nLsx2^n\ge\dfrac{L-s}{x}

nlog(Lsx)n\ge \log\left(\dfrac{L-s}{x}\right)

完事。

关于计算字符个数,其实也很简单,题目明确说了,一共只有6262种字符,那么我们开个数组,桶排就好了,比如说大写字母个数就存在b1b_{1}b26b_{26},小写字母个数就存在b27b_{27}b52b_{52},而数字个数就存在b53b_{53}b62b_{62}

对了,还有一点重要提醒:开 long long 还是会炸,要开 long double 或 unsigned long long!!!,本题还特别提醒,要注意数据范围,结果我因为没开 long double 调了半小时……。long long 的范围是到26312^{63}-1,但本题的LL是到26412^{64}-1,所以用了 long long 还是不行。

代码:

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
#include<bits/stdc++.h>
using namespace std;
string s;
long long maxn,ans,b[63];
long double l;//再次提醒,一定要开 long double 或 unsigned long long。
long long my_log(long double x)//我个人不太信得过 cmath 里的函数,所以能自己写的我还是自己写好了。
{
long long s=0;
while(x>1)//当 x 为 1 时,表示长度已经等于 L 了,所以不能再累加了。
{
s++;
x/=2;
}
return s;
}
int main()
{
cin>>s>>l;
for(int i=0;i<s.length();i++)
{
if(s[i]>='A'&&s[i]<='Z')//分段存,判断当前字符属于哪一类,然后对应的下标+1
b[s[i]-'A'+1]++;
if(s[i]>='a'&&s[i]<='z')
b[s[i]-'a'+27]++;
if(s[i]>='0'&&s[i]<='9')
b[s[i]-'0'+53]++;
}
for(int i=1;i<=62;i++)//找出最数量最多的字符
maxn=max(maxn,b[i]);
cout<<my_log((l-s.length()+maxn)*1.0/maxn);//这里的 1.0 主要起转化类型的作用
return 0;//谔谔完毕
}

就这样,如果还有不懂的,可以在评论里问,如果有什么不对的地方,还请大佬指出,谢谢!