【洛谷 P6101】出言不逊

题意：

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

思路：

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

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

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

那么我们该怎么办呢？推规律呗！

设 $s=|S|-x$ （也就是除开我们要倍增的那种字符以外的字符个数）， $L_i$ 为第 $i$ 次操作后的字符串长度。

$L_1=s+2\cdot x=s+2^1\cdot x$

$L_2=s+2\cdot 2\cdot x=s+2^2\cdot x$

$L_3=s+2\cdot 2\cdot 2\cdot x=s+2^3\cdot x$

$\cdots$

$L_n=s+2^n\cdot x$

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

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

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

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

完事。

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

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

代码：

#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;//谔谔完毕
}

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

【洛谷 P6101】 出言不逊

【洛谷 P6101】出言不逊