Open Wizmann opened 4 years ago
Code Contest
先快速写一个版本，后面再补齐吧
我们把初始状态（n个1）和最终状态写在两行。然后画箭头将球进行转移。 如果所有的箭头不相交（可以有相同的目标点），那么一定有解。 可以很容易的观察得出，我们可以从左边开始，向右画依次箭头。最后把这种策略转化成题目要求的图即可。
DP可做。
又通过暴力枚举，我们可以观察到R和B的基本是连续的，也就意味着最大值不会超过sqrt(n)。所以在O(n n n)的复杂度下可做。
我觉得一般情况下就不要乱猜结论了。。。浪费时间还做不对。。。
二分图裸题。
为啥我就看不出来呢？。。。
先写我自己的做法，标程比我的优一个数量级。后面补。 这题是不难的，只要不写挫了就行。
观察得出，最终结果一定是原图2x2的格子经过放大之后形成的pattern。每一个原图的格子放大到n * n个格子即可。（假设n > m，这样可以足够包裹之前的小矩形了）
因为2x2的格子最多有2^4=16种可能。我们在原矩阵中枚举这些可能性，然后对其进行放大。然后把原矩阵放到放大后的矩阵进行匹配，然后在其中找到最大的联通图形。
最大的时间复杂度是（假设 n > m）：
所以总的复杂度是O(n^4)，常数是64。加点优化，勉强能用Pypy卡过去，对C++来说应该不是问题。
原题的解法也是枚举16种格子，然后在原矩阵上划十字线（四个象限）。在每个象限上找相对应的颜色，然后找联通块。这样的常数是16，复杂度是O(n^4)。
Code Contest
A. Falling Balls
我们把初始状态（n个1）和最终状态写在两行。然后画箭头将球进行转移。 如果所有的箭头不相交（可以有相同的目标点），那么一定有解。 可以很容易的观察得出，我们可以从左边开始，向右画依次箭头。最后把这种策略转化成题目要求的图即可。
B. Graceful Chainsaw Jugglers
DP可做。
又通过暴力枚举，我们可以观察到R和B的基本是连续的，也就意味着最大值不会超过sqrt(n)。所以在O(n n n)的复杂度下可做。
C. Costume Change
二分图裸题。
D. Gridception
观察得出，最终结果一定是原图2x2的格子经过放大之后形成的pattern。每一个原图的格子放大到n * n个格子即可。（假设n > m，这样可以足够包裹之前的小矩形了）
因为2x2的格子最多有2^4=16种可能。我们在原矩阵中枚举这些可能性，然后对其进行放大。然后把原矩阵放到放大后的矩阵进行匹配，然后在其中找到最大的联通图形。
最大的时间复杂度是（假设 n > m）：
所以总的复杂度是O(n^4)，常数是64。加点优化，勉强能用Pypy卡过去，对C++来说应该不是问题。