[ROIR 2021 Day 1] 基因突变 题解

· · 题解

前言

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

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

解法

Part 1 在解题之前

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

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

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;
}

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