分裂 题解

· · 题解

定位签到题，所以不讲部分分（雾

按题意模拟即可。但是直接模拟是 O(n^4) 的，考虑优化。容易想到的优化就是用数据结构维护。发现 v 的值很小，所以只要开 10 个 set 来维护每种棋子就可以了。时间复杂度 O(n^2\log{n})。

Code:

#include<set>
#include<cctype>
#include<cstdio>
#define rg register
inline char rc()
{
    static char buf[524288],*pn=buf,*pe=buf;
    return (pn==pe)&&(pe=(pn=buf)+fread(buf,1,524288,stdin),pn==pe)?EOF:*pn++;
}
inline int read()
{
    int x=0;
    char cc=rc();
    while(!isdigit(cc))cc=rc();
    while(isdigit(cc))x=(x*10+cc-'0'),cc=rc();
    return x;
}
using std::set;
int n,m,k,v,r,c;
int a[1003][1003];
int bs[1003][1003];
int res[1003][1003];
struct bd
{
    int x,y;
    bool operator <(const bd &t)const
    {
        if(bs[x][y]==bs[t.x][t.y])
        {
            if(x+y==t.x+t.y)return x<t.x;
            return (x+y)<(t.x+t.y);
        }
        return bs[x][y]>bs[t.x][t.y];
    }
};
inline bd make(int x,int y)
{
    bd nw;
    nw.x=x,nw.y=y;
    return nw;
}
set<bd>S[13];
inline void upd(int r,int c)
{
    int vl=a[r][c];
    bd nw=make(r,c);
    if(!S[vl].count(nw))return;
    S[vl].erase(nw);
    ++bs[r][c],S[vl].insert(nw);
}
int main()
{
    n=read(),m=read();k=n*m;
    for(rg int i=1;i<=n;++i)
    {
        for(rg int j=1;j<=m;++j)
        {
            a[i][j]=read();
            bs[i][j]+=(i==1),bs[i][j]+=(i==n);
            bs[i][j]+=(j==1),bs[i][j]+=(j==m);
            S[a[i][j]].insert(make(i,j));
        }
    }
    for(rg int i=1;i<=k;++i)
    {
        v=read();
        set<bd>::iterator tmp=S[v].begin();
        r=tmp->x,c=tmp->y;
        S[v].erase(tmp),res[r][c]=i;
        if(r>1)upd(r-1,c);
        if(r<n)upd(r+1,c);
        if(c>1)upd(r,c-1);
        if(c<m)upd(r,c+1);
    }
    for(rg int i=1;i<=n;++i)
    {
        for(rg int j=1;j<m;++j)printf("%d ",res[i][j]);
        printf("%d\n",res[i][m]);
    }
    return 0;
}