SA调参头秃了,求救
  • 板块P3936 Coloring
  • 楼主yql123456SN弱校小菜鸡
  • 当前回复6
  • 已保存回复6
  • 发布时间2020/7/15 19:46
  • 上次更新2023/11/6 23:04:19
查看原帖
SA调参头秃了,求救
220838
yql123456SN弱校小菜鸡楼主2020/7/15 19:46

#pragma GCC optimize(3)

#pragma GCC target("avx")

#pragma GCC optimize("Ofast")

#pragma GCC optimize(3)

#pragma GCC optimize("Ofast")

#pragma GCC optimize(2)

#pragma GCC optimize(3)

#pragma GCC optimize("Ofast")

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<cmath>

using namespace std;

#pragma GCC optimize(3)

//#define double long double

inline char gc()

{

    return getchar();

}

inline void pc(char c)

{

    putchar(c);

    return;

}

inline int read()

{

    register int f=1,x=0;

    char c=getchar();

    while(c>'9'||c<'0')

    {

        if(c=='-') f=-f;

        c=getchar();

    }

    while(c>='0'&&c<='9')

        x=x*10+c-'0',c=gc();

    return x*f;

}

char buffer[20],top;

inline void write(int x)

{

    if(x==0)

    {

        pc('0');

        //pc(en);

        return;

    }

    top=0;

    if(x<0) putchar('-'),x=-x;

    while(x) buffer[++top]=x%10+'0',x/=10;

    for(int i=top;i;i--)

        putchar(buffer[i]);

    //putchar(en);

    return;

}

#define ma 25

inline int rd(int l,int r)

{

    return (rand())%(r-l+1)+l;

}

int a[ma][ma];

struct col

{

    int x[ma][ma];

    inline int getq(int n,int m)

    {

        int q=0;

        for(int i=1;i<=m;i++)

           for(int j=1;j<n;j++)

                if(x[j][i]^x[j+1][i])

                    q++;

        for(int i=1;i<=n;i++)

            for(int j=1;j<m;j++)

                if(x[i][j]^x[i][j+1])

                    q++;

        return q;

    }

    inline void setit(int n,int m)

    {

        for(int i=1;i<=n;i++)

            for(int j=1;j<=m;j++)

                x[i][j]=a[i][j];

        return;

    }

    inline void out(int n,int m)

    {

        for(int i=1;i<=n;i++)

        {

            for(int j=1;j<=m;j++)

                write(x[i][j]),putchar(' ');

            putchar('\n');

        }

        return;

    }

};

int p[55];

col now;

inline void SA(int n,int m,col &an)

{

   // now=an;

    double T=3.587,endT=1e-16,deta=0.99999;

    int ans=an.getq(n,m);

    int sum;

    for(;T>endT;T*=deta)

    {

        int x1=rd(1,n);

        int x2=rd(1,n);

        int y1=rd(1,m);

        int y2=rd(1,m);

        //while(x1==x2&&y1==y2)

          //  x1=rd(1,n),x2=rd(1,n),y1=rd(1,m),y2=rd(1,m);

        swap(now.x[x1][y1],now.x[x2][y2]);

        sum=now.getq(n,m);

        if(sum<ans)

            ans=sum,an=now;

        else if(exp((ans-sum)/T)<((double)(rand()))/RAND_MAX)

            swap(now.x[x1][y1],now.x[x2][y2]);

        else if(sum-ans>0.85*T)

            now=an,sum=ans;

    }

}

inline col getans(int n,int m)

{

    col ans;

    ans.setit(n,m);

   // for(int i=1;i<=n*m;i++)

   //     swap(ans.x[rd(1,n)][rd(1,m)],ans.x[rd(1,n)][rd(1,m)]);

    now=ans;

    int ti=1;

    while(ti--)

    SA(n,m,ans);

    return ans;

}

signed main()

{

    //srand(20060307);

    srand(time(0));

    //srand(rand()^19260817);

    int n=read(),m=read(),c=read();

    int h=1,l=1;

    for(int i=1;i<=c;i++)

    {

        p[i]=read();

        while(p[i]--)

        {

            a[h][l]=i;

            l++;

            if(l>m)

                h++,l=1;

        }

    }

    col ans=getans(n,m);

    ans.out(n,m);

}
2020/7/15 19:46
加载中...