AcWing 5055. 画矩形

来自 AcWing 第 113 场周赛，题目链接

赛时没看出来是一个组合数问题。

在 n 条边种选择 k*2 条，然后第 1 条和第 k*2 条，第 2 条和第 k*2-1 条，以此类推。

答案为：$C(n-1, k\times 2)\times C(m-1, k\times 2)$

Code

LeetCode 6955. 长度递增组的最大数目

来自 LeetCode 第 355 场周赛，题目链接

一个很难想到的构造题。

假设 usageLimits 是单调递增的。

对于长度为 $n$ 的 usageLimits ，如果对于 usageLimits[i] >= i + 1 ，则按照下面的构造方式即可。

1
2
3
4
5

0 1 2 3 4
  1 2 3 4
    2 3 4
      3 4
        4

接下来考虑 [1, 2, 2] 这种情况，只能构造出 $2$ 个，因为如果要生成第三组的话，就需要三个数，这里不足够三个。

1
2

0 1 
  1

如果要在上述的情况中，满足可以生成第三组，要么是 [1, 2, 3] ，要么是 [1, 2, 2, 1] 。 对于 [1, 2, 3]

1
2
3

0 1 2
  1 2
    2

对于 [1, 2, 2, 1]，因为我们假设是单调递增的，所以转换为 [1, 1, 2, 2]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

0 
---------
0
---------
0 1
  2
---------
0 1 2
  2 3
    3

一种是数 i 的数量不能构成新的一组，数 i 和 数 i+1 的数量可以构成新的一组，并且还有多余 数 i+1 剩余的数量和数 i+2 的数量可以构成下面一组，那么是否存在一种构造方案使得这两组中的数 i+1 不会冲突，即不在一行。

假设： 数 i 有 x 个， 数 i+1 有 y 个， 数 i+2 有 z 个，

根据我们先前的定义：x <= y <= z

假设数 i 和数 i+1 构成第 a 组，需要 a 个数 即 x + y >= a，那么剩下数 i+1 的数量为 y-(a-x)

对于第 a+1 组，需要 a+1 个数，由于只有数 i+1 之间存在冲突， 那么先将对应行已经有数 i+1 的，全部用 i+2 填充，因为 z >= y，所以必然可以全部覆盖，剩下的位置全部用多余的 i+1 填充即可。

你可能会有疑问，如果某一组需要三种数才能构成，会冲突吗？

待补。。。