题解：P17242 [IOI 2026] 方块游戏 / tiling

_MCYYDS_ · 2026-08-12 14:18:54 · 题解

考虑最极端的情况，每个 2\times 2 小块都只有一个白色块（如果不止一个，可以任取其中一个白色小块，并将剩下三个白色小块视为黑色）。观察到如果 2\times 2 的小方块在某一个角是白色的，那么将小方块放到相反的角落一定满足条件，举个例子：

如上图，我们可以让要填在左上角的小块和右上角的小块放在同一行，当一行填满后再从下一行开始填，由于白块在放的角的对面，因此一定不会出现 2\times 2 的黑色小块（每相邻两行中有一行是全黑，剩下一行里面每相邻两 1\times 1 小块至少有一个白色）。对于要填左下角和右下角的小块同理。对于上下中间的交汇，让要填左上和左下的小块填左边，右上和右下的小块填右边即可，如图：

其中中间两行是交汇处，左边填的部分偶数行一定有一个白色，右边填的部分奇数行一定有一个白色，而中间（列）交汇处的两列都有一个白色。对于中间行和上下两行的相较（即图片中的第 2, 3 行和 4, 5 行），显然上下两行都不是全黑的那一行，所以满足条件。

代码：

#include<bits/stdc++.h>
#define pii pair<int,int>
using namespace std;
int n,m;
int mp[101][101],up,down,lu,ru,ld,rd,op,l,r;
void init(int _n,int _m)
{
    n=_n,m=_m;
    up=0,down=n-1;
    lu=ld=0,ru=rd=m-1;
    l=r=-1;
}
pii receive_block(int tl,int tr,int bl,int br)
{
    if(up==down)
    {
        if(l==-1)l=max(lu,ld),r=min(ru,rd);
        pii ans;
        if(!tl||!bl)
        {
            ans={down<<1,r<<1};
            r--;
        }
        else
        {
            ans={down<<1,l<<1};
            l++;
        }
        return ans;
    }
    if(!tl)
    {
        pii ans={down<<1,rd<<1};
        rd--;
        if(rd<ld)
        {
            down--;
            ld=0,rd=m-1;
        }
        return ans;
    }
    if(!tr)
    {
        pii ans={down<<1,ld<<1};
        ld++;
        if(rd<ld)
        {
            down--;
            ld=0,rd=m-1;
        }
        return ans;
    }
    if(!bl)
    {
        pii ans={up<<1,ru<<1};
        ru--;
        if(ru<lu)
        {
            up++;
            lu=0,ru=m-1;
        }
        return ans;
    }
    if(!br)
    {
        pii ans={up<<1,lu<<1};
        lu++;
        if(ru<lu)
        {
            up++;
            lu=0,ru=m-1;
        }
        return ans;
    }
}