题解：P17669 [IO 2025 #4] 卢拉的火柴魔术

· · 题解

题目大意

给定一个由 2\times n 个小方格组成的火柴网格，求至少拿走多少根火柴，才能使剩下的火柴无法围成任何矩形。

这里的矩形要求两条水平边和两条竖直边都完整，没有缺口。

思路

题目最底下的图给了我们一点启发，记住左图这个数字 2 形状的东西，我们不妨把 n=3 的效果图变一下：

就变成了一个数字 2 加上一个镜面的 C。

这样好看多了后，我们这样想，我们每次都向右填满后一直扩展，看看会有怎么样一个规律。

从 n=1 到 n=2 时，新增一列与原网格共用边 ①，而这条边已经被取走。因此，只需再取走边 ②，就能得到图中的方案，取走的火柴数增加 1。

从 n=2 到 n=3 时，我们再取走边 ③ 和边 ④，使新增部分也形成数字 2 的形状，取走的火柴数增加 2。

再多做几种情况，就发现了规律，往后无非就是填满后删一条或者两条边，到达 n=3 后你会发现它的右侧又变回 n=1 时候的情况了，这样就是不断循环下去。

看不懂？高亮一波：

就是这个数字 2 形状的东西，不断出现，非常有规律，而且很显然这样做是最优的了。

于是得出递推关系，设 f(n) 表示答案，初始时 f(1)=2 以及 f(2)=3。对于 n\ge 3：

本质等价于 \left\lceil \frac{3n}{2}\right\rceil。

简单证明

每次向右扩展时，按照图中的方式交替增加 1 根、2 根需要取走的火柴，就能让右侧不断重复之前的形状。这种构造共取走 \left\lceil\frac{3n}{2}\right\rceil 根火柴。

下面说明不能取得更少。分别考虑上面一行、下面一行，以及忽略中间横边后的整个长条。这三个长条各有 n 个封闭区域，每取走一根火柴，至多使其中一个长条的封闭区域数减少 1。要使一个长条中没有矩形，至少需要取走 n 根属于它的火柴。

而每根火柴恰好属于其中两个长条，所以取走 k 根火柴，必须满足 2k\ge 3n，即 k\ge\left\lceil\frac{3n}{2}\right\rceil。

我们的构造恰好达到这个下界，因此是最优的了。

代码

#include<bits/stdc++.h>
#define int long long
#define endl '\n'
using namespace std;
int a[10010];
signed main(){
    int n;
    cin>>n;
    a[1]=2;
    a[2]=3;
    for(int i=3;i<=n;i++){
        if(i%2==1) a[i]=a[i-1]+2;
        else a[i]=a[i-1]+1;
    }
    cout<<a[n]<<endl;
}

致谢

本文配图由本人提供草图，ChatGPT 辅助绘制与调整。