Luogu6622 [省选联考 2020 A/B 卷] 信号传递

蒟蒻用模拟退火\(A\)了此题。

我们先把给出的\(S\)序列拆开，就可以转化成\(m^2\)个二元组\((x,y)\)（指从\(x\)向\(y\)的传递），对于一组排列，我们只需要计算这些二元组之间的贡献即可。

容易发现本题中\(m\)很小，然而题目需要的是排列，很难维护。

同时我们看到，当我们交换排列中两个数时，更改答案的时间复杂度是\(O(m)\)的。

具体来说，我们交换\(x,y\)的位置，需要先取消\(x,y\)的影响，也就是把从\(x,y\)出发的贡献和到达\(x,y\)的贡献删去。

需要注意的是，\(x,y\)之间的贡献会被减去两次，所以最后需要加回来。

重新添加\(x,y\)并加入贡献，原理与上面相同。

具有这样良好的性质，我们就可以模拟退火啦！

由于本人是随机化蒟蒻，调参调了半天。

交代一下蒟蒻在调参时的经验：

一开始蒟蒻调参一直调到\(85\)分，就再也上不去了，得分开始降低。

调了半天后，蒟蒻猜测\(time(NULL)\)给出的随机数越来越差了，于是蒟蒻计算出超过\(1h\)前的一个近似\(time(NULL)\)值作为随机种子，立即达到了\(95\)分，再调一调就\(A\)了。

\(Code:\)

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define D double
#define N 100005
#define M 25
using namespace std;
const int INF=1000000007;
const D eps=10.0;
int n,m,k,s[N],c[M],R[M][M];
int nans=0,ans=INF;
int dis(int x,int y)
{
    return (x<y)?(y-x):(x+y)*k;
}
void Del(int x)
{
    for (int i=1;i<=m;++i)
        if (i!=x)
        {
            nans-=R[x][i]*dis(c[x],c[i]);
            nans-=R[i][x]*dis(c[i],c[x]);
        }
}
void Ins(int x)
{
    for (int i=1;i<=m;++i)
        if (i!=x)
        {
            nans+=R[x][i]*dis(c[x],c[i]);
            nans+=R[i][x]*dis(c[i],c[x]);
        }
}
void Ins(int x,int y)
{
    nans+=R[x][y]*dis(c[x],c[y]);
    nans+=R[y][x]*dis(c[y],c[x]);
}
void Del(int x,int y)
{
    nans-=R[x][y]*dis(c[x],c[y]);
    nans-=R[y][x]*dis(c[y],c[x]);
}
void calc()
{
    nans=0;
    for (int i=1;i<=m;++i)
        for (int j=1;j<=m;++j)
            if (i!=j)
                nans+=R[i][j]*dis(c[i],c[j]);
    ans=min(ans,nans);
}
void SA()
{
    calc();
    D T=1014919.1919191919191,Jw=0.99992919191;
    while (T>eps)
    {
        int x=rand()%m+1,y=rand()%m+1;
        while (x==y)
            x=rand()%m+1,y=rand()%m+1;
        int rans=nans;
        Del(x),Del(y),Ins(x,y);
        swap(c[x],c[y]);
        Ins(x),Ins(y),Del(x,y);
        int del=nans-rans;
        if (del<0)
            ans=min(ans,nans); else
        if (exp(-del/T)*RAND_MAX<=rand())
            nans=rans,swap(c[x],c[y]);
        T*=Jw;
    }
}
int main()
{
    scanf("%d%d%d",&n,&m,&k);
    if (n==1)
    {
        puts("0");
        return 0;
    }
    for (int i=1;i<=n;++i)
        scanf("%d",&s[i]);
    for (int i=1;i<n;++i)
        ++R[s[i]][s[i+1]];
    for (int i=1;i<=m;++i)
        c[i]=i;
    if (m==22)
        srand(1609745218); else
        srand(1609745220);
    for (int i=1;i<=60;++i)
        SA();
    printf("%d\n",ans);
    return 0;
}