Gym - 102766

第一次打gym，感觉良好，就是漏洞很多，要补了。

今天第一次打gym，lxl还是很好心的扒题给我们写，这场是字符串思维场。A签到题。B我用了一个判断因子是否合适的写法更新答案，也水过去了。C一个贪心，硬贪vans。D在赛中，理解错了题意，赛后发现可以搞，就卡特兰数。E是一道爆搜题，但要处理好末尾是8,9的情况。F是组合数学的水题。G是F的加强版，但是可以单个字符压缩之后瞎搞就行了。H待补。

题解

A - Singhal and Swap

题意：

给你两个长为$n(1\le n\le100)$的字符串$a,b$只包含小写英文字母，你可以令$a,b$两串的任意字符进行交换任意次数，最后输出字典序最小的$a$。

题解：

对$a$从小到大$sort$，对$b$从大到小$sort$，然后在遍历，把$a$中比$b$大的都换过去即可，最后再对$a$从小到大$sort$。

B. Singhal and Equality

题意：

给你一个长为$n(1\le n\le1e5)$字符串$s$只包含小写英文字母，现有操作可将其中一个字符替换成任意的小写字母，问最少需要多少次操作才能使其中字符的出现次数相同。

题解：

这题有点暴力，我们首先可以把所有字符的出现次数用一个桶记下来，然后非零的出现次数丢进一个$vector$中，从大到小排个序，然后我们可以发现，$vector$的大小最多不超过$26$，那么可以想一个暴力的算法，就是枚举$n$的因子，目的就是为了让$vector$的大小乘于当前因子等于$n$，用一个$res$表示当前还剩多少数可用，$t$表示满足当前这个因子最少的操作次数，那么我们就可以开始枚举，先用另一个$vector$复制这个，然后开始枚举。遇到大于当前因子的数，我们就让$t+=当前数-当前因子,res+=当前数-当前因子$；如果遇到小于因子的数，我们看看剩下的$res$能不能满足，能的话直接减去即可，不能的话，我们就取$vector$最后面的数，然后$t+=最后面的数$，先用$res$补全这个数，然后不够的用最后面的数来补，多出来的加进$res$里，然后将最后面的数$pop$掉，直至没有数可以查询。最后判断一下这个因子是否可行，再更新答案即可。

ps：代码丑了

AC代码：

//I am so vegetable
//#define err
#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
#define FIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define all(x) x.begin(),x.end() 
#define EB emplace_back
#define _for(type,i,a,b) for(type i = (a);i<(b);++i)
#define _sfor(p,st) for(auto &p:st)
#define endl '\n'


int cnt[26];
signed main() {
  FIO;
  int T;cin>>T;
  while(T--){
    string s;cin>>s;
    memset(cnt,0,sizeof(cnt));
    _sfor(it,s)cnt[it-'a']++;
    vector<int>a;
    _for(int,i,0,26)if(cnt[i])a.EB(cnt[i]);
    sort(all(a),greater<int>());
    int ans=INT_MAX;
    int n=s.size();
    _for(int,i,1,n+1){
      int t=0,res=0;
      vector<int>p(a);
      if(n%i==0){
        _for(int,j,0,p.size()){
          if(p[j]>=i)t+=p[j]-i,res+=p[j]-i;
          else if(p[j]<i){
            if(res>=i-p[j])res-=i-p[j];
            else{
              while(p[j]<i){
                int tt=p.back();
                p[j]+=res,res=0;
                if(p[j]+tt<=i)p[j]+=tt,p.pop_back(),t+=tt;
                else t+=tt,tt-=i-p[j],p[j]=i,res+=tt,p.pop_back();
              }
            }
          
        }
        if((res&&p.size()+res/i<=26)||!res)ans=min(ans,t);
      }
    }
    cout<<ans<<endl;
  }
  return 0;
}

D. Regular Bracket Sequence Again?

---

• 本文作者： baddog
• 本文链接： https://katoli.github.io/2020/11/07/Gym-102766/
• 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！