题解 P6101 【出言不逊】
引领天下
2020-02-15 18:14:24
这个题首先是贪心：肯定要选取原字符串中最多的字符进行复制，然后再次选择该字符复制，一直复制下去。
可以直接模拟，但需要考虑大小，所以要用 __int128 。
由于模拟的复杂度是 log 的，可做。
当然也可以不用 __int128 ，但相比之下会麻烦一点。
代码：
```cpp
#include <bits/stdc++.h>
#define min(x,y) ((y)^(((x)^(y))&(-((x)<(y)))))
#define max(x,y) ((x)^(((x)^(y))&(-((x)<(y)))))
using namespace std;
string s;
__int128 ans,mx,l,nl;
map<char,int> cnt;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline void read(__int128 &x){
int f=1;x=0;char ch=nc();
while (ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=nc();}
while (ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=nc();}
x*=f;
}
inline void write(__int128 n){
if (n==0)return ;
write(n/10);
putchar(n%10+'0');
}
int main(){
#ifndef ONLINE_JUDGE
// #define FILE_OUTPUT
#ifdef FILE_OUTPUT
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
long long c1=clock();
#endif
cin>>s;
read(l);
for (int i=0;i<s.size();i++)cnt[s[i]]++,mx=max(mx,cnt[s[i]]);/找出出现次数最多的字符
nl=s.size();
while(nl<l)nl+=mx,mx+=mx,ans++;//手动模拟复制
if(ans)write(ans);//输出答案，由于使用了 __int128 ，需要自己写一个输出。
else putchar('0');
#ifndef ONLINE_JUDGE
#ifndef FILE_OUTPUT
puts("\n--------------------------------");
printf("Process exited after %g seconds with return value 0\n",(clock()-c1)/1000.0);
system("pause");
#endif
#endif
return 0;
}
```