P17242 [IOI 2026] Tiling Game
zhlzt
·
·
题解
IOI 也会有签。
令 S=TL+TR+BL+BR。
将 “L” 按拐点所处的位置分为左上、右上、左下、右下四类。那么可以按照以下策略放置：
- 将第一类（左上）放在当前未被填充的 $i+j$ 最小的位置。
- 将第二类（右上）放在当前未被填充的 $i-j$ 最小的位置。
- 将第三类（左下）放在当前未被填充的 $-i+j$ 最小的位置。
- 将第四类（右下）放在当前未被填充的 $-i-j$ 最小的位置。
:::info[为什么该策略是对的]
一个不合法局面的例子：
```
⬜⬛ ⬛⬛
⬛⬛ ⬛⬜
```
证明我们的策略不可能造成该局面的出现：
- 反证法，假设该局面出现。
- 不妨设右侧的 2×2 方块先被填充。
- 由于左侧方块的 $i+j$ 比右侧方块小，故填充第一类 “L” 形时会优先选择左侧方块。
- 与假设矛盾，证毕。
:::
代码中使用 `set` 来维护。
注意在洛谷上提交时要把 `#include<tiling.h>` 删掉。
```cpp line-numbers
#include<tiling.h>
#include<bits/stdc++.h>
using namespace std;
int n,m;
set<pair<int,pair<int,int>>>st[4];
void init(int N,int M){
n=N,m=M;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
st[0].insert({i+j,{i,j}});
st[1].insert({i-j,{i,j}});
st[2].insert({-i+j,{i,j}});
st[3].insert({-i-j,{i,j}});
}
}
}
pair<int,int> receive_block(int TL,int TR,int BL,int BR){
pair<int,int>res;
if(!BR) res=(*st[0].begin()).second;
else if(!BL) res=(*st[1].begin()).second;
else if(!TR) res=(*st[2].begin()).second;
else res=(*st[3].begin()).second;
auto [i,j]=res;
st[0].erase({i+j,{i,j}});
st[1].erase({i-j,{i,j}});
st[2].erase({-i+j,{i,j}});
st[3].erase({-i-j,{i,j}});
return make_pair(i<<1,j<<1);
}
```