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;
}
回顾
其实不难，细致即可。