• 欢迎光临~

trick

开发技术 开发技术 2022-08-06 次浏览

感觉很常见啊啊啊啊啊啊啊

有印象的好像见了 4 次,2 次想出来了。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。

就是考虑抽象每个数的可选择区间,考虑构造一个合法的匹配。

那么考虑从选择区间小的开始试,因为选择区间大的可选的更多嘛。

正确性?扫描线加上去感觉挺显然的。亦或是咱想想找一个数的二进制组成,是不是从大到小试啊?

例子:某个牛客,某场 CF,某个 AT,某场 CF。

比如有 n 行 m 列,然后每个砖块的高度为 1,限制只能横放。那么就按宽度从大到小一行一行试着能不能放。

又比如

https://codeforces.com/contest/1713/problem/C

考虑大的一定选择的比较少,因为平方的增长很快,大的后面的平方数肯定稀疏得多。且大的平方数能匹配到的一定更少。所以从大到小尝试从大到小选择。

程序员灯塔
转载请注明原文链接:trick
喜欢 (0)