[IOI 2026] tiling
2026-08-17 08:42:20
发布于：浙江
46阅读
0回复
0点赞
签。
天啊 升绿了，天啊我的黄怎么没变少？！（又降回来了）
破案了，P17250 签到 从灰变黄了（应该是这样）
P17242 [IOI 2026] 方块游戏 / tiling
这个和某个游戏很像，就是有 的方块，每个方块都由 黑/白 组成，其中每个方块必有一个白，但不一定只有一个，给出一个 的棋盘，我们要使把所有的方块放完后棋盘内任意位置都不出现 的黑色。
构造题，看到的时候先乱搞拿了大概 左右（因为洛谷的评测机是捆绑测试的），后面发现不是把每个白放在同个方位就行，因为不能转。
看了 一位巨佬的题解 后得到了思路，我们把每个方块的白色都朝着没填的地方放，对于每个 的黑，只有 种可能出现。
情况1：
它由两个方块的 上下/左右 两黑拼成，就是
黑黑
————
黑黑
由于上面白色是靠近中心的，下面的白色是靠近中心的，那么这四个里面必出一个白，不成立。
情况2：
它由四个方块的不同角拼成，就是这样
黑|黑
————
黑|黑
但由于我们都是把白色的放在靠近中心的地方的，那么左上的方块的右下角必然是白，其余同理，这样这四个里面也必出一白，不成立。
时间复杂度 ，能过。
#include <iostream>
using namespace syh;
int n, m;
bool vis[105][105];//标记2*2方块是否被用了（为啥是vis?）
pair<int,int> solve(int x)
{
//四个角
//遍历棋盘找符合要求的第一个方块
if(x==1)//左上
{
for(int i = 0;i<n;i++)
{
for(int j = 0;j<m;j++)
{
if(!vis[i][j]) return {i,j};
}
}
}
else if(x==2)//右上
{
for(int i = 0;i<n;i++)
{
for(int j = m-1;j>=0;j--)
{
if(!vis[i][j]) return {i,j};
}
}
}
else if(x==3)//左下
{
for(int i = n-1;i>=0;i--)
{
for(int j = 0;j<m;j++)
{
if(!vis[i][j]) return {i,j};
}
}
}
else//右下
{
for(int i = n-1;i>=0;i--)
{
for(int j = m-1;j>=0;j--)
{
if(!vis[i][j]) return {i,j};
}
}
}
}
void init(int N,int M)
{
n=N;
m=M;
}
pair<int, int> receive_block(int TL, int TR, int BL, int BR)
{
auto p=solve(!TL ? 4:(!TR ? 3:(!BL ? 2:1 ) ) );//谁是白就执行哪个角的solve
int x=p.first, y=p.second;
vis[x][y]=1;//这个也要被放
return {2*x,2*y};
}
有帮助，赞一个