自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:51:38，当前版本为作者最后更新于2023-10-20 21:25:12，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

前言

CSP 考前做大型分类讨论题。

祝大家 CSP 都能取得自己满意的成绩。

解法

Part 1 在解题之前

先定义几个“函数”（注意这里和数学意义上的函数的定义有差别）方便解题：

• $l(x)$：返回整数 $x$ 在 $10$ 进制下的位数；

• $f(x)$：将整数 $x$ 划分为 $2$ 个整数 $a+b=x$，返回使 $l(a)+l(b)$ 最大的其中一个 $a$；

  设 $h(x)$ 为 $x$ 在 $10$ 进制下的最高位，$s(x)$ 为 $x$ 在 $10$ 进制下的次高位（没有则为 $0$），$d(x)$ 为将最高位删去后的 $x$，$f(x)$ 可以通过如下方式构造：

  $f(x)=\begin{cases}d(x)&h(x)=1\land s(x)>0\\\left\lfloor\dfrac{x}{2}\right\rfloor&\mathrm{otherwise}\end{cases}$

• $e(x)$：对于一个字符型自变量 $x$，返回字符串 $\texttt{ACGT}$ 中任意一个与 $x$ 不同的字符；

三个函数的代码实现如下：

int l(int x){
  return x==1?0:(int)log10(x)+1;
}
int f(int x){
  string s=to_string(x);
  if(s[0]==49&&s[1]>48)return stoi(s.substr(1,s.length()-1));
  return x>>1;
}
char e(char c){
  return c=='A'?'G':'A';
}

其次说明接下来对原始字符串的处理方式：为方便处理，使用一个 std::vector<std::pair<int,char> >，其中 pair 的 first 为字符出现次数，second 为这个字符，按顺序存储原始字符串的所有信息。

这里给出处理部分的参考代码：

typedef pair<int,char> pic; // 以下几份代码相同
// 中间部分省略
vector<pic> a; int c=0;
for(char i:s)
  if(isdigit(i))c=(c<<1)+(c<<3)+(i^48);
  else a.emplace_back(max(c,1),i),c=0;

Part 2 最小化

可以仅使用删除操作来构造最优答案。

考虑对于一段形如 $\texttt{AA}\cdots\texttt{AAGAA}\cdots\texttt{AA}$ 的构造答案，不妨设出现多的那种字符为 $\texttt{A}$，中间那个唯一的为 $\texttt{G}$，显然可以将中间那个不一样的字符删掉，让两边两段合并。这样一次可以使长度减少地最多，设左边有 $x$ 个 $\texttt{A}$，右边有 $y$ 个，长度减少为 $l(x)+l(y)-l(x+y)+2$。

除此之外只能删掉其他任意一个字符，长度减少 $1$ 或不变。

所有方案中去长度减少最多的即可。

该部分代码（函数返回值为要删除的位置）：

int solve_min(vector<pic> a){
  int c=0,d=-1,r;
  for(int i=0;i<a.size();c+=a[i++].first)
    if(a[i].first==1&&i&&i<a.size()-1&&a[i-1].second==a[i+1].second){
      int d0=l(a[i-1].first)+l(a[i+1].first)-l(a[i-1].first+a[i+1].first)+2;
      if(d0>d)d=d0,r=c+1;
    } // 中间有一个字符，两端夹的字符相同
    else if(a[i].first<=2){
      if(d<1)d=1,r=c+1;
    }
    else{
      int d0=l(a[i].first)-l(a[i].first-1);
      if(d0>d)d=d0,r=c+1;
    } // 两种普通情况
  return r;
}

Part 3 最大化

可以仅使用插入操作来构造最优答案。

考虑一段形如 $\texttt{AA}\cdots\texttt{AA}$ 的构造答案，不妨设这一段有 $c$ 个 $\texttt{A}$，最优的方案显然是在中间插入一个字符（可以是 $\texttt{G}$）使得两边的 $\texttt{A}$ 的数量 $x$ 和 $c-x$ 满足 $l(x)+l(c-x)$ 最大。这时我们的 $f(x)$ 函数就派上用场了，$x$ 取 $f(c)$ 为其中一种最佳选择。长度增加量 $l(x)+l(c-x)-l(c)+2$。

当然如果没有长段（定义为长度大于或等于 $3$ 的）可以插，只能在最后插入一个与末尾不一样的字符。长度增加量为 $1$。

所有方案中去长度增加最多的即可。

该部分代码（函数返回值的 first 为要添加的位置，second 为要添加的字符）：

pic solve_max(vector<pic> a){
  int c=0,d=0; pic r;
  for(int i=0;i<a.size();c+=a[i++].first)
    if(a[i].first>=3){
      int x=f(a[i].first),d0=l(x)+l(a[i].first-x)-l(a[i].first)+2;
      if(d0>d)d=d0,r=make_pair(c+x,e(a[i].second));
    } // 找长段，在中间插一个不一样的
  if(!d)r=make_pair(c,e(prev(a.end())->second));
  // 普通情况，在末尾插一个
  return r;
}

于是此题所有情况讨论完毕。