社区讨论
SA调参头秃了,求救
P3936Coloring参与者 6已保存回复 6
讨论操作
快速查看讨论及其快照的属性,并进行相关操作。
- 当前回复
- 6 条
- 当前快照
- 1 份
- 快照标识符
- @lodk1r7i
- 此快照首次捕获于
- 2023/10/31 07:52 2 年前
- 此快照最后确认于
- 2023/11/06 23:04 2 年前
CPP
#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);
}
回复
共 6 条回复,欢迎继续交流。
正在加载回复...