2023ICPC沈阳区域赛I题Three Rectangles补题

题意

有一个(0,0)（左下角）到(H,W)（右上角）的矩形区域，给出3个小矩形的h和w，要求3个矩形盖住矩形区域的放置方案：要求3个矩形不能旋转，只能放到整点上，不能超出矩形区域，可以重叠。mod 1e9+7。
H,W范围1e9， \(1\leq h_i \leq H, 1 \leq w_i \leq W\)

分析及实现

由3个小矩形盖住大矩形，通过思考可以发现，至少有一个小矩形有一条边等于大矩形的边长。 (h=H or w=W)

暂时以h = H 为例分析：

如果有至少一个矩形满足\(h_i=H,w_i=W\),这一个位置固定，其它的可以随意放。

如果只有一个矩形x满足h_x = H，则x一定放于大矩形一侧，其它两个一定盖住另外的两角，否则只能x盖满整个区域（上面已讨论到）。（至于一个放于一角时已经能和一侧的盖满整个大矩形的情况，对应有两个以上矩形满足h = H） 此时先判断另外两个和这个能不能盖满（则另外两个的宽和这个合起来能不能盖满W，另外两个的高度相加能不能盖满H）。
若能盖满，答案为4： 考虑到另外两个矩形的上下位置和x的左右位置，盖法要*4。

如果恰有两个矩形x,y满足h_x=H,h_y=H,则将这两个放于两侧，则这两个可以盖满大矩形（即宽度相加盖满W）等价于三个可以盖满。若可以，则计算第三个随意摆放的方案数即可。先不考虑左右矩形的位置，最后要乘以2。

如果三个x,y,z都满足h=H,则同样有两个矩形放于两侧。这里我的想法是模拟相当于1*W的长条形上三个滑动的情况，枚举放在两端和中间的矩形（限定了左右矩阵分别是哪个后，共有三种可能），然后计算中间的矩形能够滑动的距离（1.要盖住中间的空白区域;2.不能超过边界）（可见如果两端能盖满，中间的又可以随意摆放了）。
但这里可能会算重，因为中间随意摆放的那个矩形若能放到边缘，则会和其它情况算重：1、2在左边，3在右边若可行，则会被计数两次，这种情况会发生等价于1和2中至少一个能和3盖满。 因此，只要对每个矩形判断能不能和任意一个其它的矩形盖满大矩形，若能则方案数-1。
最后同样*2。

ps：一开始我不太确定，所以在小数据范围内循环模拟计数，对照了一下，认为是对的。

以h = H 为例的分析结束后：

如果h=H和w=W都不发生，方案数为0。
如果都发生，只需考虑不同矩形分别满足两项条件的情况：
可能满足h=H和w=W的分别有1个，此时它们一定分别盖住一边，选择一种讨论即可。
可能满足条件的分别有1个和2个，比如满足h=H和w=W的分别有1、2个，此时应该从w=W出发讨论。 因为此时满足h=H的不一定盖住矩形一边。

代码

因为开始思路不清，写的有点麻烦

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define endl '\n'
typedef unsigned long long ull;

const int N = 1e5;
const int INF = 0x3f3f3f3f3f3f3f3f;
const int MOD = 1e9 + 7;

void solve()
{
    int H, W;
    cin >> H >> W;
    int h[4], w[4];
    int cf = 0;
    int ch = 0, cw = 0;
    for (int i = 1; i <= 3; ++i)
    {
        cin >> h[i] >> w[i];
        if (h[i] == H && w[i] == W)
        {
            cf = 1;
        }
        if (h[i] == H)
        {
            ch++;
        }
        if (w[i] == W)
        {
            cw++;
        }
    }
    // cout << ch << " " << cw << endl;

    int ans = 1;

    if (cf == 1)
    {
        int ans = 1;
        for (int i = 1; i <= 3; ++i)
        {
            ans *= (H - h[i] + 1) % MOD * (W - w[i] + 1) % MOD;
            ans %= MOD;
        }
        cout << ans << endl;
        return;
    }

    int check = max(ch, cw);

    if (check == 0)
    {
        cout << 0 << endl;
        return;
    }

    if (ch < cw) // 对应 1 vs 2 的情况 ，旋转矩形
    {
        swap(H, W);
        swap(ch, cw);
        swap(h, w);
    }

    // ch!=0

    if (ch == 3)
    {
        ans = 0;
        if (w[1] + w[2] + w[3] < W)
        {
            cout << 0 << endl;
            return;
        }
        for (int mid = 1; mid <= 3; ++mid)
        {
            int cover = w[1] + w[2] + w[3] - w[mid];
            int add1 = 0;
            if (cover >= W)
            {
                add1 += (W - w[mid] + 1) % MOD;
                add1 %= MOD;
            }
            else
            {
                int step = W - cover;
                // 1    4   6
                int l, r;
                if (mid == 1)
                    l = 2, r = 3;
                if (mid == 2)
                    l = 1, r = 3;
                if (mid == 3)
                    l = 1, r = 2; //强制安排两侧左右位置
                int ndl2 = w[l] + 1;
                int ndl1 = W - w[r] - w[mid] + 1;
                ndl1 = max(ndl1, (int)1);
                ndl2 = min(ndl2, W - w[mid] + 1);
                if (ndl2 - ndl1 + 1 > 0)
                    add1 += ndl2 - ndl1 + 1;
                add1 %= MOD;
            }
            ans += add1;
            ans %= MOD;
        }

        for (int r = 1; r <= 3; ++r)
        {
            int l = 0;
            for (int i = 1; i <= 3; ++i)
            {
                if (r == i)
                    continue;
                l = max(w[i], l);
            }
            if (l + w[r] >= W)
            {
                ans -= 1; ///
                ans %= MOD;
                ans += MOD;
                ans %= MOD;
            }
        }

        ans *= 2;
        ans %= MOD;
        cout << ans << endl;
        return;
    }

    int L = 0;
    int pos = -1;
    for (int i = 1; i <= 3; ++i)
    {
        if (h[i] == H)
        {
            L = w[i];
            pos = i;
            break;
        }
    }

    if (h[1] + h[2] + h[3] - h[pos] < H)
    {
        cout << 0 << endl;
        return;
    }

    if (ch == 2)
    {
        for (int i = 1; i <= 3; ++i)
        {
            if (h[i] == H && i != pos)
            {
                if (w[i] + L < W)
                {
                    cout << 0 << endl;
                    return;
                }
            }
        }
        for (int i = 1; i <= 3; ++i)
        {
            if (h[i] != H)
            {
                ans *= (H - h[i] + 1) % MOD * (W - w[i] + 1) % MOD;
                ans %= MOD;
            }
        }
    }
    else
    {
        for (int i = 1; i <= 3; ++i)
        {
            if (i != pos)
            {
                if (w[i] + L < W)
                {
                    cout << 0 << endl;
                    return; ///////
                }
            }
        }
        ans *= 2;
        ans %= MOD;
    }
    ans *= 2;
    ans %= MOD;

    cout << ans << endl;
}

signed main()
{
    // cout.flags(ios::fixed); cout.precision(8);
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int T = 1;
    cin >> T;
    for (int i = 1; i <= T; ++i)
    {
        solve();
    }
    //////////////////////////用来测试的
    // int ww[3] = {5, 5, 4};
    // int n = 5;
    // int ans = 0;
    // for (int i = 1; i <= n; ++i)
    // {
    //     for (int j = 1; j <= n; ++j)
    //     {
    //         for (int k = 1; k <= n; ++k)
    //         {
    //             vector<int> s(n + 1, 0);
    //             if (i + ww[0] - 1 > n || j + ww[1] - 1 > n || k + ww[2] - 1 > n)
    //                 continue;
    //             for (int l = i; l <= i + ww[0] - 1; ++l)
    //             {
    //                 s[l] = 1;
    //             }
    //             for (int l = j; l <= j + ww[1] - 1; ++l)
    //             {
    //                 s[l] = 1;
    //             }
    //             for (int l = k; l <= k + ww[2] - 1; ++l)
    //             {
    //                 s[l] = 1;
    //             }
    //             int ok = 1;
    //             for (int l = 1; l <= n; ++l)
    //             {
    //                 if (s[l] == 0)
    //                     ok = 0;
    //             }
    //             if (ok)
    //             {
    //                 ans++;
    //             }
    //         }
    //     }
    // }
    // cout << ans << endl;

    return 0;
}


  	 	 			 	 		    	 	  	 	 		

回顾

其实不难，细致即可。