[AGC008C]Tetromino Tiling

XYukari · 2021-11-03 23:51:15 · 题解

更好的阅读体验

给出如下图的 7 种俄罗斯方块各 a,b,c,d,e,f,g 块，可以旋转不能翻转，要求拼成宽度为 2 的长方形。输出能得到的最大长度的一半——奇怪的题目要求。

不难发现，第 3,6,7 种方块压根用不上，因为它们造成了长度为 1 的凹槽，而这些凹槽永远不可能被填平：要填平它们，就要用这三种方块；用了这三种方块，又会有新的凹槽产生。

下面考虑每种方块“自力更生”能否拼出宽度为 2 的长方形：

第 1 种，竖着两个并排，长宽 4\times 2；
第 2 种，自己符合条件，长宽 2\times 2；
第 3,4 种，一个倒扣在另一个上面，长宽 4\times 2。

看起来长度的一半为 L=\lfloor\dfrac{a}{2}\rfloor\times 2+b+\lfloor\dfrac{d}{2}\rfloor\times 2+\lfloor\dfrac{e}{2}\rfloor\times 2。

还没完！我们继续考虑几种方块“通力合作”能否拼出宽度为 2 的长方形：只有一种方案，即第 1,4,5 种方块各一个，拼成长宽 6\times 2 的长方形，如下图所示：

以此为基础，我们对上面的式子进行修正：

如果第 1,4,5 种方块都为奇数，在满足“自力更生”前提下，每种恰有一块剩余，可以组合，故 L\gets L+3；
如果第 1,4,5 种方块，只有两种为奇数，则最后会剩下两块。例如剩下了 1,4 各一块，这时，我们拆出一个 5，能得到更优的答案——拆出减 4，重组加 6，L\gets L+1。

下面是 AC 代码：

void main() {
    cin.tie(0), cout.tie(0);
    long long a, b, c, d, e, f, g;
    cin >> a >> b >> c >> d >> e >> f >> g;
    long long ans = (a / 2) * 2 + b + (d / 2) * 2 + (e / 2) * 2;
    if ((a & 1) + (d & 1) + (e & 1) >= 3)
            ans += 3;
    else if ((a & 1) + (d & 1) + (e & 1) >= 2 && (a > 0) && (d > 0) && (e > 0))//必须保证有，才能拆借
        ans++;
    cout << ans << endl;
}

虽然是 AGC 的 C 题，也没有那么难啊，主要是细节太多，如果放到 OI 赛制的模拟赛中，是一道很好的“签到题”。

[AGC008C]Tetromino Tiling

THE END