题解：CF1238E Keyboard Purchase

· · 题解

简要题意：

给定一个长度为 n 的字符串 s，s 中的每一个字符都是前 m 个小写字母中的一个。你需要找到一个长度为 m 的字符串 t，满足前 m 个小写字母都刚好在 t 中出现一次，令字符 j 在 t 中的位置为 pos_j。

然后求出下面这个式子的最小值：

\sum_{i=2}^n | pos_{s_i} - pos_{s_{i-1}}|

读完题就意识到如果已知 t 就可以在计算出 s 中不同的相邻字符对出现次数之后快速求出对应的答案。而 m \le 20 于是就想试试模拟退火。

每一次交换两个随机位置，再根据概率确定应不应该接受劣解。对于这道题，降温系数调低一点更容易过。

代码如下：

//code by ElderFour
//problem:CF1238E
#include<bits/stdc++.h>
using namespace std;
const double T0=2000.0,TD=0.98,Tk=1e-15;
const long long N=100010,M=25,INF=1e18;
long long n,m;
long long cnt[M][M],dis[M][M];
long long tmp;
string st;
long long a[N];
long long b[M];
long long calculate()
{
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            dis[min(b[i],b[j])][max(b[i],b[j])]=j-i;
        }
    }
    long long sum=0;
    for(int i=1;i<=m;i++)
    {
        for(int j=i+1;j<=m;j++)
        {
            if(!cnt[i][j])continue;
            sum+=dis[i][j]*cnt[i][j];
        }
    }
    return sum;
}
long long answer=INF,ans;
void SA()
{
    double t=T0;
    for(int i=1;i<=m;i++)b[i]=m-i+1;
    ans=INF;
    while(t>Tk)
    {
        long long ex=rand()%m+1,ey=rand()%m+1;
        if(ex==ey)continue;
        swap(b[ex],b[ey]);
        long long eans=calculate();
        double de=eans-ans;
        if(de<0)ans=eans;
        else
        {
            if(exp(-de/t)*RAND_MAX<rand())swap(b[ex],b[ey]);
        }
        t*=TD;
    }
    answer=min(answer,ans);
    return;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>m>>st;
    srand(2.19);
    double beg=clock();
    for(int i=0;i<n;i++)a[i+1]=st[i]-'a'+1;
    for(int i=2;i<=n;i++)cnt[min(a[i],a[i-1])][max(a[i],a[i-1])]++;
    while((double)(clock()-beg)/CLOCKS_PER_SEC<0.9)SA();
    cout<<answer;
    return 0;
}