题解：P4283 [AHOI2008] Y型项链

· · 题解

这是本人的第一篇题解，也是我第一道 AC 的蓝题！

说实在的，我认为这题不应该被评为蓝。

  1. 最长公共前缀：考虑有两个字符串（以下简称串），它们的最长公共前缀就是它们前缀的最长部分 （有些偏废话了）。

  2. 思路：三个串两两匹对，找到任意两个串的最长公共前缀，比较选出中最长的公共前缀（如样例中：一串与三串的最长公共前缀为 CAT ，这是三种两两匹配方案的串中最长的前缀，这就是我们的目标串），找到后只需计算将三个串都更新成目标串所用的步数即可（如样例中将三个串更新成 CAT 就是最少的步数）。

  3. 特别的，如果查找后三种可能的公共前缀均为空（即三者两两匹配后没有公共前缀部分），那么把三串清空就是最少的步数。

  4. 以下是 AC 代码（目前是全题解区中最简洁代码)：

#include<bits/stdc++.h>
using namespace std;
int nx,ny,nz,mxy,mxz,myz,maxn;
int n;
char x[100],y[100],z[100];//三个串
int main()
{
    cin>>nx>>x>>ny>>y>>nz>>z;
    while(x[mxy]==y[mxy]&&mxy<nx&&mxy<ny) mxy++;//mxy是指x串与y串的最长公共前缀的长度
    while(x[mxz]==z[mxz]&&mxz<nx&&mxz<nz) mxz++;//同理于上
    while(y[myz]==z[myz]&&myz<ny&&myz<nz) myz++;
    maxn=max(max(mxy,mxz),myz);//maxn是指最长的最长公共前缀的长度，即目标串的长度
    if(maxn==mxy) n=(nx-mxy)+(ny-mxy)+(nz-mxy)+(maxn-mxz)*2;
    else if(maxn==mxz) n=(nx-mxz)+(ny-mxz)+(nz-mxz)+(maxn-mxy)*2;
    else if(maxn==myz) n=(nx-myz)+(ny-myz)+(nz-myz)+(maxn-mxz)*2;//以上是计算更新成目标串所用的步数
    cout<<n;
    return 0;//good habit
}

通俗易懂，简约大方。希望大家能给蒟蒻一些鼓励，有不足之处请放宽直言。