题解：P15012 再生

· · 题解

首先不认为本题评橙。

我们令找到的两个串为 t1,t2。

我们观察到相同长度最大的 t1 和 t2 最多只有一位不同，这个是我手玩样例好久发现的。感性证明一下：

假设 t1 和 t2 是构造出的相同长度最长的两个串，那么同时在这里面减去一个位置得到的 t1' 和 t2' 相同的长度会更小，并且 t1,t2 要求最少有一位字母相同的地方在 S 中位置不同，所以就除了不相同的地方其它剩余地方全加进 t1 和 t2 里面就行。

然后我们枚举这个颜色相同但在 S 中位置不同的位置对 (i,j)，这样我们可以把 [1,i] 和 [j,n] 这两个区间里面所有的位置都加进 t1 和 t2 里面，答案是 n - (i - j)，(i - j) 是中间抛弃的不用的长度。

直接统计时间复杂度是 O(n^2) ，需要你对每种字母的每个位置都计算一遍，我们可以预处理出字母为 i 时，j 位置处的下一个字母 i 的位置 k。这个预处理的方式跟子序列自动机一样。

但是还有更简单的方式，我们考虑贪心的选取这个 (i,j)，要让 (j - i) 最小，肯定是选取相邻的两个比选取不相邻的两个不劣，所以我们可以开一个 vector，记录字母 i 出现的位置们 vec_{i,j}，然后对于每一种字母遍历一遍 vec_{i,j}，不断更新答案即可。

时间复杂度是 O(n) 的，每个位置只会被计算一遍，就相当于把原字符串 S 按照字母分了一下类。

这玩意能是橙色的我吃。赛时用了 35 分钟才想清楚。

建议本题评黄及以上。

:::info[代码]

#include <bits/stdc++.h>
#define ll long long
#define rep(i,a,n) for(int i = (a);i<=(n);++i)
#define endl '\n'

using namespace std;
template<typename T>inline void read(T &x){
    char c = getchar();
    short int t = 1;x = 0;
    for(;!isdigit(c);c = getchar())if(c == '-')t=-1;
    for(;isdigit(c);c = getchar())x = (x<<1) + (x<<3) + (c^48);
    x*=t;
}
const int N = 1e5+10;
int n = 0;
char c[N];
vector<int> vec[30];

signed main(){
    read(n);
    scanf(" %s",c+1);

    for(int i = 1;i<=n;++i){
        vec[c[i] - 'a'].push_back(i);
    }
    int ans = 0;
    for(int i = 0;i<26;++i){
        int las = -1;
        for(int j : vec[i]){
            if(las == -1){
                las = j;
                continue;
            }else{
//              cout <<las<<" "<<j<<endl;
                ans = max(n - (j - las),ans);
                las = j;
            }
        }
    }
    if(ans == 0){
        cout <<-1<<endl;
    }else{
        cout <<ans<<endl;
    }
    return 0;
}
/*

*/

/*

*/

:::

做完这个题之后我三个小时冲 T2，失败，完全正解，心态 -20。