大佬求助 AC#1 70
查看原帖
大佬求助 AC#1 70
381643
Stairs_upon_temple楼主2024/8/27 20:55
/*
g++ -o2 P3936.cpp -o c -std=c++14\
.\c

*/

#include<cstdio>
#include<cmath>
#include<ctime>

// #define double long double

using namespace std;
// typedef double long double;

int dx[5]={0,1,-1,0,0};
int dy[5]={0,0,0,1,-1};

const int N=60;
const int inf=0x3f3f3f3f;

int n,m,c;
int map[N][N];
int p[N];
int ans=inf;

// int pri[N][N];

inline int max(int a,int b){return a>b?a:b;}
inline int min(int a,int b){return a<b?a:b;}

inline void swap(int &x,int &y){
    int t=y;
    y=x;
    x=t;
    return ;
}

inline int calc(int x1,int y1,int x2,int y2){
    int res=0;
    for(int k=1;k<=4;k++){
        int nx=x1+dx[k];
        int ny=y1+dy[k];
        if(nx<1 || nx>n)continue;
        if(ny<1 || ny>m)continue;
        if(map[nx][ny]!=map[x1][y1])res++;
    }
    for(int k=1;k<=4;k++){
        int nx=x2+dx[k];
        int ny=y2+dy[k];
        if(nx<1 || nx>n)continue;
        if(ny<1 || ny>m)continue;
        if(map[nx][ny]!=map[x2][y2])res++;
    }
    // ans=min(ans,res/2);
    return res/2;
}

inline void simulate(){
    double t=1000;
    while(t>1e-16){
        int rx=rand()%n+1;
        int ry=rand()%m+1;
        int nx=rand()%n+1;
        int ny=rand()%m+1;
        int cnt=calc(rx,ry,nx,ny);
        swap(map[rx][ry],map[nx][ny]);
        int tmp=calc(rx,ry,nx,ny);
        int d=cnt-tmp;
        if(exp((double)-d/t) > (double)rand() / RAND_MAX){
            swap(map[rx][ry],map[nx][ny]);
        }
        t=t*0.9999995;
    }
    return ;
}

int han,zon;

void pri(){
    ans=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            for(int k=1;k<=4;k++){
                int nx=i+dx[k];
                int ny=j+dy[k];
                if(nx<1 || nx>n)continue;
                if(ny<1 || ny>m)continue;
                if(map[nx][ny]!=map[i][j])ans++;
            }
        }
    }
    ans/=2;
    printf("%d\n",ans);
    return ;
}

int main(){
    freopen("P3936_2.in","r",stdin);
    // srand(20080201); last npy's birthday
    han=1;
    zon=1;
    scanf("%d%d%d",&n,&m,&c);
    for(int i=1;i<=c;i++){
        scanf("%d",&p[i]);
        for(int j=1;j<=p[i];j++){
            map[han][zon]=i;
            zon++;
            if(zon==m+1){
                zon=1;
                han++;
            }
        }
    }
    // for(int i=1;i<=n;i++){
    //     for(int j=1;j<=m;j++){
    //         printf("%d ",map[i][j]);
    //     }
    //     printf("\n");
    // }
    // for(int i=1;i<=100;i++)simulate();
    while((double)clock() / CLOCKS_PER_SEC <4.5)simulate();
    // simulate();
    pri();
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
    return 0;
}
2024/8/27 20:55
加载中...