牛客周赛66文字版题解
写篇题解吧~
写在前面
A.小苯吃糖果
只需要比较吃最大的一堆和其余两堆之和的值，取较大即可。
时间复杂度:
void solve(){
int a,b,c;
cin>>a>>b>>c;
cout<<max(max({a,b,c}),a+b+c-max({a,b,c}));
}
B.小苯的排列构造
注意到 ，且满足数组单调不增，由于只需要构造一种，那我们可以考虑特殊情况，即对于数组
全部相等，只需要令
，所以只需要对排列从大到小输出即可。
例如:
时间复杂度:
void solve(){
int t;
cin>>t;
while(t--){
int n;
cin>>n;
for(int i=n;i>=1;i--) cout<<i<<" \n"[i==1];
}
}
C.小苯的最小整数
考虑到数字 的数位不超过
，所以直接暴力枚举可以得到的所有数字，然后取最小的即可，笔者这里用字符串的方法，也可以考虑直接用数字计算。
时间复杂度:
void solve(){
int t;
cin>>t;
while(t--){
string s;
cin>>s;
vector<string>vv;
for(int i=0;i<s.size();i++){
string t="";
if(s.size()-i>0)t+=s.substr(i,s.size()-i);
if(i>0)t+=s.substr(0,i);
vv.push_back(t);
}
sort(vv.begin(),vv.end(),[](string a,string b){
if(a.size()==b.size()) return a<b;
return a.size()<b.size();
});
cout<<vv[0]<<"\n";
}
}
D E 小苯的蓄水池(Easy -Hard）
考虑到两个挡板之间取出后，左右两个水池会合并为一个水池，很容易让人想到并查集操作，由于每个挡板取出后不会再被影响，所以实际上每个挡板只会被枚举一次。
那么对于一个区间 之间的取出挡板应该如何操作呢?
首先我们先考虑 这两个区间，在
和
之间存在一个挡板，考虑并查集，我们可以把每个区间的所有点的祖先结点都赋值为该区间最右端点
，所以我们只需要合并
和
也就相当于合并
和
的祖先结点，也是把这个两个区间合并起来了，那么依次递进枚举到该区间的最后一个挡板，也就可以把该区间的所有子区间合并为一个区间，同时做一下区间水量和以及区间位置个数和即可。
时间复杂度:
void solve(){
int n,q;
cin>>n>>q;
vector<int>a(n+1);
vector<int>p(n+1);
vector<i64>s_cnt(n+1,1);
vector<i64>s_water(n+1);
for(int i=1;i<=n;i++) p[i]=i;
for(int i=1;i<=n;i++) cin>>a[i],s_water[i]=a[i];
auto find=[&](auto &&self,int x)->int
{
if (p[x] != x)
p[x] = self(self,p[x]);
return p[x];
};
auto merged=[&](int x,int y)->void{
int fx=find(find,x);
int fy=find(find,y);
if(fx==fy) return ;
if(fx<fy) swap(fx,fy);
s_cnt[fx]+=s_cnt[fy];
s_water[fx]+=s_water[fy];
p[fy]=fx;
};
while(q--){
int o;
cin>>o;
if(o==1){
int l,r;
cin>>l>>r;
for(int i=l;i<r;i++){
merged(i,i+1);
i=find(find,i)-1;
}
}else{
int x;
cin>>x;
int fa=find(find,x);
cout<<fixed<<setprecision(4)<<1.0*s_water[fa]/s_cnt[fa]<<"\n";
}
}
}
F.小苯的字符提前
做法很多，并不局限于此。
第一步，
我们可以发现提 是有规律的，由于字典序的排序规则，
必然是最小，
必然最大。所以只要先考虑每个字符出现的次数，然后找到第
小的位于哪个字符，得到目标字符
，此时需要的即是
所有可得到的字符串中，第
(所有小于
的字符个数) 小的那个。
例如: ，那么第
小的必然是位于
，所以此时只需要找
中第
小，即
中第二小的即可。
第二步：我们对每个 进行排名即可，推导排名的过程。
例如:。
当
时，存在三种情况:
1.
位会是原来的
，但是如果移动后面
，新的字符串的第三位至少会是现在的
。所以当前位置若操作，将会是排名较大的字典序。
2.
位会是原来的
，但是如果移动后面
，新的字符串的第三位会是现在的
。所以当前位置若操作，将会是排名较小的字典序。
3.
处理完后，对于
位置未排名的位置赋值
一致的排名即可。
然后把所有排名排序，找到我们想要的那个排名字符串即可。
时间复杂度:
void solve(){
int _;
cin>>_;
for(int __=1;__<=_;__++){
int n,k;
cin>>n>>k;
string s;
cin>>s;
map<char,int>cnt;
for(int i=0;i<n;i++){
cnt[s[i]]++;
}
int scnt=0;
char tar;
for(auto t:cnt){
if(k<=t.second){
tar=t.first;
break;
}
k-=t.second;
}
int pd=k;
int l=1,r=1e6;
vector<int>vv(n+1,-1);
for(int i=0;i<n;i++){
if(s[i]==tar){
if(i==n-1){
vv[i]=r;
}else{
if(s[i+1]>s[i]){
vv[i]=r--;
}else if(s[i+1]<s[i]){
vv[i]=l++;
}else{
continue;
}
}
}
}
// 对每赋值排名的赋值排名
for(int i=n-1;i>=0;i--){
if(s[i]==tar&&vv[i]==-1){
vv[i]=vv[i+1];
}
}
vector<pair<int,int>>kk;
for(int i=0;i<n;i++){
if(s[i]==tar){
kk.push_back({i,vv[i]});
}
}
sort(kk.begin(),kk.end(),[](pair<int,int>x,pair<int,int>y){
return x.second<y.second;
});
for(auto vvv:kk){
pd--;
if(pd<=0){
cout<<tar;
for(int i=0;i<vvv.first;i++) cout<<s[i];
for(int i=vvv.first+1;i<n;i++) cout<<s[i];
break;
}
}
cout<<"\n";
}
}
G.小苯的数位MEX
我们只需要考虑 该区间所有数字可以出现的
，然后从大到小枚举
，若满足存在的个数大于
则输出这个
，并计算出对应出现的次数。
由于
组询问且
都很大，考虑数位
。
思路+套一下数位 的模板:
只会是
,一一枚举计算:
用
表示枚举到第
位，此时已经填写过数字的状态为
的条件下，所有数字的数位
等于当前枚举的
的个数。
这里的状态
是十进制数字，其意义表示二进制下的共有
位，用于记录对应位数的数字是否出现过，比如已经填过
，那么第
位下便是
，否则是
。
那么转移过程就只需要枚举一下该位
填与不填就行。
当枚举到最后一位时，讨论
共
种情况：
若
，那么该状态的第
位不能填过，所以状态必然是个偶数才能计数。
若
，那么该状态的所有位置都需要填过，即
，在二进制下为
，此时才能计数。
其余情况的
就只能是其较低位全是
，该位为
才能计数。
时间复杂度:
i64 dp[11][1025];
i64 cul(string s,int w,int leader0,int limit,int state,int mex){
if(w==s.size()){
if(mex==0){
if(state&1) return 0;
else return 1;
}else if(mex==10){
// state 必须全是 1
return state==1023;//111111111
}else{
//看一下第一位不是1的位置是不是mex
for(int i=0;i<=10;i++){
if(((~state)>>i)&1){
if(i==mex) return 1;
return 0;
}
}
return 0;
}
}
if(!limit&&!leader0&&dp[w][state]!=-1) return dp[w][state];
int r=limit?s[w]-'0':9;
i64 ans=0;
for(int i=0;i<=r;i++){
ans+=cul(s,w+1,leader0&&(i==0),limit&&(s[w]-'0'==i),leader0&&(i==0)?0:(state|(1<<i)),mex);
}
if(!limit&&!leader0) dp[w][state]=ans;
return ans;
}
i64 get(string r,int mex){
memset(dp,-1,sizeof dp);
return cul(r,0,1,1,0,mex);
}
void solve(){
int t;
cin>>t;
while(t--){
int l,r;
cin>>l>>r;
string sr=to_string(l+r);
string sl=to_string(l-1);
for(int i=10;i>=0;i--){
i64 a=get(sr,i),b=get(sl,i);
if(a-b>0){
cout<<i<<" "<<a-b<<endl;
break;
}
}
}
}
查看16道真题和解析