CF837C Two Seals 题解

· · 题解

CF837C Two Seals 题解

洛谷题目传送门\ Codeforces 题目传送门

第一步题意

选两枚印章在一个尺寸 a \times b 的纸上印两片印记。一共有 n (1 \le n \le 100) 种印章，第 i 枚印章的尺寸（或者说印在纸上的印记的尺寸）是 x_i \times y_i，允许旋转 90 度后再印，印记不能重叠和超出纸张。求这两片印记覆盖面积的最大值。

第二步做法

要使覆盖面积最大，两片印记一定是靠在一起的。

由于 n 很小，我们可以暴力枚举两枚印章，然后求这两个印章印出来的印记最大能覆盖的面积，然后求最大值即可。

第三步细节

难点在于判断这两片印记是否能放在纸张里。

每种印章都有两种状态印印记：第一种是不旋转，第二种是旋转。

两片印记的摆放方式也有两种：第一种是上下放，第二种是左右放。

有两种印章要印，所以一共有 2 \times 2 \times 2 = 8 种放法。

在判断是否能放在纸张里时，为了方便，我们可以把两片印记看成一个长方形（因为纸张和印章（印记）是长方形，这么做不会出现奇奇怪怪的问题）。

假设是选第 i 个印章和第 j 个印章印印记，8 种放法分别是：

第四步代码

:::info[完整代码（码风较丑勿喷）]

#include <bits/stdc++.h>

using namespace std;

const int N = 1e2 + 5;

int n, a, b, x[N], y[N];

signed main () {
    ios::sync_with_stdio (0), cin.tie (0), cout.tie (0);
    cin >> n >> a >> b;
    for (int i = 1; i <= n; i++)
        cin >> x[i] >> y[i];

    // 判断是否能放在纸张里
    auto check = [&] (int i, int j) -> int {
        if (x[i] + x[j] <= a && max (y[i], y[j]) <= b) // 第一个不旋转，第二个不旋转，左右放
            return 1;
        if (max (x[i], x[j]) <= a && y[i] + y[j] <= b) // 第一个不旋转，第二个不旋转，上下放
            return 1;
        if (x[i] + y[j] <= a && max (y[i], x[j]) <= b) // 第一个不旋转，第二个旋转，左右放
            return 1;
        if (max (x[i], y[j]) <= a && y[i] + x[j] <= b) // 第一个不旋转，第二个旋转，上下放
            return 1;
        if (y[i] + x[j] <= a && max (x[i], y[j]) <= b) // 第一个旋转，第二个不旋转，左右放
            return 1;
        if (max (y[i], x[j]) <= a && x[i] + y[j] <= b) // 第一个旋转，第二个不旋转，上下放
            return 1;
        if (y[i] + y[j] <= a && max (x[i], x[j]) <= b) // 第一个旋转，第二个旋转，左右放
            return 1;
        if (max (y[i], y[j]) <= a && x[i] + x[j] <= b) // 第一个旋转，第二个旋转，上下放
            return 1;
        return 0;
    };

    // 枚举印章并求答案
    int ans = 0;
    for (int i = 1; i <= n; i++)
        for (int j = i + 1; j <= n; j++)
            if (check (i, j))
                ans = max (ans, x[i] * y[i] + x[j] * y[j]);

    cout << ans << "\n";
    return 0;
}

:::

后记

我最讨厌分讨了喵 /kel。

制作不易，点个关注，再点个赞吧。

:::info[AI 使用说明] 使用 DeepSeek 润色文章。 :::