题解 P7218 【[JOISC2020] 伝説の団子職人】

· · 题解

题意

略。

题解

我我我再也不做调参人了！

参数是重新调的（因为原来的答案丢了），抢了个你谷首 A 还是蛮开心。/cy

一开始想的是枚举白色团子匹配哪两个，如果能匹配就匹配，发现这东西只能写随机贪心，于是考虑变换一下枚举绿色或者粉色，大概这样：

对于一个当前没有匹配的非白色团子，枚举八个方向看能不能匹配，如果能匹配且不会带来冲突则匹配，否则撤销与之冲突团子的匹配，然后类似匈牙利解决冲突问题。

但是这个东西并不能一遍求出最优解，所以大概可以考虑刷一下。对于每一个情况随很多方案出来取个 \max 得到最优方案。

但是这个所谓的最优方案有些时候还不够，于是考虑用这个初始解去刷更好的解，类似模拟退火一样一开始随机的幅度很大，然后后面随机幅度很小来调整，然后多花点时间刷解应该能行。

提交的答案是这样的：

Data 1: 47220
Data 2: 41984
Data 3: 51391
Data 4: 19129
Data 5: 48625
Data 6: 46503

由于增加了许多一轮刷解时候的次数所以目前得到的结果比之前的那一份解法要好，如果大家有更好的答案可以联系我。

下面的代码大概是这么用的：输入测试数据编号和参数（参数为 0 则为刷一个比较好的初始解存到 .out1 中，参数为 1 则意味着从 .out1 中得到一份好的初始解刷一个更好的），然后一轮大概是 500s 左右的样子可以跑出一个比较好的解，毕竟提答题就是看耐心以及算法的优秀程度。

如果并行的话应该能够在 30min 之内跑完所有 6 个数据。

代码

#include<bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef int ll;
typedef long long int li;
typedef pair<ll,ll> pii;
const ll MAXN=505;
vector<pii>v;
ll n,m,r,rr,par,tp;
string test;
mt19937 mt(time(0));
ll vx[8]={1,-1,0,0,1,-1,1,-1},vy[8]={0,0,1,-1,1,-1,-1,1};
ll vis[MAXN][MAXN],match[MAXN][MAXN][2],matchr[MAXN][MAXN][2];
char ch[MAXN][MAXN],chr[MAXN][MAXN],res[MAXN][MAXN];
inline ll read()
{
    register ll num=0,neg=1;
    register char ch=getchar();
    while(!isdigit(ch)&&ch!='-')
    {
        ch=getchar();
    }
    if(ch=='-')
    {
        neg=-1;
        ch=getchar();
    }
    while(isdigit(ch))
    {
        num=(num<<3)+(num<<1)+(ch-'0');
        ch=getchar();
    }
    return num*neg;
}
inline char getId(char x)
{
    return x=='|'?0:x=='-'?1:x=='\\'?2:3;
}
inline char getOp(ll x)
{
    return "|-\\/"[x>>1];
}
inline ll dfs(ll x,ll y)
{
    ll wx,wy,px,py,cx,cy;
    if(vis[x][y])
    {
        return 0;
    }
    vis[x][y]=1,v.push_back((pii){x,y});
    for(register int i=0;i<8;i++)
    {
        wx=x+vx[i],wy=y+vy[i],px=wx+vx[i],py=wy+vy[i];
        if(ch[wx][wy]=='W'&&ch[px][py]+ch[x][y]=='P'+'G')
        {
            cx=match[px][py][0],cy=match[px][py][1],ch[wx][wy]=getOp(i);
            if(cx==-1||dfs(cx,cy))
            {
                if(cx!=-1)
                {
                    for(register int j=0;j<8;j++)
                    {
                        if(cx+2*vx[j]==px&&cy+2*vy[j]==py)
                        {
                            ch[cx+vx[j]][cy+vy[j]]='W';
                        }
                    }
                }
                match[px][py][0]=x,match[px][py][1]=y;  
                match[x][y][0]=px,match[x][y][1]=py;
                return 1;
            }   
            ch[wx][wy]='W';
        }
    }
    return 0;
}
inline void calc(ll op)
{
    vector<pii>cc;
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++)
        {
            ch[i][j]!='W'&&match[i][j][0]==-1?cc.push_back((pii){i,j}):(void)1;
        }
    }
    if(op)
    {
        shuffle(cc.begin(),cc.end(),mt);
    }
    for(auto i:cc)
    {
        if(match[i.first][i.second][0]==-1)
        {
            r+=dfs(i.first,i.second);
            for(auto j:v)
            {
                vis[j.first][j.second]=0;
            }
            v.clear();
        }
    }
}
inline void calc1(ll c)
{
    vector<pii>undo;
    memcpy(matchr,match,sizeof(match)),memcpy(chr,ch,sizeof(ch)),rr=r;
    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=m;j++)
        {
            !isupper(ch[i][j])?undo.push_back((pii){i,j}):(void)1;
        }
    }
    shuffle(undo.begin(),undo.end(),mt);
    for(auto i:undo)
    {
        if(!(mt()%(ll)ceil(1.5*c)))
        {
            ll x=i.first,y=i.second,tp=getId(ch[x][y]);
            ch[x][y]='W',r--;
            match[x+vx[tp<<1]][y+vy[tp<<1]][0]=-1;
            match[x+vx[tp<<1]][y+vy[tp<<1]][1]=-1;
            match[x+vx[tp<<1|1]][y+vy[tp<<1|1]][0]=-1;
            match[x+vx[tp<<1|1]][y+vy[tp<<1|1]][1]=-1;
        }
    }
    calc(1);
    if(r<rr)
    {
        memcpy(match,matchr,sizeof(match)),memcpy(ch,chr,sizeof(ch)),r=rr;
    }
}
int main()
{
    cin>>test,par=read();
    if(par==0)
    {
        freopen((test+".in").c_str(),"r",stdin);
        freopen((test+".out1").c_str(),"w",stdout);
    }
    if(par==1)
    {
        freopen((test+".out1").c_str(),"r",stdin);
        freopen((test+".out").c_str(),"w",stdout);
    }
    srand(time(0));
    memset(match,-1,sizeof(match));
    if(par==1)
    {
        n=m=500;
    }
    else
    {
        n=read(),m=read();
    }
    fprintf(stderr,"%d %d\n",n,m);
    for(register int i=1;i<=n;i++)
    {
        scanf("%s",ch[i]+1);
    }
    fprintf(stderr,"%d\n",strlen(ch[1]+1));
    if(par)
    {
        for(register int i=1;i<=n;i++)
        {
            for(register int j=1;j<=m;j++)
            {
                if(!isupper(ch[i][j]))
                {
                    tp=getId(ch[i][j]),r++;
                    match[i+vx[tp<<1]][j+vy[tp<<1]][0]=i+vx[tp<<1|1];
                    match[i+vx[tp<<1]][j+vy[tp<<1]][1]=j+vy[tp<<1|1];
                    match[i+vx[tp<<1|1]][j+vy[tp<<1|1]][0]=i+vx[tp<<1];
                    match[i+vx[tp<<1|1]][j+vy[tp<<1|1]][1]=j+vy[tp<<1];
                }
            }
        }
    }
    else
    {
        calc(0);
    }
    fprintf(stderr,"%d\n",r);
    for(register int i=1;i<=200;i++)
    {
        for(register int j=1;j<=60;j++)
        {
            calc1(i);
            if(j%10==0)
            {
                fprintf(stderr,"%d\n",r);
            }
        }
    }
    fprintf(stderr,"%d\n",r);
    for(register int i=1;i<=n;i++)
    {
        printf("%s\n",ch[i]+1);
    }
}